杂文|Codeforces Round #757 (Div. 2) 题解贪心|数学|值域线段树|杂文

Codeforces Round #757 (Div. 2) 题解 A：Divan and a Store 题目大意
给你若干个数，然后你要选若干个数，每个数都在 l~r 之间，你要在尽可能选多的数的同时保证所有你选的数的和不超过一个值。
思路
就直接贪心，把可以选的数拿出来排个序，从小到大能选就选即可。
代码

#include #include #include #include #include #include #include #include #define ll long longusing namespace std; int T, now, ans, x; int n, l, r, k, a[101]; int main() { scanf("%d", &T); while (T--) { scanf("%d %d %d %d", &n, &l, &r, &k); a[0] = 0; now = 0; ans = 0; for (int i = 1; i <= n; i++) { scanf("%d", &x); if (l <= x && x <= r) a[++a[0]] = x; } sort(a + 1, a + a[0] + 1); for (int i = 1; i <= a[0]; i++) { now += a[i]; ans++; if (now > k) { now -= a[i]; ans--; break; } } printf("%d\n", ans); } return 0; }

B：Divan and a New Project 题目大意
给你一个直线，然后起点在 0 位置，然后有 n 个地方可以让你选放在这个直线的 n 个地方（1~n 位置），然后每个地方要有去的次数。
每次去这个地方的费用是2 ∣ x 0 ? x i ∣ 2|x0-xi| 2∣x0?xi∣（就是两个地方的距离差乘二），然后要你最小化费用并给出放置方案。
思路
显然又是一个贪心，就尽可能的把要去次数多的放的靠近 0 位置即可。
（也是一个排序的事情）
代码

#include #include #include #include #include #include #include #include #define ll long longusing namespace std; struct node { int x, id; }a[200001]; int T; int n, ans[200001]; ll answ, bas; bool cmp(node x, node y) { return x.x < y.x; }int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i].x), a[i].id = i; sort(a + 1, a + n + 1, cmp); answ = 0; bas = 1; bool op = 0; ans[0] = 0; for (int i = n; i >= 1; i--) { ans[a[i].id] = bas; if (op) ans[a[i].id] = -bas; answ += 2ll * a[i].x * bas; if (op == 0) op = 1; else { bas++; op = 0; } } printf("%lld\n", answ); for (int i = 0; i <= n; i++) printf("%d ", ans[i]); printf("\n"); } return 0; }

C：Divan and bitwise operations 题目大意
要你构造一个长为为 n 的数组，然后有一些限制条件：某一段区间的数与起来的结果是某个数。
然后要你输出你构造出的数组的权值，定义这个权值是它所有子序列的异或和的和。
然后多种构造方法输出任意一个的答案即可。
思路
考虑把构造和计算权值分开。
给出一种简单的构造方法：
首先二进制拆分，然后一开始默认全部都是1 1 1，然后如果有一个限制条件要求某一段区间是0 0 0，那就把他们都标记为0 0 0。（这个可以用差分标记）
然后接着计算权值当然也是对于二进制每一位算贡献。
那我们就可以枚举子序列有多少个这一位是 1 的，那就只有奇数个数的会被统计。
那我们考虑如何统计。（ s 0 s0 s0 是这一位是0 0 0 的个数， s 1 s1 s1 是这一位是1 1 1 的个数）
首先是如果是这一位是0 0 0 的就随便，直接2 s 0 2^{s0} 2s0，接下来就看是1 1 1 的。
（好像直接组合数( s 1 i ) \binom{s1}{i} (is1?) 也可以，但我当时以为会超时）
然后我比赛的时候就想了个递推的，就直接设f i , 0 / 1 f_{i,0/1} fi,0/1? 为当前到第i i i 个，然后当前的异或值是0 / 1 0/1 0/1 的方案数。
代码

#include #include #include #include #include #include #include #include #define ll long long #define mo 1000000007using namespace std; struct node { int l, r, x; }a[200001]; int TT, n, m, num[31]; ll jc[200001], inv[200001]; ll F[200001][2]; int b[31][200002]; ll ksm(ll x, ll y) { ll re = 1; while (y) { if (y & 1) re = re * x % mo; x = x * x % mo; y >>= 1; } return re; }ll C(ll n, ll m) { return jc[n] * inv[m] % mo * inv[n - m] % mo; }int main() { jc[0] = 1; for (int i = 1; i <= 200000; i++) jc[i] = jc[i - 1] * i % mo; inv[200000] = ksm(jc[200000], mo - 2); for (int i = 200000 - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mo; scanf("%d", &TT); while (TT--) { scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &a[i].l, &a[i].r, &a[i].x); for (int j = 0; j <= 30; j++) { if (!((a[i].x >> j) & 1)) {//差分 b[j][a[i].l]++; b[j][a[i].r + 1]--; } } }F[0][0] = 1; for (int i = 1; i <= n; i++) { F[i][1] = (F[i - 1][1] + F[i - 1][0]) % mo; F[i][0] = (F[i - 1][0] + F[i - 1][1]) % mo; }ll ans = 0; //计数 for (int i = 0; i < 30; i++) { int num1 = 0; for (int j = 1; j <= n; j++) { b[i][j] += b[i][j - 1]; if (!b[i][j]) num1++; } int num0 = n - num1; ans = (ans + 1ll * (1 << i) * ksm(2, num0) % mo * F[num1][1] % mo) % mo; } printf("%lld\n", ans); for (int i = 0; i <= 30; i++) for (int j = 1; j <= n + 1; j++) b[i][j] = 0; } return 0; }

D1：Divan and Kostomuksha (easy version) 题目大意
给你一个数组，然后你要重新排列它们，使得：
∑ i = 1 n gcd ? ( a 1 , a 2 , . . . a i ) \sum\limits_{i=1}^n\gcd(a_1,a_2,...a_i) i=1∑n?gcd(a1?,a2?,...ai?) 这个值最大，输出这个值。
思路
首先看到你从i = 1 ～ n i=1\sim n i=1～n，它每次贡献的值是不会变大，只会不变或者变小，而且每次变小都会变成它的因子。
那我们考虑反过来这个过程，从1 1 1 不断变大。（那你就算最后不是到1 1 1 你也可以相当于没有值参与到变1 1 1 的过程，贡献可以直接抵消掉）
不难想到我们可以用一个记忆化搜索：
d f s ( x ) dfs(x) dfs(x) 为当前gcd ? \gcd gcd 为x x x，之后能有的贡献。
首先你算当前能有的所有数都用x x x 来贡献。
（那我们也就是要处理出每个数有多少个数是它的倍数，这个不难处理，每个数用质数遍历因子加即可）
那你就枚举下一次变成的倍数。
那如果当前有的数是n x nx nx，当前枚举到的倍数是y y y，这个y y y 有n y ny ny 个数是它的倍数。
那我们首先要减去这n y ny ny 个x x x 个贡献，再加上d f s ( y ) dfs(y) dfs(y) 的结果，我们要最大化这个部分。
然后就可以了。
代码

#include #include #include #include #include #include #include #include #define ll long longusing namespace std; int n, a[100001]; int pl[5000001]; int np[5000001], prime[5000001]; int cnt[10001], cntpl[10001]; ll num[5000001], rem[5000001]; void yz(int now, int va, int xx) { if (now > cntpl[0]) { num[va] += xx; return ; } yz(now + 1, va, xx); for (int i = 1; i <= cnt[now]; i++) { va *= cntpl[now]; yz(now + 1, va, xx); } }ll dfs(int now) { if (rem[now]) return rem[now]; ll re = 0; for (int i = now + now; i <= 5000000; i += now) { if (!num[i]) continue; re = max(re, dfs(i) - num[i] * now); } return rem[now] = (re + num[now] * now); }int main() { for (int i = 2; i <= 5000000; i++) { if (!np[i]) { prime[++prime[0]] = i; pl[i] = prime[0]; } for (int j = 1; j <= prime[0] && i * prime[j] <= 5000000; j++) { np[i * prime[j]] = prime[j]; if (i % prime[j] == 0) break; } } scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sort(a + 1, a + n + 1); for (int l = 1; l <= n; l++) { int r = l; while (r < n && a[r + 1] == a[l]) r++; int noww = a[l]; cntpl[0] = 0; while (noww) { if (noww == 1) break; cnt[++cntpl[0]] = 0; cntpl[cntpl[0]] = (np[noww] ? np[noww] : noww); while (noww % cntpl[cntpl[0]] == 0) { noww /= cntpl[cntpl[0]]; cnt[cntpl[0]]++; } } yz(1, 1, r - l + 1); l = r; } printf("%lld\n", dfs(1)); return 0; }

D2：Divan and Kostomuksha (hard version) 题目大意
同 D1，但是每个数的大小更大，不能用O ( V log ? V ) O(V\log V) O(VlogV) 的复杂度解决。（ V V V 是数的最大值）
思路
考虑会超时的部分，发现是你d f s dfs dfs 里面枚举倍数不行，别的地方都可以。
考虑改进。
会发现你乘一个z z z 的倍数，如果z = x ? y z=x*y z=x?y，你完全可以先走到x x x 倍，再走到x ? y x*y x?y 倍。
那你就只需要枚举它乘上每个质数，就可以了。
复杂度就降到了O ( V log ? log ? V ) O(V\log\log V) O(VloglogV)。
代码

#include #include #include #include #include #include #include #include #define ll long longusing namespace std; int n, a[100001]; int pl[20000001]; int np[20000001], prime[20000001]; int cnt[100001], cntpl[100001]; ll num[20000001], rem[20000001]; void yz(int now, int va, int xx) { if (now > cntpl[0]) { num[va] += xx; return ; } yz(now + 1, va, xx); for (int i = 1; i <= cnt[now]; i++) { va *= cntpl[now]; yz(now + 1, va, xx); } }ll dfs(int now) { if (rem[now]) return rem[now]; ll re = 0; for (int i = 1; i <= prime[0] && 1ll * now * prime[i] <= 20000000; i++) { if (!num[now * prime[i]]) continue; re = max(re, dfs(now * prime[i]) - num[now * prime[i]] * now); } return rem[now] = (re + num[now] * now); }int main() { for (int i = 2; i <= 20000000; i++) { if (!np[i]) { prime[++prime[0]] = i; pl[i] = prime[0]; } for (int j = 1; j <= prime[0] && i * prime[j] <= 20000000; j++) { np[i * prime[j]] = prime[j]; if (i % prime[j] == 0) break; } } scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sort(a + 1, a + n + 1); for (int l = 1; l <= n; l++) { int r = l; while (r < n && a[r + 1] == a[l]) r++; int noww = a[l]; cntpl[0] = 0; while (noww) { if (noww == 1) break; cnt[++cntpl[0]] = 0; cntpl[cntpl[0]] = (np[noww] ? np[noww] : noww); while (noww % cntpl[cntpl[0]] == 0) { noww /= cntpl[cntpl[0]]; cnt[cntpl[0]]++; } } yz(1, 1, r - l + 1); l = r; } printf("%lld\n", dfs(1)); return 0; }

E：Divan and a Cottage 题目大意
给你一个序列，然后对于这个序列的每个前缀，有一些询问，询问给你一个初始数字，然后被这个前缀操作后的结果是什么。
操作是你依次看这个数组的每个位置，如果当前的数字小于它这个位置的值，就把当前的数字加一，如果是大于就减一，如果等于就不变。
强制在线。
思路
首先可以发现一个性质：
对于初始数字x < y x 那你考虑每次操作数组多了一点会怎么样，假设新的是x x x。
那左边一段前缀（考虑把每个初始数组的答案弄成一个数组）的答案就加一，后面一段后缀的答案就减一。
【杂文|Codeforces Round #757 (Div. 2) 题解】然后由于这个数组长度1 e 9 1e9 1e9，我们考虑用值域线段树来搞（就动态开点）。
然后你维护一下数组最大值就可以搞了。
代码

#include #include #define ll long longusing namespace std; int n, a[200001], q; int x, lstans, rt; struct XD_tree { int val_max[400001 << 7]; int ls[400001 << 7], rs[400001 << 7]; int lzy[400001 << 7], tot; void up(int now) { val_max[now] = max(val_max[rs[now]], val_max[ls[now]]); } void down(int now, int l, int r) { int mid = (l + r) >> 1; if (!ls[now]) { ls[now] = ++tot; val_max[ls[now]] = mid; } if (!rs[now]) { rs[now] = ++tot; val_max[rs[now]] = r; } if (!lzy[now]) return ; val_max[ls[now]] += lzy[now]; val_max[rs[now]] += lzy[now]; lzy[ls[now]] += lzy[now]; lzy[rs[now]] += lzy[now]; lzy[now] = 0; } int query(int now, int l, int r, int pl) { if (l == r) return val_max[now]; down(now, l, r); int mid = (l + r) >> 1; if (pl <= mid) return query(ls[now], l, mid, pl); else return query(rs[now], mid + 1, r, pl); } void insert(int &now, int l, int r, int L, int R, int va) { if (L > R) return ; if (!now) { now = ++tot; val_max[now] = r; } if (L <= l && r <= R) { lzy[now] += va; val_max[now] += va; return ; } down(now, l, r); int mid = (l + r) >> 1; if (L <= mid) insert(ls[now], l, mid, L, R, va); if (mid < R) insert(rs[now], mid + 1, r, L, R, va); up(now); } int query_l(int now, int l, int r, int pl) { if (l == r) return l; down(now, l, r); int mid = (l + r) >> 1; if (val_max[ls[now]] >= pl) return query_l(ls[now], l, mid, pl); else return query_l(rs[now], mid + 1, r, pl); } }T; int main() { T.insert(rt, 0, 1e9, 0, 1e9, 0); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); int maxn = T.query(rt, 0, 1e9, 1e9); int pl = T.query_l(rt, 0, 1e9, a[i] + 1); //printf("%d \n", maxn); if (maxn > a[i]) T.insert(rt, 0, 1e9, pl, 1e9, -1), maxn--; if (T.query(rt, 0, 1e9, 0) < a[i]) { int pl; if (a[i] > maxn) pl = 1e9; else pl = T.query_l(rt, 0, 1e9, a[i]) - 1; //printf("%d\n", pl); T.insert(rt, 0, 1e9, 0, pl, 1); }scanf("%d", &q); while (q--) { scanf("%d", &x); x = (x + lstans) % 1000000001; lstans = T.query(rt, 0, 1e9, x); printf("%d\n", lstans); } } return 0; }