比赛链接
https://codeforces.com/contest/2020
A题
思路
按照 2 2 2的整次幂从大到小枚举。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, k;
int qmi(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
void solve()
{
cin >> n >> k;
if (k == 1)
{
cout << n << endl;
return;
}
int ans = 0;
for (int i = 30; i >= 0; i--)
{
int op = qmi(k, i);
if (op <= n && op > 0)
{
ans += (n / op);
n = n - (n / op) * op;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}
B题
思路
灯泡最后为开或关,与开关灯的操作次数有关。
每次开关灯的条件是包含因数 i i i,因此最后开着的灯的操作次数为偶数。
因为,只有平方数有奇数个因数,所以 [ 1 , n ] [1,n] [1,n]排除所有平方数的个数即为 k k k。
因此我们可以直接二分查找答案求解。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int k;
int func(int x)
{
return x - (int)(sqrtl(x));
}
void solve()
{
cin >> k;
int low = 1, high = 2e18;
while (low < high)
{
int mid = low + high >> 1;
if (func(mid) >= k)
{
high = mid;
}
else low = mid + 1;
}
cout << high << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}
C题
思路
所以可以从高位到低位贪心地确定 a a a的该位取什么值,然后分类讨论即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int b, c, d;
void solve()
{
cin >> b >> c >> d;
int ans = 0;
bool ok = true;
for (int j = 61; j >= 0; j--)
{
int bitb = (b >> j) & 1;
int bitc = (c >> j) & 1;
int bitd = (d >> j) & 1;
if (bitd == 1)
{
if (bitb == 1 && bitc == 1)continue;
if (bitb == 1 && bitc == 0)continue;
if (bitb == 0 && bitc == 1) {ok = false; continue;}
if (bitb == 0 && bitc == 0)ans += (1ll << j);
}
else
{
if (bitb == 1 && bitc == 1) {ans += (1ll << j); continue;}
if (bitb == 1 && bitc == 0) {ok = false; continue;}
if (bitb == 0 && bitc == 1) {ans += (1ll << j); continue;}
if (bitb == 0 && bitc == 0)continue;
}
}
if (!ok)
{
cout << -1 << endl;
}
else
{
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}
D题
思路
我们发现 d d d的大小只有 10 10 10。
我们可以将每一组 a , d , k a,d,k a,d,k视作一个区间。我们可以按照 d d d和 a % d a \% d a%d依次对每一个区间进行分组。
之后,我们按照分好的每个小组依次进行区间合并。
对于合并后的区间,我们使用并查集进行暴力缩点,最后统计连通块的数量即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m;
struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
vector<pair<int, int>> merge(vector<pair<int, int>>&segs)
{
vector<pair<int, int>>res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
{
if (ed < seg.first)
{
if (ed != -2e9) res.push_back({st, ed});
st = seg.first;
ed = seg.second;
}
else ed = max(ed, seg.second);
}
if (st != 2e9) res.push_back({st, ed});
return res;
}
void solve()
{
cin >> n >> m;
DSU dsu(n + 1);
map<int, map<int, vector<pair<int, int>>>>mp1;
map<int, set<int>>mp2;
for (int i = 1, a, d, k; i <= m; i++)
{
cin >> a >> d >> k;
if (!mp1.count(d))
{
mp1[d][a % d].push_back({a, a + k * d});
mp2[d].insert(a % d);
}
else
{
if (mp2[d].count(a % d))
{
mp1[d][a % d].push_back({a, a + k * d});
}
else
{
mp1[d][a % d].push_back({a, a + k * d});
mp2[d].insert(a % d);
}
}
}
for (auto mpp : mp1)
{
int d = mpp.first;
for (auto val : mpp.second)
{
vector<pair<int, int>>op = merge(val.second);
for (pair<int, int> & pii : op)
{
int a = pii.first;
int high = pii.second;
for (int i = a + d; i <= high; i += d)
{
dsu.merge(i - d, i);
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (dsu.find(i) == i) ans++;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}
E题
思路
概率 d p dp dp
我们发现 a i a_{i} ai最大为 1023 1023 1023,也就是 2 10 − 1 2^{10}-1 210−1。
我们令 d p i , j dp_{i,j} dpi,j表示前 i i i个数,最终值为 j j j时的概率,状态转移方程为:
d p [ i ] [ j ] = d p [ i − 1 ] [ j ⊕ a [ i ] ] × p [ i ] 1 e 4 + d p [ i − 1 ] [ j ] × ( 1 − p [ i ] 1 e 4 ) dp[i][j] = dp[i-1][j \oplus a[i]] \times \frac{p[i]}{1e4} + dp[i-1][j] \times (1-\frac{p[i]}{1e4}) dp[i][j]=dp[i−1][j⊕a[i]]×1e4p[i]+dp[i−1][j]×(1−1e4p[i])
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n;
int a[N], p[N];
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MLong {
i64 x;
constexpr MLong() : x{} {}
constexpr MLong(i64 x) : x{norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
explicit constexpr operator i64() const {
return x;
}
constexpr MLong operator-() const {
MLong res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MLong &operator*=(MLong rhs) & {
x = mul(x, rhs.x, getMod());
return *this;
}
constexpr MLong &operator+=(MLong rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong &operator-=(MLong rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong &operator/=(MLong rhs) & {
return *this *= rhs.inv();
}
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
i64 v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};
template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 1000000007;
using Z = MInt<P>;
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> p[i];
}
int m = 1ll << 10;
const Z inv1e4 = Z(10000).inv();
vector<Z>dp(m);
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
vector<Z>f(m);
for (int j = 0; j < m; j++)
{
f[j ^ a[i]] += dp[j] * p[i] * inv1e4;
f[j] += dp[j] * (Z(1ll) - p[i] * inv1e4);
}
dp.swap(f);
}
Z ans = 0;
for (int i = 0; i < m; i++)
{
ans += Z(1) * i * i * dp[i];
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}