题目链接：codeforces 1670F 题解 首先，对于 sum，有 根据前缀的思想，所以得到 ans = sum[r] - sum[l-1]。 于是问题转化为和为 sum 的情况下异或和等于 z 的方案数。 不难想到，当 z 的某位上为 时，说明这个位置上的 1 的个数为奇数，反之，则为偶数。 定义 dp[i][j] 为前 i 位且第 i 位上 的剩余个数为 j 的方案数。 定义状态转移方程为 dp[k][t] += dp[k+1][min(n, y - t)] * C[n][t]，其中y 是当前位 的个数的最大值。于是可以理解为前 k 位且第 k 位上 的剩余个数为 t 的状态前 k+1 位且第 k+1 位上 的剩余个数为 min(n, y-t) 的状态转移而来。 为什么是 min(n, y-t) 呢？ 因为当 的个数超过 n 个时，超过的部分对我们的答案不影响，所以取最小值处理。 那么如何得到这个 y 的值呢？ 设 z 的当前位为 c，枚举 的个数 x，有 枚举 t 时，要注意遍历范围和增幅。 参考代码 1234567891011121314151617 ...

题目链接：codeforces 1631D 题解 越大，所选的区间长度越长，对应的分割后的个数越少，所以二分查找这个最小的差值。 那么怎么保证划分后的每个区间的在 内的个数大于在 外的个数？不妨反过来想，如果都保证了，那么所有的在 内的个数一定大于在 范围外的个数。所以我们可以在写 check 函数的时候，只要考虑这个区间的最大个数与此时区间外的个数之差是否大于等于 即可。 最后用贪心的方法去划分数组即可。 参考代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <bits/stdc++.h>using namespace std;const int maxn = 2e5 + 10;int a[maxn], b[maxn];int n, k;bool check(int x) { int num = 0; for (int i = 1; i + x <= n; i++) { ...

题目链接：codeforces 1631E 题解 如果数字之间不影响，那么直接考虑贪心，每次选最长的区间，然后中间的改为 。但是有可能中间的数字有可能是其他区间的端点。 考虑用动态规划来解决。首先某个数字最后出现的位置一定是区间的右端点，用一个数组 pos 记录某个数字最后出现的位置。定义 dp[i] 为前 i 个 的个数。为什么是 的个数而不是 的个数呢？因为填 的位置是端点，转移的时候用端点比较好写方程。 显然，第一个数一定是左端点，定义状态转移方程： 用一个指针 cur 记录右端点的最大值，让当前最大右端点 ，即 dp[cur]，其状态转移方程为： 每次转移的时候，如果当前数字 是左端点，那么 dp[cur] 会增加 ；如果 不是左端点，那么 dp[i] 不会更新，dp[cur] 也不会更新。最后答案就是 n-dp[n]。 参考代码 12345678910111213141516171819#incldue <bits/stdc++.h>using namespace std;const int maxn = 2e5 + 10;int a[maxn ...

题目链接：codeforces 1620E 题解 倒序遍历每次的操作，对于操作 ，相当于把 x 加入到代表元是 y 的集合。 参考代码 12345678910111213141516171819#include<iostream>using namespace std;const int N = 5e5 + 10;int a[N], x[N], y[N], fa[N];int main () { int q, n = 0; cin >> q; for (int i = 1; i <= q; i++) { int opt; cin >> opt >> x[i]; if (opt == 2) cin >> y[i]; } for (int i = 1; i <= 500000; i++) fa[i] = i; for (int i = q; i >= 1; i--) { if (!y[i]) a[++n] = fa[x[i]]; ...

题目链接：codeforces 1622C 题解 贪心思想，显然，用最小的数去替换数组中的数。 答案与顺序无关，不妨先从小到大排个序，假设替换了末 个数字，当前和为 。 比较好想的是，如果当前 ，则答案就是最小的 。如果 ，则需要先减少最小的数再去替换。具体做法是：先尝试替换后 个数，求的差值 ，然后最后的次数加上 即可。因为对于一个被替换的数，先替换它再减少所需要的操作数和先减少最小的数再去替换它所需要的操作数是相等的。于是可以用总的所需要的操作数平摊到 个数。 参考代码 123456789101112131415161718192021222324252627282930313233#include <iostream>#include <algorithm>using namespace std;typedef long long ll;const int N = 2e5 + 10;ll a[N], pre[N];ll n, k;int main() { int t; cin >> t; while (t--) { ...

题目链接：codeforces 1622D 题解 暴力枚举区间 ，每次考虑把边界上的 放在中间的方案数。用预处理的方法求组合数。 参考代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <iostream>#include <vector>#include <string>using namespace std;typedef long long ll;const int N =5000+10;const int mod = 998244353;ll n, k;string s;ll fac[N], inv_fac[N];ll a[N];ll qpow(ll a, ll b) { ll res = 1; a %= mod; while (b > 0) { if (b & 1) { ...

题目链接：codeforces 1627C 题解 给一颗树的边赋值，单条边的权值为质数，相邻两条边的权值和也为质数。 不难发现必然有一条边的权值是 ，与这条边相邻的边的权值是其他任意质数。所以，显然，如果存在可行解的的话，这颗树已经退化成一条链，即不可能有一个节点的度为 。 于是，只要找到这条链的一端，然后再去根据条件赋值即可。 参考代码 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <bits/stdc++.h>using namespace std;void solver(){ int n; cin >> n; vector<array<int, 2>> a[n+1]; for (int i = 1; i <= n-1; i++) { int u, v; cin >> u >> v; a[u].push_back({v, i} ...

题目链接：codeforces 1624F 题意 已知 ，猜数字 。 对于每次询问： + c：返回 。 题解 二分，每次加的 为到下一个 所需的值，然后再去判断这个整数 与返回的 的大小，每次搜索后，保证 是 的整数倍。 参考代码 12345678910111213141516171819202122#include <iostream>using namespace std;int main() { int n; cin >> n; int l = 1, r = n-1, mid; while (l < r) { mid = (l+r+1) >> 1; int c = n - mid % n, k = mid/n + 1; cout << "+ " << c << endl; int p; cin >> p; if (p >= k) { l = mid; ...

题目链接：codeforces 1625C 题解 定义 dp[i][j] 为终点为 ，选中 个点所需要的最少时间。状态转移方程： 其中 为 前 个中的任意节点。方程表示，每次选中的 个点是在 中，而不在 中，不断枚举更新，最后求的的答案是 dp[n+1][k]。 参考代码 123456789101112131415161718192021222324#include <iostream>#incldue <cstring>using namespace std;const int maxn = 550;int a[maxn], d[maxn], dp[maxn][maxn];int main() { int n, l, k; cin >> n >> l >> k; for (int i = 1; i <= n; i++) cin >> d[i]; d[n+1] = l; for (int i = 1; i <= n; i++) cin >> a ...