每个题目的代码部分只给出了一组数据的解题流程。请注意，Codeforces上都是多组数据的。
代码中的il均表示long long类型。
Problem A. Escalator Conversations 题意 有$n$个人，$m$级台阶,每节台阶的高是$k$，给出每个人的身高$h_i$，以及自己的身高$H$。其中某人能与另一人对话的条件是他们的身高差等于一级或多级台阶的高度差。现在问$n$个人中有几人能和自己对话，可行性相互独立。
题解 注意对话两人不能站在同一级台阶上。能对话的条件是两人身高差的绝对值能被$k$整除，并且大于$0$，小于$k\cdot m$
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void solve () int n, m ,k, H; cin >> n >> m >> k >> H; vector<int > h (n) ; for (auto &v : h) { cin >> v; } int ans = 0 ;; for (auto v : h) { if (abs (v - H) % k == 0 && abs (v - H) / k < m && v != H) { ans ++; } } cout << ans << '\n' ; }
Problem B. Parity Sort 题意 有一个长度为$n$的数组，你只能交换数组中数值奇偶性相同的数字的位置，问是否能够使得整个数组是有序的。
题解 奇数只能和奇数交换位置，偶数只能和偶数交换位置。因此，通过上述操作，排序后原来是奇数的位置必然还是奇数，原来是偶数的位置必然还是偶数。我们进行一次正常的排序，如果某个位置的数值的奇偶性发生变化，那么必然不可能通过这种方式排序成功。反之，则一定可以成功。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int a[200100 ], b[200100 ];void solve () int n; cin >> n; for (int i = 0 ;i < n;i++) { cin >> a[i]; b[i] = a[i]; } sort (b, b + n); for (int i = 0 ;i < n;i++) { if (a[i] % 2 != b[i] % 2 ) { cout << "No\n" ; return ; } } cout << "Yes\n" ; }
Problem C. Tiles Comeback 题意 有$n$块地砖从左到右排成一条直线，每个地砖上有一个数字$c_i$。你可以向右跳任意多个地砖。现在问是否存在一种走法，起点为$1$号地砖，终点为$n$号地砖，使得走法按顺序中经过的地砖上的数字$c_i$能够分为一个或多个长度为$k$的段，使得每个段内的数字相同，且段之间没有相互重叠部分，相邻的段内的数字可以是相同的。
例如$k=3$时，经过的地砖颜色依次为$[1,1,1,2,2,2]$，$[1,1,1,1,1,1]$或$[1,1,1]$都是符合要求的。但是$[1,1,1,2,2]$，$[1,1,1,1,1]$都是不符合要求的。
题解 因为我们可以向右跳任意个地砖，而且问的是存在性，而非数目，我们只需要考虑起点和终点的数字$c_1$和$c_n$
代码 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 void solve () int n, k; cin >> n >> k; vector<int > c (n) ; for (auto &x : c) { cin >> x; } if (c[0 ] == c[n - 1 ]) { int cnt = 0 ; for (int i = 0 ;i < n;i++) { if (c[i] == c[0 ]) { cnt ++; } } cout << (cnt >= k ? "Yes\n" : "No\n" ); return ; } int target = c[0 ], cnt = 0 , idx = -1 ; for (int i = 0 ;i < n;i++) { if (c[i] == target) { cnt ++; if (cnt == k) { idx = i; break ; } } } target = c[n - 1 ], cnt = 0 ; int idx2 = -1 ; for (int i = n - 1 ;i >= 0 ;i--) { if (c[i] == target) { cnt ++; if (cnt == k) { idx2 = i; break ; } } } cout << ((idx != -1 && idx2 != -1 && idx < idx2) ? "Yes" : "No" ) << '\n' ; }
Problem D. Prefix Permutation Sums 题意 有一个长度为$n$的前缀和数组，但是其中的一个值（你不知道它的具体位置）在抄送中丢失了。按顺序给出剩下的$n-1$个数，问恢复这个丢失的值之后，这个前缀和数组是否有可能是由一个长度为$n$的排列产生的。
题解 由损坏的前缀和数组我们可以得到$n-1$个数，可以对这$n-1$个数进行分析
丢失的情况有两种：
不是在结尾处丢失了一个值：
那么这$n-1$个数中，必然有一个数$K$表示两数之和，剩下的$n-2$个数各不相同，且都小于等于$n$。并且$K$就等于缺失的两个数之和。注意找到$K$有两种情况，一种是在$[1,n]$区间内，但与该位置之前的某个数相同；另一种则是大于$n$。无论如何，这样的$K$只能出现一次，否则就不可能恢复成$n$的排列。
在结尾处丢失了一个值：
我们不能通过上面的方法找到$K$，并且$n-1$个数各不相同且都小于等于$n$，此时可以确定最后一个缺失的值。
代码 写的略复杂了2333
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 il a[200100 ]; void solve () int n; cin >> n; for (int i = 1 ;i <= n - 1 ;i++) { cin >> a[i]; } bitset<200100> st; il type = -1 , outbound; for (il i = 1 ;i <= n - 1 ;i++) { il delta = a[i] - a[i - 1 ]; if (delta > n) { if (type == -1 ) { type = 0 ; outbound = delta; } else { cout << "No\n" ; return ; } } else { if (st[delta]) { if (type == -1 ) { type = 2 ; outbound = delta; } else { cout << "No\n" ; return ; } } else { st[delta] = true ; } } } vector<il> absent; for (il i = 1 ;i <= n;i++) { if (!st[i]) { absent.push_back (i); } } il sum = 0 ; for (auto x : absent) { sum += x; } if ((type != -1 && sum == outbound && absent.size () == 2 ) || (type == -1 && absent.size () == 1 )) { cout << "Yes\n" ; } else { cout << "No\n" ; } }
Problem E. Nastya and Potions 题意 有$n$种药剂，第$i$种可以用$c_i$枚硬币购买，也可以通过$m_i$种药剂（各一份）合成。现在你有$k$种药剂编号分别为$p_1,p_2\dots,p_n$是无限免费供应的。分别求获得第$i$种药剂的最小代价（硬币消耗数）。注意，如果$m_i=0$，说明该药剂不能被合成。
题解 直接记忆化搜索即可，记录每种药剂的最小代价。每种药剂至多被计算一次，每条边也至多被访问一次（总共$\sum\limits_{i=1}^nm_i$条）
一个药剂的最小代价的计算方式：
如果该药剂免费，则直接返回0
否则，如果可以合成，则计算合成材料的代价总和，与直接购买价格比较，选取较小者。如果不能合成，则为直接购买价格。
记录计算结果（注意不能以价格为0为依据判断是否已经计算过，否则可能导致TLE）
代码 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 array<vector<int >, 200100> e; int cost[200100 ];il fee[200100 ]; bool computed[200100 ];il determine (int typ) { if (cost[typ] == 0 ) { return 0 ; } if (computed[typ]) { return fee[typ]; } if (e[typ].empty ()) { computed[typ] = 1 ; return fee[typ] = cost[typ]; } il ans = 0 ; for (const auto &item: e[typ]) { ans += determine (item); } ans = min ((il)cost[typ], ans); fee[typ] = ans; computed[typ] = 1 ; return ans; } void solve () int n, k, v; cin >> n >> k; for (int i = 1 ;i <= n;i++) { cin >> cost[i]; fee[i] = 0 ; computed[i] = 0 ; } for (int i = 1 ;i <= k;i++) { cin >> v; cost[v] = 0 ; } for (int i = 1 ;i <= n;i++) { e[i].clear (); int m; cin >> m; for (int j = 0 ;j < m;j++) { cin >> v; e[i].push_back (v); } } for (int i = 1 ;i <= n;i++) { cout << determine (i) << ' ' ; } cout << '\n' ; }
Problem F. Lisa and the Martians 题意 有$n$个数$a_1,a_2,\dots,a_n$，他们在二进制下的长度不超过$k$，即严格小于$2^k$。现在请你选择$i,j,x$来最大化$(a_i\oplus x)\&(a_j\oplus x)$的值，其中$i\ne j,1\le i,j\le n,0\le x\lt 2^k$。
题解 要最大化该表达式的值，我们先从二进制的某一位的情况下手，不妨让$k=1$，暴力枚举$a_i,a_j,x$分别为$0,1$的情况。运行如下代码：
1 2 3 4 5 6 7 8 int limit = 2 ;for (int i = 0 ; i < limit; ++i) { for (int j = 0 ; j < limit; ++j) { for (int x = 0 ; x < limit; ++x) { printf ("(%d^%d)&(%d^%d)=%d\n" , i, x, j, x, (i^x)&(j^x)); } } }
得到输出：
1 2 3 4 5 6 7 8 (0^0)&(0^0)=0 (0^1)&(0^1)=1 (0^0)&(1^0)=0 (0^1)&(1^1)=0 (1^0)&(0^0)=0 (1^1)&(0^1)=0 (1^0)&(1^0)=1 (1^1)&(1^1)=0
我们看到，只有两种情况下能够使得一个位上产生$1$的结果，即$a_i$和$a_j$的这一二进制位上的数相同，且$x$的该二进制位上取与$a_i,a_j$该位上相反的数时。
我们可以用与“最大异或和”类似的思想，使用01-trie解决这个问题。区别在于“最大异或和”问题是让高位尽量相反，而本题是尽量使得高位相同。这样我们可以在$O(k\cdot n)$的时间复杂度内解决本题。
设当前的答案$ans=-1$
01-trie按顺序地处理每一个数$a_i$：
首先在01-trie中查询，查询的方法是，如果有与当前位相同的后继节点，就移动到这个节点，否则移动到另一个节点（每个节点的直接后继只有两个）。最后返回节点上记录的索引值，构造对应的$x$，看是否需要更新答案。
然后将当前数$a_i$插入01-trie中，末端节点记录当前数的索引$i$
代码 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 int a[200100 ];struct TrieNode { int next[2 ] = {}; int data = 0 ; TrieNode () { next[0 ] = next[1 ] = 0 ; data = 0 ; } }; struct Trie { vector<TrieNode> p; int k, alloc = 0 ; explicit Trie (int len) : k(len) { p.emplace_back (); } void insert (int x, int idx) int id = 0 ; for (int i = k - 1 ;i >= 0 ;i--) { int v = (x & (1 << i)) != 0 ; if (p[id].next[v] == 0 ) { p.emplace_back (); p[id].next[v] = ((int )p.size ()) - 1 ; } id = p[id].next[v]; } p[id].data = idx; } int query (int x) int id = 0 ; for (int i = k - 1 ;i >= 0 ;i--) { int bit = (x & (1 << i)) != 0 ; int preferred = bit; if (p[id].next[preferred] != 0 ) { id = p[id].next[preferred]; } else { id = p[id].next[preferred ^ 1 ]; } } return p[id].data; } }; void solve () int n, k; cin >> n >> k; Trie trie (k) ; int ai = -1 , aj = -1 , ax = -1 , ans = -1 ; for (int i = 1 ;i <= n;i++) { cin >> a[i]; if (i != 1 ) { int j = trie.query (a[i]); int x = 0 ; for (int v = k - 1 ; v >= 0 ; v--) { int mask = 1 << v; int curr = 0 ; if ((a[i] & mask) == (a[j] & mask)) { curr = (a[i] & mask) == 0 ; } x = x * 2 + curr; } int nans = (a[i] ^ x) & (a[j] ^ x); if (nans > ans) { ans = nans; ai = i, aj = j, ax = x; } } trie.insert (a[i], i); } cout << min (ai, aj) << ' ' << max (aj, ai) << ' ' << ax << '\n' ; }
求解$x$的另一种方法 上面的代码中，求$x$的代码略显繁琐，其实还有更简便的位运算方法，具体代码如下：
1 2 int nans = (~(a[i] ^ a[j])) & ((1 << k) - 1 );int x = (a[i] ^ nans) & (a[j] ^ nans);
首先$nans$一句直接求出了$a_i,a_j$情况下最大化的答案：异或取反，相同的位上就是$1$，而再和$mask=(1<<k)-1$做或运算，就是限制$k$位下的最大值。
而下面的$x$一句，将两数分别和$nans$做异或运算，将答案位上的$0,1$颠倒，再做与运算，还原出了$x$。
另一种解法 异或最小的两个数总是排序后相邻的某两个数。该性质的证明参见AtCoder Beginner Contest 308 G的官方题解 。因此可以排序后$以O(n\cdot log(n))$的时间复杂度通过本题。
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 struct Value { int v; int idx; } a[200100 ]; void solve () int n, k; cin >> n >> k; int ai = -1 , aj = -1 , ax = -1 , ans = -1 ; for (int i = 1 ;i <= n;i++) { cin >> a[i].v; a[i].idx = i; } std::sort (a + 1 , a + n + 1 , [](auto &lhs, auto &rhs) { return lhs.v < rhs.v; }); for (int i = 1 ;i < n;i++) { int j = i + 1 ; int nans = (~(a[i].v ^ a[j].v)) & ((1ll << (il)k) - 1 ); int x = (a[i].v ^ nans) & (a[j].v ^ nans); if (nans > ans) { ans = nans; ai = a[i].idx, aj = a[j].idx, ax = x; } } cout << min (ai, aj) << ' ' << max (aj, ai) << ' ' << ax << '\n' ; }
Problem G. Vlad and the Mountains 题意 有$n$座山，每座山有一个高度$h_i$，从第$i$座山到第$j$座山需要消耗的能量为$h_j-h_i$。注意这个能量是可正可负的，也就是说，到更低的山头，就会恢复能量。
现在有$q$个询问，每个询问给出$a,b,e$三个数，其中$a$是当前所在的山头，$b$是目标山头，$e$是当前剩余的能量，请你判断是否能到达$b$山头。
题解 我们可以发现，只要给定$a,e$，那么我们能达到的最大高度就是确定的，为$h_a+e$。如果把边的权值定为$E=max(h_u,h_v)$，如果当前能达到的最大高度为$K$，我们就可以走$E\le K$的边，使得这些边的起点和终点联通，这可以用并查集维护。所以我们可以离线处理询问，最后输出答案。
读入所有边和所有询问，将边按权值$E$从小到大排序，将询问按照能达到的最大高度$K$排序。
定一个指针$ptr$指向下一个应该被加入的边，初始指向排序后的第一个位置，逐个处理询问，每次处理时，总是尝试将指针$ptr$向后移动，将权值小于当前最大高度的边加入，并更新并查集中的连通性。然后，检查$a$和$b$是否在同一个连通块，这就是我们需要的答案。
最后，按照询问的顺序输出答案即可。
代码 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 struct Query { int index; int a, b, e; il comp; bool ans; int operator <(const Query &rhs) const { return comp < rhs.comp; } } queries[200100 ]; int pos[200100 ];struct Edge { int u, v; int k; int operator <(const Edge &rhs) const { return k < rhs.k; } } edges[200100 ]; int h[200100 ];int fa[200100 ];int Find (int a) return fa[a] == a ? a : (fa[a] = Find (fa[a])); } void Merge (int a, int b) a = Find (a), b = Find (b); fa[a] = b; } void solve () int n, m, u, v, q; cin >> n >> m; for (int i = 1 ;i <= n;i++) { cin >> h[i]; fa[i] = i; } for (int i = 0 ;i < m;i++) { cin >> u >> v; edges[i] = {u, v, max (h[u], h[v])}; } cin >> q; for (int i = 0 ;i < q;i++) { cin >> queries[i].a >> queries[i].b >> queries[i].e; queries[i].index = i; queries[i].comp = (il)h[queries[i].a] + queries[i].e; } sort (edges, edges + m); sort (queries, queries + q); int ptr = 0 ; for (int i = 0 ;i < q;i++) { while (ptr < m && edges[ptr].k <= queries[i].comp) { Merge (edges[ptr].u, edges[ptr].v); ptr ++; } pos[queries[i].index] = i; queries[i].ans = Find (queries[i].a) == Find (queries[i].b); } for (int i = 0 ; i < q; ++i) { cout << (queries[pos[i]].ans ? "Yes" : "No" ) << '\n' ; } }
