Codeforces Round 922 (Div. 2) 题解_codeforce平台div2的题目
赞
踩
C
给你整数 a a a 、 b b b 、 r r r 。求所有 0 ≤ x ≤ r 0 \leq x \leq r 0≤x≤r 中 ∣ ( a ⊕ x ) − ( b ⊕ x ) ∣ |({a \oplus x}) - ({b \oplus x})| ∣(a⊕x)−(b⊕x)∣ 的最小值。
⊕ \oplus ⊕ 是 bitwise XOR 的运算， ∣ y ∣ |y| ∣y∣ 是 y y y 的 absolute value。
思路
我们逐位考虑。
如果a和b的当前位相同，则没有影响。
如果a=1且b=0，那么我们如果选择1，那么后面一旦遇到a=1,b=0那么就设0，遇到a=0,b=1那么就设1
如果我们选择0，那么我们后面一旦遇到a=1,b=0那么就设为1，反之就设为0。
我们分别求出这两种的答案，取最小值即可。
现在我们考虑r的限制。那么在限制位（即r的最高位）之前（即更高位）我们都只能取0，然后在限制位特殊考虑后后面选用尽可能补回差距的方法。
代码
#include <bits/stdc++.h> #include <queue> #define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i) #define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i) using namespace std; // #define pb push_back #define mp make_pair #define int long long #define pii pair<int, int> #define ps second #define pf first #define X(j) i[j] #define Y(j) (dp[j] + (i[j] + L) * (i[j] + L)) #define rd read() int read() { int xx = 0, ff = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') ff = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar(); return xx * ff; } void write(int out) { if (out < 0) putchar('-'), out = -out; if (out > 9) write(out / 10); putchar(out % 10 + '0'); } const int N = 3e5 + 5; const int INF = 1e18; signed main(){ int t=rd; while(t--){ int a=rd,b=rd,r=rd; int x=0; int lim=1; if(a>b)swap(a,b); for(int i=59;~i;i--){ int pa=a&(1ll<<i); int pb=b&(1ll<<i); if(pa!=pb){ if(lim)lim=0; else{ if(!pa&&x+(1ll<<i)<=r){ x+=(1ll<<i);a^=(1ll<<i);b^=(1ll<<i); } } } } cout<<b-a<<endl; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
D
给你一个由数字 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an 组成的数组。你的任务是封锁数组中的一些元素，以最小化成本。假设你封锁了索引为 1 ≤ b 1 < b 2 < … < b m ≤ n 1 \leq b_1 < b_2 < \ldots < b_m \leq n 1≤b1<b2<…<bm≤n 的元素。那么数组的成本计算为以下各项的最大值：
-
阻塞元素的总和，即 a b 1 + a b 2 + … + a b m a_{b_1} + a_{b_2} + \ldots + a_{b_m} ab1+ab2+…+abm 。
-
移除阻塞元素后，数组被分割成的段的最大和。即以下（ m + 1 m + 1 m+1 ）子数组的最大和：[ 1 , b 1 − 1 1, b_1 − 1 1,b1−1 ]、[ b 1 + 1 , b 2 − 1 b_1 + 1, b_2 − 1 b1+1,b2−1 ]、[ … \ldots … ]、[ b m − 1 + 1 , b m − 1 b_{m−1} + 1, b_m - 1 bm−1+1,bm−1 ]、[ b m + 1 , n b_m + 1, n bm+1,n ]（形式为[ x , x − 1 x,x − 1 x,x−1 ]的子数组中的数字之和被认为是 0 0 0 ）。
例如，如果 n = 6 n = 6 n=6 ，原始数组是[ 1 , 4 , 5 , 3 , 3 , 2 1, 4, 5, 3, 3, 2 1,4,5,3,3,2 ]，而你屏蔽了位于 2 2 2 和 5 5 5 位置的元素，那么数组的代价将是被屏蔽元素之和（ 4 + 3 = 7 4 + 3 = 7 4+3=7 ）和子数组之和（ 1 1 1 ， 5 + 3 = 8 5 + 3 = 8 5+3=8 ， 2 2 2 ）的最大值，也就是 max ( 7 , 1 , 8 , 2 ) = 8 \max(7,1,8,2) = 8 max(7,1,8,2)=8 。
您需要输出阻塞后数组的最小代价。
思路
考虑dp
设f_i为封锁i个元素的最大和，然后我们从前往后考虑。转发现不少处理有关阻元素最大值的计算。
我们可以进行二分答案，假设我们二分一个答案为m，那么我们现在来判定m，这就很好做了。
设f_i为考虑到第i个元素，并且已经封锁了元素i时，且满足每一个区块的和≤m时的最小费用。
转移就很简单了
f_i=min(f_j)+a_i满足sum_{j+1\sim i-1}≤m，此时我们可以使用单调队列优化转移。
代码
注意：注意单调队列什么时候是pop_back，什么时候是pop_front。
list的使用方法。
#include <bits/stdc++.h> #include <queue> #define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i) #define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i) using namespace std; // #define pb push_back #define mp make_pair #define int int64_t #define pii pair<int, int> #define ps second #define pf first #define X(j) i[j] #define Y(j) (dp[j] + (i[j] + L) * (i[j] + L)) #define rd read() int read() { int xx = 0, ff = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') ff = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar(); return xx * ff; } void write(int out) { if (out < 0) putchar('-'), out = -out; if (out > 9) write(out / 10); putchar(out % 10 + '0'); } const int N = 3e5 + 5; const int INF = 1e18; int n, a[N], qz[N]; int f[N]; bool judge(int m) { // cerr<<"OK"<<endl; list<int> q; q.push_back(0); for (int i = 1; i <= n; i++) { while (q.size() && ((q.front() == 0) ? qz[i - 1] : qz[i - 1] - qz[q.front()]) > m) { // cerr << "POPP" << q.front() << "at" << i << endl; q.pop_front(); } int l; if (q.size()) l = q.front(); else { // l=0; return 0; } f[i] = f[l] + a[i]; // cerr<<i<<"f="<<f[i]<<" front()="<<q.front()<<endl; while (q.size() && f[q.back()] >= f[i]) { // cerr << "POBB" << q.front() << "at" << i << endl; q.pop_back(); } q.push_back(i); } // cout << m << endl; // for (int i = 1; i <= n; i++) // cout << f[i] << ' '; // cout << endl; // cerr << "find" << endl; int res = INF; for (int i = 1; i <= n; i++) if (qz[n] - qz[i] <= m) res = min(res, f[i]); return res <= m; } void solve() { n = rd; for (int i = 1; i <= n; i++) { a[i] = rd; qz[i] = qz[i - 1] + a[i]; } int ans = 0; int l = 0, r = INF; while (l <= r) { // cerr<<l<<' '<<r<<endl; int mid = l + r >> 1; if (judge(mid)) ans = mid, r = mid - 1; else l = mid + 1; } if (judge(ans - 1)) ans--; cout << ans << endl; // cout << judge(13); } signed main() { int T = rd; while (T--) { solve(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
E
这是一个互动问题！
在新一轮中，有 n n n 个任务，难度从 1 1 1 到 n n n 。协调人决定第一轮的任务不按难度顺序排列，于是重新排列了任务，结果出现了难度从 1 1 1 到 n n n 的排列。之后，协调人让王牌 5 以下列方式猜测排列顺序。
首先，协调人从 1 1 1 到 n n n 中选择一个数字 x x x 。
ace5 可以进行以下形式的查询： ? i ?\ i ? i .答案将是
-
> > > ，如果是 a i > x a_i > x ai>x ，之后 x x x 会增加 1 1 1 。
-
< < < ，如果是 a i < x a_i < x ai<x ，则 x x x 减少 1 1 1 。
-
= = = ，如果是 a i = x a_i = x ai=x ，之后 x x x 保持不变。
王牌 5 的任务是在不超过 40 n 40n 40n 次查询中猜出排列。由于王牌 5 忙于撰写公告，他把这项任务交给了你。
思路
互动就是构造！
随机解决方案： 我们将使用 quicksort 算法。我们将从数组中随机选择一个元素，让其索引为 i i i ，然后执行 ? ? ? i i i 直到得到答案 = = = （即 x = a i x = a_i x=ai ）。 i i i 直到得到答案 = = = （即 x = a i x = a_i x=ai ）。现在我们将询问所有其他元素，从而找出它们是大于还是小于 a i a_i ai （不要忘记返回 a i a_i ai ）。(不要忘记返回 x = a i x = a_i x=ai ，即执行 ? ? ? i i i i i i ）。之后，我们将把所有元素分为两部分，即 a i < x a_i < x ai<x 和 a i > x a_i >x ai>x 。我们将对每一部分递归运行算法。这些部分将变得越来越小，最后，我们将对排列进行排序，从而猜出排列结果。
非随机解法： 我们将通过 3 n 3n 3n 次查询找到数组中的元素 1 1 1 。为此，我们将遍历数组，每次询问每个元素。如果答案是 < < < ，我们将继续询问，直到答案变成 = = = ；如果答案是 = = = 或 > > > ，我们将继续询问下一个元素。那么答案为 = = = 的最后一个元素就是 1 1 1 。在这个过程中， x x x 最多会增加 n n n （每个元素最多会增加 1 1 1 ），因此最多会减少 2 n 2n 2n ，即最多查询 3 n 3n 3n 次。同样，我们将找到元素 n n n 。现在我们将运行与随机解类似的算法，但现在我们可以设置 x = n / 2 x = n/2 x=n/2 而不是将 x x x 作为随机元素。
这两种解决方案都能在 40 n 40n 40n 次查询的限制内轻松完成。
代码
#include <bits/stdc++.h> #include <queue> #define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i) #define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i) using namespace std; // #define pb push_back #define mp make_pair #define int int64_t #define pii pair<int, int> #define ps second #define pf first #define X(j) i[j] #define Y(j) (dp[j] + (i[j] + L) * (i[j] + L)) #define rd read() int read() { int xx = 0, ff = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') ff = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar(); return xx * ff; } void write(int out) { if (out < 0) putchar('-'), out = -out; if (out > 9) write(out / 10); putchar(out % 10 + '0'); } const int N = 3e5 + 5; const int INF = 1e18; mt19937 rnd(114514); char query(int i) { cout << "? " << i + 1 << endl; char c; cin >> c; return c; } void qsort(vector<int> &a, vector<int> &ord) { if (a.size() == 0) return; int mid = rnd() % a.size(); while (query(a[mid]) != '=') ; vector<int> l, r; for (int i = 0; i < a.size(); ++i) { if (i == mid) continue; if (query(a[i]) == '<') { l.push_back(a[i]); } else { r.push_back(a[i]); } query(a[mid]); } vector<int> lo, ro; qsort(l, lo); qsort(r, ro); for (int i = 0; i < lo.size(); ++i) { ord.push_back(lo[i]); } ord.push_back(a[mid]); for (int i = 0; i < ro.size(); ++i) { ord.push_back(ro[i]); } return; } signed main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a; vector<int> ord; for (int i = 0; i < n; ++i) { a.push_back(i); } qsort(a, ord); cout << "! "; vector<int> ans(n); for (int i = 0; i < n; ++i) { ans[ord[i]] = i; } for (int i = 0; i < n; ++i) { cout << ans[i] + 1 << ' '; } cout << endl; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
F
毛毛虫决定拜访树的每一个节点。一开始，它坐在树根上。
这棵树是一棵有根的树，树根位于节点 1 1 1 。毛虫每次爬行到邻近节点需要 1 1 1 分钟。
树下有一个蹦床。如果毛毛虫从树上脱落，掉到蹦床上，它将在 0 0 0 秒内到达树根。但是蹦床已经很旧了，只能承受毛毛虫 k k k 次的坠落。
毛毛虫访问树上所有节点的最短时间是多少？
更正式地说，如果毛毛虫从树根（节点 1 1 1 ）开始，用两种方法移动，我们需要找出访问树上所有节点所需的最短时间。
-
沿着一条边爬行到邻近的一个节点：需要 1 1 1 分钟。
-
传送到根：不耗时，不会访问新节点。
第二种方法（传送）最多可使用 k k k 次。毛毛虫可以在任意节点完成旅程。
思路
性质：要访问一个节点，就要把这个节点的子树一起访问掉。
现在我们考虑当这条路走到头时我们应该怎么办。先不考虑限制k。
当前节点为x，假设到最近的未访问节点u的距离≤u的距离，那么我们就选择爬过去。否则我们就选择传送到根。因此，如果知道访问树叶的顺序，就可以找到最佳时间。
那么我们怎么样确定我们访问子树的顺序呢？我们可以尝试把子树按子树中最深的点的深度排序，这样我们就可以先访问小的子树——为什么这样？这样可以贪心地让每当我们要走回头路时经过的距离的和最短。想一想，用数字表示子树最深的深度，那么是1 4 2更好还是1 2 4更好？
那么选择假设k=0，我们把每一次转移需要花费的步数w_{u,v}求出来，将w_{u,v}-dep_v排序，将最大的那k个用dep_v替代即可。
（下面是题解原话）
事实证明，如果将这棵树的每个节点的子节点按子树深度的升序(而不是降序)排序，然后从左到右(按深度优先顺序)写下所有树叶，那么这将是最佳树叶顺序之一。这种树和树叶的排序顺序被称为子树深度排序顺序。
G
你只得到了一个数字 n n n 。你对这个数似乎并不感兴趣，于是想知道是否有可能想出一个长度为 n n n 的数组，由非零整数组成，这样，如果数组中的每个元素都被其相邻元素的和所替换（两端的元素被其唯一的相邻元素所替换），你就得到了原数组中数字的排列组合。
思路
就是我们要构造一个长度为n的序列s，经过题目中的变换后变成t，使得t是s的一个排列。
构造题。时间复杂度要求O(n)。
解法由 green_gold_dog提供：
我们的想法是，任何正确的数组都可以通过 2 2 2 个元素来保持正确性。让数组以数字 a a a 和 b b b 结尾。那么它可以扩展两个元素，如下所示：
KaTeX parse error: {equation*} can be used only in display mode.
这个数组将转变为其排列方式：除了 a a a 之外，整个旧数组都由旧数组生成；最后三个单元格生成 a − b a-b a−b 、 a a a 、 − b -b −b ，即两个新元素，以及缺失的元素 a a a 。新元素必须为非零。如果旧数组的最后两个元素不同，那么新元素也非零；此外，新元素不可能相同，因为 a a a 和 b b b 都非零，所以这个操作可以重复多次。
首先，有两个数组就足够了： [ 1 , 2 ] [1, 2] [1,2] 对应 n = 2 n = 2 n=2 ， [ 1 , 2 , − 3 , 2 , 4 , − 5 , − 2 ] [1, 2, -3, 2, 4, -5, -2] [1,2,−3,2,4,−5,−2] 对应 n = 7 n = 7 n=7 。然后可以通过 2 2 2 扩展这些数组，得到偶数或奇数 n n n 的答案。
如果是奇数长度，则在[1, 2, -3, 2, 4, -5, -2]基础上按上面的方法不断生成。否则在[1,2]的基础上不断生成即可。
可以发现上面的生成方法是合法的且可持续的。
代码
#include <bits/stdc++.h> #include <queue> #include <iostream> #define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i) #define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i) using namespace std; // #define pb push_back #define mp make_pair #define int int64_t #define pii pair<int, int> #define ps second #define pf first #define X(j) i[j] #define Y(j) (dp[j] + (i[j] + L) * (i[j] + L)) #define rd read() int read() { int xx = 0, ff = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') ff = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar(); return xx * ff; } void write(int out) { if (out < 0) putchar('-'), out = -out; if (out > 9) write(out / 10); putchar(out % 10 + '0'); } const int N = 3e5 + 5; const int INF = 1e18; int n; signed main(){ n=rd; if(n==3||n==5){ cout<<"NO"<<endl; return 0; } cout<<"YES"<<endl; if(n%2==0){ n-=2; cout<<"1 2 "; int a=1,b=2; while(n){ cout<<-b<<' '<<a-b<<' '; int ta=a,tb=b; a=-tb;b=ta-tb; n-=2; } }else{ cout<<"1 2 -3 2 4 -5 -2 "; n-=7; int a=-5,b=-2; while(n){ cout<<-b<<' '<<a-b<<' '; int ta=a,tb=b; a=-tb;b=ta-tb; n-=2; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
