VP: Codeforces Round #746 (Div. 2) (CF746)
官方题解：SolutionA简要题意你有 $n$ 种武器，每种武器使用一次可以造成 $a_i$ 的伤害，并且同一种武器不能连续用两次（但是可以重复使用）。现在有一个 HP 为 $H$ 的遗迹守卫，问你最少多少次A掉它。题解确实是我傻逼，题看错了 WA 了三发，好在是 VP。我们肯定会交替使用伤害最高的两种武器，伤害分别为 $x, y$。假设一个操作回合我们用这两种武器，那么一共会造成 $x+y$ 的伤害。假如 $H \equiv 0 \mod {(x+y)}$，那么答案就是 $ans = 2 \times \frac{H}{x+y}$。如果不整除，只需要讨论余数在 $x$ 内还是外，分别对应 $+1$ 和 $+2$。虽然是一道简单题，但还是要认真总结。因为看错了题，而且切的太慢了。B简要题意给你一个数组，你需要将其升序排序。但是对于第 $i$ 个数，你只能交换 $j \in [i + x, n]$ 中的数。问是否存在合法方案。题解可能是个牛逼题，我看见 zqy 秒掉了这个题，duang 28min 才切，iodwad 直接没切。不知道是为什么。我也吃了三发罚时（我是垃圾首先 $n \geq 2 \cdot x$ 的肯定有解，相当于没有这个限制，每个数都可以先跳到一个 $ > i+x$ 的地方再跳回一个 $ \leq i + x$ 的地方。否则的话，只有头 $n-x$ 个数和尾 $n-x$ 个数可以互换位置。那么只需要判断中间的那些数是不是跟有序的数组一样就行了。智慧树上智慧果，智慧树下你和我。C简要题意给一棵 $n$ 个点的树，现在你可以割至少 $1$ 条、至多 $k-1$ 条边，要求割了边之后形成的各个连通块内的点的异或和相等。问是否存在合法方案。题解好像 C 题比 B 题好切。什么条件下，每个连通块内的点的异或和会相等？首先你知道 $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$ 且 $n \equiv 0 \mod {2}$ ，那么说明 $a_1 = a_2 = \dots = a_n$。如果 $n \equiv 1 \mod{2}$ ，那么异或起来应该等于 $a_i$。$n \equiv 0 \mod{2}$ 的情况比较平凡，直接 puts("YES") 即可。我们来讨论第二种情况，也就是说，我们要把整棵树分成奇数个连通块，可以认为就是分成 $3$ 个就行。我们要叉掉两条边，假如能找到一条边叉掉以后连通块异或和相等，只需要检查 $K \neq 2$ 即可。具体地如何找这两条边，我们只需要先找到一棵子树异或和 $=x$，然后再找第二条即可。D简要题意CF 文件交互题给一棵 $n$ 个点的树，定义 $Dist(u,v)$ 为 $u \to v$ 路径上的边构成的边权集合的 $\gcd$，且 $u \neq v$。每一你可以询问交互库 $x$ 个点的点集 $X$，交互库会返回 $X$ 中，$\max\{Dist(u,v)\}, u,v \in X$ 。也就是说，交互库会找到 $X$ 中 $Dist$ 最大的一个点对 $(u,v)$ 并且返回它们的 $Dist$。最多可以询问交互库 $12$ 次。你需要找到整棵树中 $Dist(u,v)$ 最大的那个点对 $(u,v)$。若有多个，任意一个都合法。交互格式：询问：? k v_1 v_2 ... v_k回答：! u v题解不是很懂，看了题解恍然大悟。这个 $Dist$ 的定义看起来很高端，但实际上，要 $Dist$ 最大，肯定就是两个点相邻，然后那条边的边权在树上最大.....然后就二分一下就行了，$n \leq 10^3$ 问 $12$ 次肯定能过。E简要题意给定一个 $n$ 个数的数组，要求找一个连续子区间，满足该子区间的区间 $\&$ 和 $>$ 区间异或和。求该子区间的最大长度。题解首先 $\&$ 出来要不是 $0$，那肯定是该区间所有数的二进制在那一位上全是 $1$。其次还要满足 $\&$ 出来要大于异或和。那如果该区间长度为奇数，那么 $\&$ 和有可能与异或和相等。所以只有长度为偶数的子区间合法。现在要做的事就是找到一个位满足这个条件：在某一个子区间上这一位全是 $1$。如果高位满足条件，那么低位都可以不考虑。但是出现了一个问题，不一定 $\&$ 出来比异或和大。强制规定更高为的异或和为 $0$ ，这样在枚举到更高位时情况没有算漏。代码也非常精简：for (int i = 19; ~i; -- i) { for (int j = 1; j <= n; ++ j) { And[j] = And[j - 1] + ((a[j] >> i) & 1), Xor[j] ^= ((And[j] & 1) << i); } memset(pre, -1, sizeof(pre)); pre[0] = 0; for (int j = 1; j <= n; ++ j) { if (pre[Xor[j]] == -1) pre[Xor[j]] = j; else { int k = pre[Xor[j]]; if (And[j] - And[k] == j - k) ans = std::max(ans, j - k); else pre[Xor[j]] = j; } } }
A题意$\exists x$, 对于$\forall i \in [l,r]$，要求$i\ mod\ x \geq \frac{x}{2}$,判断是否存在这样的$x$B题意给定一个长度为偶数的$01$串，每次可以选定一个子串进行翻转操作。要求最后翻转成一个$0,1$交替的串（只有$0101\dots01$和$1010\dots10$类型的串是合法的串）。求最少的操作次数。CDescription有$n$到菜品被放入了一个烤炉中，每到菜品都有一个最佳取出的时间$t_i$。现在按照一定顺序把菜品从烤炉中取出，每到菜品都有可能因为不在最佳时间被取出而造成不美味，定义这个不美味度为$|T-t_i|$，其中$T$是取出的时刻。求把所有菜品都取出来的最小不美味度。Solution设$f[i][j]$表示在$i$时刻拿出了前$j$个菜品可以获得的最小不美味度考虑暴力DP若不选，则$f[i][j] = min\{ f[i-1[j]\}$如果选的话，那么$f[i][j] = min\{f[i-1][j-1] + |i - t[k]|\}$按照现在的方式DP,每次都要枚举最后选的那个菜品$k$，考虑怎么优化它贪心地选，我们肯定希望$t[i]$比较小的物品在比较靠前的时间就被选中了，这样会比较优如果我们对所有$t[i]$进行排序，那么选出的菜品将会是连续的一段。也就是说，最后一个还未被选中的菜品一定当前要选的Code#include <bits/stdc++.h> using namespace std; const int SIZE = 6e2 + 5; const int inf = 0x7f7f7f7f; int T, n; int a[SIZE], f[SIZE][SIZE]; inline int read() { char ch = getchar(); int f = 1, x = 0; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * f; } int main() { T = read(); while (T --) { n = read(); for (int i = 1; i <= n; ++ i) a[i] = read(); std::sort(a + 1, a + n + 1); memset(f, inf, sizeof(f)); int minn = inf; f[0][0] = 0; for (int i = 1; i <= 2 * n; ++ i) { f[i][0] = 0; for (int j = 1; j <= std::min(i, n); ++ j) { f[i][j] = std::min(f[i][j], f[i - 1][j]); f[i][j] = std::min(f[i - 1][j - 1] + abs(i - a[j]), f[i][j]); } if (i >= n) minn = std::min(minn, f[i][n]); } printf("%d\n", minn); } return 0; }D题意Monocarp有一棵树，可是他已经忘记了它的形态。但是他有这棵树的$bfs$序，并且对于每一个节点，$bfs$都会按照升序遍历它的子节点。现在给出这个$bfs$序，求出这棵树的最小深度。