Codeforces

LCat90 · 2023-09-08 23:49:08 · 个人记录

Lovely_Cat's Codeforces

不知道几百年前写的：

才开始打。新人局还没打完。甚至 div3 进不了前 1000，div2 进不了前 2000。有大问题。

争取尽快上紫。

怎么说，现在能上蓝就好了。

9.26 Div3 进 1000。

9.30 Div2 掉出 7000。

10.8 Div2 进 2000。

Div 3

sb 模拟题，赛时差点没调出来。

代码能力需要加强。

首先排序，发现对于 a_1，其后 n-1 个 \min 都是他。普遍的，如果序列单调不减，那么第 i 个位置带来的 \min 值有 n-i+1 个，包括自己。

所以我们将输入的 b 进行排序，如果有解的话那么最小的数一定在最前面且个数和上面的推导一样，每次往后跳相应的个数输出即可。

这样会剩下没有影响的最后一个数，我们只需要保证它大于等于最后一个数即可。最好是等于，因为 a 和 b 的上界相同，避免越界。

首先排除是图论的可能性，因为建边就需要 n^2，而 div3 不可能在这里考什么线段树优化建图。

所以应该是思维。观察样例发现，对于点 x,y,z，如果有边 x\rightarrow y,y\rightarrow z，那么一定有边直接 x\rightarrow z。

这说明，每个点直接到达的点和通过其它点到达的点是相同的，就和图论没有关系了。

将式子 a_x-a_y\ge b_x-b_y 移项得 (a_x-b_x)-(a_y-b_y)\ge 0，所以此题的 a 和 b 直接合并为 a-b。并按此从小到大排序。

然后对于每个点，如果要到达所有点，那么肯定是要 a_y-b_y 最大时仍满足条件，即 (a_i-b_i)-(a_n-b_n)\ge 0。

转换一下题意，设当前点为 i，就是求 n+\sum_{j=1}^n |a_i-a_j|。

先从小到大排个序，然后如果 j<i，则直接拆开绝对值，这些 j 的贡献为： (i-1)\times a_i-\sum_{j=1}^{i-1} a_j 。

反之如果 j>i，则反过来： \sum_{j=i+1}^{n}-(n-i)\times a_i。

区间和用前缀和求。

初中数学。

记得上课讲的吗：知二求二？

已知 a_i+a_j=x,a_ia_j=y，如何求出 a_i 和 a_j ？

注意要判断 \sqrt{x^2-4y} 是否为整，以及 x +\sqrt{x^2-4y} 是否为偶数。

最后求得了 a_i,a_j，将他们的数量相乘即可（考虑用 map 记录数量）。特别地，如果 a_i=a_j，那么答案为 \dfrac{m(m-1)}{2}（m 为 a_i 的数量）。

如果不要重复的话，长度为 x 的序列的方案数即为 \dfrac{x(x-1)}{2}。于是我们二分这个 x，找到最大的 x 使答案小于等于 n。

注意最终是要让答案刚好等于 n。所以我们还要减少一部分的方案。

这时就需要加入重复的元素了，因为之前相同的元素已经和其它不同元素匹配了，所以新加的元素只能和相同的元素匹配且仅匹配一次，但这已经足够了，所以答案为 x+(n-\dfrac{x(x-1)}{2})。

容易发现减少量只和最后去看的地方有关，所以我们枚举这个位置，问题就转化成了在前面几个数中选出 m 个最大的大于 0 的数，优先队列维护即可。

可以开始攒魔法最后一次性使用。

观察到 n\times \sum s\le 10^8 可以背包。

假设我们要用 A 消灭怪物和为 x，总的怪物为 S，则 B 的和即为 S-x。可以背包预处理出合法的 x，然后时间即为 \max \{\dfrac{x}{w}, \dfrac{S-x}{f}\} 向上取整。

一种麻烦的方法是直接建线段树然后打标记。

显然有巧妙的做法，考虑从异或的性质出发。

首先对于取反操作，被选的数字变为不选，没选的数字变为选了。可以通过直接异或上区间异或和得到。因为一个数异或自己奇数次得到的答案是自己，偶数次是 0，恰好满足。

然后是求整个序列异或和。如果是求标号 1 的就直接输出结果，否则输出区间内其它元素的异或和。类似地可以通过所有元素异或和异或上当前标号为 1 的异或和。

复杂度为线性。

类似于 ABC315 F。

乘法极易产生溢出，那么问题一定可以排除掉大部分。

如果序列中所有数的乘积比这个区间的理论最大和更大，则可以直接选取整个序列。特殊情况是除掉首尾的 1。

否则我们就在区间中暴力选取左右端点，前提是不为 1。由于所有数的乘积小于理论最大和，那么大于 1 的数的数量一定小于 50（2^{50}\ge 2\times 10^{14}）。复杂度上限是 O(50^2)，稳过。

判断乘积是否大于一个值的时候，为了防止越界，可以将一个乘数移到另一边改为除法。（NOI 春测遗留技巧）

回顾 ABC315 F，此题中我们通过 2^x 的增量大发现 x 的上界极小，于是从此出发优化了 DP 转移。

总结起来，从上界的局限性出发，这也不失为一种优化算法的新方法。

一种暴力的做法是平衡树无脑翻转。

但是我们考虑巧妙的做法。题目中 x 对应了一个连续的区间，并且这些区间一定没有交叉，要么就是包含。

根据这个性质，对于一个点 i，我们记录它被翻转了几次。如果是奇数次，就将它和另一个元素翻转；如果偶数次则保留。区间加我们可以维护差分序列，最后求和。

性质 1： a \& b \le a,b。

性质 2： 当且仅当 a_l 到 a_r 的第 k 为均为 1，\& _ {i=l}^r a_i 的第 k 位为 1。

性质 1 告诉我们单调性，即可以二分；而性质 2 则直接告诉我们 check 怎么写。

Div 2

把题干转化为 a[\ l[i]\ ]=l[i+1]，似乎要清晰地多了。很容易看出这是一个环状结构。于是可以发现当这个环的长度为 k 的时候对于环内明显是可以构造的。

建边就是朴素地将 i 和 b_i 相连，即 (i,b_i)。

对于不在环上的点，我们先考虑填充它们。选上 k 个数（可以选环上的）使不在换上的点一定满足条件，后面我们最后再覆盖环上的即可。因为顺序后面的优先级更大。

等于的情况满足了，接下来要判断大于或小于的情况。

如果环长小于 k，那么在环上的操作中，至少有一个顶点不是来自环上，这意味着环上至少有一个顶点将被一个不在环上下一个顶点的数字所替换。但是因为环上的每个顶点都应该被它后面的下一个顶点所替换，故不行。大于的情况同理不行。故问题即为判断环长是否等于 k。

注意特判 1 的情况。

样例水并且是结论题的时候，一定要打暴力对拍验证自己的代码。

注意到题目只对 a_{n+1} 进行了限定。并且对应关系说明了如果 a_{n+1} 固定，那么整个 a 就确定了。

然后考虑对应关系：a_i=a_{i+1}\bmod i，这说明 a_i < i。而题目要求的是相同的 a_i，这说明很可能出现一段连续的 x。

手推一下样例，并且注意到样例只给了一个很大的 k，且还无解。剩余 k 都很小。就可以大胆推测：k 很大时无解。

发现当 a_{n+1}=x\le n 时，x 这个值会一直延续直到遇到 x 下标，此时变为 0，并且一直延续到最后，共 2 个不同的值（当 x=0 时只有 1 个）；当 a_{n+1}=x>n 时，a_n 的时候就会进行突变，然后按照上面的方法继续，答案为 3。然后就大胆地猜测 k 的上限是 3，超过 3 无解。经过暴力认证正确。

你说得对，但是求方案数。

很套路地想到确定最大值然后计算它的贡献次数。

所以想到从大到小排序，对于当前 x。都有使之能被选的下标 id，即它的因数。从大到小处理的好处就是，如果之前的数已经用了一个因数 r，那么它的贡献只能是之前的 x'，不能是当前的数 x。那么我们可以打标记，保证这个数一定是被选的最大值。

所以我们 \sqrt n 地枚举出下标 id 的因数，找出满足约束的合法因数个数，设为 m。

想一下怎么计算方案，发现是一个排列组合。对于这 m 个因数，任意选 1 个就可以使 a_{id} 成为最大值，也即 m 个数中任意选，只要不是空集。故有 2^m-1 种选法。然后其它数呢？除了之前有约束的（已经被选过的，设有 p 个）不能选，其它随便选。即 2^{n-p-m}，乘起来然乘 a_i 加给答案。

考虑重复的问题，如果重复那么就说明一个集合所构成的数集对应的最大值不唯一，显然矛盾，故不会有重复。

有个 map，所以时间复杂度是 O(n\sqrt n\log n)，非常跑不满。