Codeforces Round 976 (Div. 2)（A，B，C，D，E）并查集，区间合并，概率dp

比赛链接

https://codeforces.com/contest/2020

A题

思路

按照$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$，因此最后开着的灯的操作次数为偶数。

因为，只有平方数有奇数个因数，所以$[1,n]$排除所有平方数的个数即为$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$的该位取什么值，然后分类讨论即可。

代码

#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$的大小只有$10$。

我们可以将每一组$a,d,k$视作一个区间。我们可以按照$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题

思路

概率$dp$

我们发现$a_i$最大为$1023$，也就是$2^{10}-1$。

我们令$d{p}_{i,j}$表示前$i$个数，最终值为$j$时的概率，状态转移方程为：

$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})$

代码

#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;
}