题目地址
https://codeforces.com/contest/2093
锐评
在所有题意都理解正确的情况下，整体难度不算太难。但是偏偏存在F这么恶心的题意，样例都不带解释一下的，根本看不懂题。D题也恶心，在于递归过程的拆分，需要点数学，跟打印递归定义的图形一样，写麻了，好在过了。E题居然卡双 (log) 做法常数，也是恶心。反而是G题很典，太裸了，可惜被D防住了，根本没看到G题。再次陷入“看完所有题不会写，不看完所有题却会写”的魔咒。主要还是自己太菜了，打破不了这个魔咒，大佬们就没这个烦恼。
题解
Problem A. Ideal Generator
题目大意
由 (k) 个正整数组成的数组 (a) 在 ([a_1, a_2, dots, a_k] = [a_k, a_{k-1}, dots, a_1]) 的情况下称为回文数组（其实就是正着读反着读是一样的）。例如，数组 ([1, 2, 1]) 和 ([5, 1, 1, 5]) 是回文数组，而数组 ([1, 2, 3]) 和 ([21, 12]) 不是回文数组。
如果任何整数 (n) ( (n geq k) ) 都可以表示为一个长度正好为 (k) 的回文数组的元素之和，我们就称这个数 (k) 为理想生成数。数组中的每个元素都必须大于 (0) 。
例如，数字 (1) 是一个理想生成数，因为任何自然数 (n) 都可以用数组 ([n]) 生成。然而，数字 (2) 并不是一个理想生成数，因为不存在长度为 (2) 的和为 (3) 的回文数组。
请判断给定的数字 (k) 是否是理想生成数。
题解思路：思维
先通过样例观察，发现奇数可以，偶数不行。开始验证，假如和为 (k) ，那么全部数组元素为 (1) 即可，假如和为 (k + 1) ，那么全部数组元素为 (1) 的基础上，有一个数要加上 (1) 还要是回文数组，那么只能放在最中间的位置上了，不然所放位置对称的那一个位置就不相等了。又因为 (n) 是连续的，所以差值为 (1) 只有数组长度是奇数才能满足，每次都在最中间位置加上 (1) 。时间复杂度为 (O(1)) 。
参考代码（C++）
Problem B. Expensive Number
题目大意
正整数 (n) 的代价被定义为数字 (n) 除以其数位之和的结果。
例如，数字 (104) 的代价是 (frac{104}{1 + 0 + 4} = 20.8) ，数字 (111) 的代价是 (frac{111}{1 + 1 + 1} = 37) 。
给你一个不包含前导零的正整数 (n) 。你可以从数字 (n) 中删除任意数位(包括不删除)，这样剩下的数字至少包含一位数，并且严格大于零。剩下的数字不能重新排列。因此，你可能得到一个前导为零的数字。
例如，给你一个数字 (103554) 。如果去掉 (1) 、 (4) 和一个数字 (5) ，最后得到的数字是 (035) ，其代价是 (frac{035}{0 + 3 + 5} = 4.375) 。
为了使代价最小，你需要从这个数字中删除最少多少个数字？
题解思路：贪心
首先，一个数字的数位之和是不可能大于这个数字的，最多和它相等。那么代价最小意味着什么？显然就是相等。所以只有一位数字时代价达到最小，代价为 (1) 。因为题目删除数位后允许有前导 (0) ，所以选定某个数字前面的 (0) 可以不删除。又因为题目要求删除后组成的这个数必须严格大于 (0) ，所以我们要找一个非 (0) 数位。因为前导 (0) 可以保留，后导 (0) 不能保留（保留就不是个位数了），所以我们倒着枚举，找到第一个非 (0) 数位位置，将这个位置前面的非 (0) 数位删除以及后面的数位删除，删除的数位个数即是答案。时间复杂度为 (O(n)) 。
参考代码（C++）
Problem C. Simple Repetition
题目大意
帕夏喜欢质数！为了找到生成质数的新方法，他再次对互联网上的一种算法产生了兴趣：
- 要得到一个新数字 (y) ，重复 (k) 次数字 (x) 的十进制表示 (x) (不含前导零)。
例如， (x = 52) 和 (k = 3) 可以得到 (y = 525252) ， (x = 6) 和 (k = 7) 可以得到 (y = 6666666) 。
帕夏非常希望得到的数字 (y) 是质数，但他还不知道如何检验这种算法生成的数字的质性。请帮助帕夏，告诉他 (y) 是否是质数！
如果一个整数 x 只有 2 个不同的除数 1 和 x ，那么这个整数 x 就是质数。例如， 13 是质数，因为它只有 2 个除数： 1 和 13 。请注意，数字 1 不是质数，因为它只有一个除数。
题解思路：思维/分类讨论
我们来一一分析下。
- (k = 1) ，显然只需要判定 (x) 是否质数。
- (k gt 1) ，即 (x) 至少重复了 (2) 次，设 (x) 有 (n) 个数位，那么 (y) 显然有一个除数 (x) ，使得 (frac{y}{x} = a_1 underbrace{0 cdots 0}_{n - 1个} a_2 underbrace{0 cdots 0}_{n - 1个} dots a_k) ，其中 (a_i = 1, 1 leq i leq k) 。那么只要 (1 lt x lt y) ， (y) 必然不是质数，显然 (x lt y) 必然成立，所以只需要再单独判断一下 (x) 为 (1) 的情况即可。
根据上面的分析，问题得解。时间复杂度为 (O(1)) 。
参考代码（C++）
Problem D. Skibidi Table
题目大意
瓦迪姆喜欢用整数填充方形表格。不过今天他想到了一个好玩的方法！以大小为 (2 times 2) 的表格为例，表格的行从上到下编号，列从左到右编号。我们将 (1) 置于左上角单元格， (2) 置于右下角单元格， (3) 置于左下角单元格， (4) 置于右上角单元格。这就是他所需要的全部乐趣！
幸运的是，瓦迪姆有一个大小为 (2^n times 2^n) 的表格。他计划用从 (1) 到 (2^{2n}) 的整数按升序填满它。为了填满这样一个大表，瓦迪姆将把它分成 (4) 个相等的方表，先填满左上角的表，然后填满右下角的表，接着填满左下角的表，最后填满右上角的表。在填满每张小方表的过程中，他又会把每张小方表分割成更小的表，直到填满 (2 times 2) 大小的方表为止。
现在瓦迪姆迫不及待地想开始填表，但是他有两类 (q) 个问题：
- 第 (x) 行第 (y) 列的单元格中的数字是多少
- 数字 (d) 位于哪个单元格坐标
帮助回答瓦迪姆的问题。
题解思路：DFS
题意倒是很直接，思路也很明确，就是不断DFS缩小区域。但是这个区域怎么设计还真是恶心，会的很会，不会的真的会卡很久，看群友有被卡两小时的。
首先对于块的大小，假如当前处于第 (n) 层，块的大小为 (2^{n - 1} times 2^{n - 1}) ，即是宽高各减一半。其次是对于坐标步长，根据前面分析（宽高各减一半），可知步长就是 (2^{n - 1}) 。知道这两个性质就好办了，只需要知道当前处于第几层，以及当前层的左上角坐标，即可一步步缩小范围，直到不能再缩小，即是答案，详见代码。时间复杂度为 (O(nq)) 。
参考代码（C++）
Problem E. Min Max MEX
题目大意
给你一个长度为 (n) 的数组 (a) 和一个数字 (k) 。
子数组的定义是数组中一个或多个连续元素的序列。你需要将数组 (a) 分割成 (k) 个不重叠的子数组 (b_1, b_2, dots, b_k) ，使得这些子数组的合集等于整个数组。此外，你需要最大化 (x) 的值，即 (x = min(MEX(b_i)), 1 leq i leq k) 。
(MEX(v)) 表示数组 (v) 中没有的最小非负整数。
题解思路：二分
对于 (u = MEX(v)) ，如果选择数组 (v) 的一部分数组成数组 (vt) ，那么对于所有 (w lt u) ，是否都能找到 (w = MEX(vt)) ？答案是肯定的。所以我们考虑二分，下限 (l = 0) ，上限 (r = n) （因为数组顶多是 ([0, 1, dots, n - 1]) ）。那么我们怎么去check呢？对于 (MEX) 为 (u) ，我们只需要维护一个集合，然后遍历整个数组，对于每个元素，满足 (a_i lt u, 0 leq i lt n) ，就将其加入集合，当集合元素个数达到了 (u) ，然后计数加一（表示可以划分为一个子数组，满足 (MEX geq u)），并且清空当前集合。这样到最后，只要计数大于等于 (k) ，表示可以合理划分。时间复杂度为 (O(nlognlogn)) （check用到了set，换成数组每次标记取反可以降到 (O(nlogn)) ）。
PS：此题居然卡双 (log) 做法常数，真是无语啊！
参考代码（C++）
双 (log) 超时代码。
双 (log) 通过代码。
单 (log) 通过代码。
Problem F. Hackers and Neural Networks
题目大意
黑客们再次试图利用神经网络的输出创建娱乐短语。这一次，他们想获得长度为 (n) 的字符串数组 (a) 。
最初，他们有一个长度为 (n) 的数组 (c) ，其中充满了空白，用符号 (*) 表示。因此，如果 (n = 4) ，则初始值为 (c=[*, *, *, *]) 。
黑客可以访问 (m) 个神经网络，每个神经网络都有自己的请求答案版本--长度为 (n) 的字符串数组 (b_i) 。
黑客试图通过以下操作从数组 (c) 中获取数组 (a) ：
-
选择神经网络 (i) ，对数组 (c) 执行下一步操作：选择一个随机的空白，例如在位置 (j) 处，将 (c_j) 替换为 (b_{i, j}) 。
例如，如果选择了第一个神经网络 (b_1 = [text{«I»}, text{«love»}, text{«apples»}]) ，当前 (c = [*, text{«like»}, *]) ，那么在对第一个神经网络进行操作后， (c) 可能会变成 ([text{«I»}, text{«like»}, *]) 或 ([*, text{«like»}, text{«apples»}]) 。
-
选择位置 (j) 并将 (c_j) 替换为空白。
不幸的是，由于黑客访问神经网络的方式，他们只能在所有操作完成后才能看到修改后的数组 (c) ，因此他们必须事先指定整个操作序列。
然而，神经网络的随机行为可能会导致永远无法获得所需的数组，或者获得所需的数组需要过多的操作。
因此，黑客们希望您能帮助他们选择一个操作序列，以保证在最少的操作次数内获得数组 (a) 。
更具体地说，如果存在一个操作序列可以保证从数组 (c) 中获得数组 (a) ，那么在所有这样的序列中，找出一个操作次数最少的序列，并输出其中的操作次数。
如果没有将数组 (c) 转换成数组 (a) 的操作序列，则输出 (-1) 。
题解思路：贪心
题意真的很长且很拉，真的看完好像不知道要求什么？让我们再细细品味一下！反正就是进行两个操作嘛，只要对应位置的字符串不对就一定要继续操作。只要操作，那么操作次数必然会增加。
假如某个操作后，某个位置已经是正确的，下一次操作你会不会去改它？显然不会了，不然你还得再至少进行一次操作二以及至少随机一次操作一，而且随机后不一定是对的，何必呢？
如果所有位置都是空的，你会不会进行操作二？显然也不会，白白浪费一次操作嘛。所以第一次操作肯定是操作一，这是个随机过程。
通过上面的分析，我们唯一能决定的就是可以选择跑哪个神经网络。从概率论角度来说，我们当然希望选择命中概率更高的，这样所得的期望就越大，后续所需要的操作就更少。所以第一次操作就至关重要了，我们就选命中概率最大的神经网络，这样我们就能保证 (n) 次操作后，随机正确位置最大。这样所有位置都被填满了，最后对不正确的位置，我们只需要先执行一次操作二，再找到一个神经网络，其对应位置存在正确字符串，因为只会空白位置随机，而当前空白位置只有一个，显然这是一个必然事件。
上面操作一定是最优的吗？一定的。假设你选择某个神经网络的命中率是 (frac{x}{y}) ，你把其他所有的神经网络全部组合起来，命中率形如 (frac{x + a}{y + b}) ，其不可能更大。
对于不存在的情况，显然所有对应位置都没有目标串，就无法做到。时间复杂度为 (O(mn max(|b_{i, j}|))) 。
参考代码（C++）
Problem G. Shorten the Array
题目大意
长度为 (m) 的数组 (b) 的美感定义为所有可能数对 (1 leq i leq j leq m) 中的 (max(b_i oplus b_j)) ，其中 (x oplus y) 是数字 (x) 和 (y) 的 bitwise XOR。我们将数组 (b) 的美感表示为 (f(b)) 。
如果数组 (b) 中有 (f(b) geq k) ，那么这个数组 (b) 就叫做美丽数组。
最近，科斯佳从商店买了一个长度为 (n) 的数组 (a) 。他认为这个数组太长了，所以打算从中剪切出一些美丽的子数组。也就是说，他想选择数字 (l) 和 (r) ( (1 leq l leq r leq n) )，这样数组 (a_{l dots r}) 就很美丽了。这样一个子数组的长度为 (r - l + 1) 。整个数组 (a) 也被视为一个子数组(包含 (l = 1) 和 (r = n) )。
你的任务是找出数组 (a) 中最短的美丽子数组的长度。如果没有一个子数组是美丽的，那么你应该输出数字 (-1) 。
题解思路：双指针+字典树Trie
首先，对于每个 (l) ，如果找到第一个满足条件的 (r(r geq l)) ，那么显然 (r + 1(r lt n)) 也可以。既然这样，那么我们维护一个双指针，对于每个左指针，不断扩展右指针，直到找到第一个满足条件的位置，更新答案即可。那么怎么快速计算出当前区间是否可以满足条件呢？很容易就会想到字典树求当前区间可以得到的最大异或值。时间复杂度为 (O(n)) （计算次数实际为 (30n) ，常数忽略，但实际运行时间还是要考虑的）。
参考代码（C++）
