留档1

千早爱音 · 2022-07-26 10:14:19 · 个人记录

CF1634C

分析：如果 k=1 ，随便输出一个 1-n 的排列即可。

如果 n 是奇数且 k≠1 ，无解，因为奇数的数量必须和偶数一样，否则无法构造一种合法方案。

否则，我们对于每一排 i ，放置 i,i+n,i+2 \times n,…,i+(k-1) \times n 。

可以证明，对任意区间 [l,r] ,区间和都能被 r-l+1 整除。

证明如下:

显然在 n 为偶数时， (r-l+1) \mid sum 。命题得证。时间复杂度 \mathcal{O}(n \times k) 。

另外，本题还有一种构造方案：把所有奇数和偶数分别输出即可。

证明： \sum\limits_{i=1}^{n}{(2 \times i -1)}=n \times n 显然能被 n 整除。

然后其余的子区间可以视为由这个数列所有数同时加某个数得到，所以平均数显然还是整数。

时间复杂度 \mathcal{O}(n*k) 。

CF1548A

分析：直接暴力显然是不行的。

由题意可得最大的那个人连着的所有人都会寄，所以如果有一个人 a 比 b 强度大，而且 a,b 之间有连边，那么 b 就会寄。因为 a 一定在 b 之后死，这条边就一直存在。

然后维护比每个节点弱的节点的数量即可。

时间复杂度为 \mathcal{O}(N+M+Q) 。

CF1542B

分析：由题意可得 S 内的数都可以表示为 a^i+b \times j 的形式。

因为把计算顺序改变并没有影响，可以把加法移到前面，不影响答案。

因为 n \bmod b 的值只能通过 \times a 的操作改变，所以只要先算出 a 的所有小于等于 n 的幂，判断 n \bmod b 是否与 a^i \bmod b 相等即可。

注意 a=1 时需要直接判断。

时间复杂度 \mathcal{O}(T\log{n}) 。

CF1352F

分析：当 n1 等于0时，因为题目保证有解，所以输出 n0+1 个 0 或者 n2+1 个 1 即可。

否则答案中至少有一个 01 或 10 。然后连接这些串，可以形成类似 01010101 这样的序列，然后在第一个 0 前面加上 n0 个 0 ，在第一个 1 前面加上 n2 个 1 ，构造出来的字符串即满足要求。

时间复杂度 \mathcal{O}(n) 。

CF1352G

分析：看到绝对值之差在 2-4 之间，可以想到把 1-n 的数按照奇偶性分成两类，先输出 1,3,5,… 再输出 n/2*2,…,8,6,4,2 。

可以简单证明 n<4 时一定无解。

但因为 \leq n 的最大偶数与最大奇数只相差 1 ，这么构造是不行的。

于是可以微调一下序列，把偶数序列交换其中两项使得满足条件即可。

时间复杂度 \mathcal{O}(n) 。

CF1542C

分析：直接计算显然不行，所以可以打表找规律。

发现 f(6)=f(12)=f(18)=4,\operatorname{lcm}(1,2,3)=6

于是猜想可以通过 \operatorname{lcm} 把每个数按照 f(x) 的值分类，然后用类似数论分块的思想解决。

考虑 f(x)=i ，那么 x 必须要有 1-i-1 这些因子。

当我们计算 n/\operatorname{lcm}(1,2,3,…,i-1) ，我们得到的就是能被这些数整除的数 的个数，我们计算 n/\operatorname{lcm}(1,2,3,…,i) 时，就得到了前面计算到 i−1 时，能被 i 整除的个数，相减后我们就能够得到 f(x)=i 的元素个数。

因此结果就是统计 所有满足 i 条件的总和即可。

打表后发现 n < \operatorname{lcm}(1,40) ，所以总时间复杂度 \mathcal{O}(40T) 。

CF76D

分析：如果 A<B 或者 A-B 是奇数显然无解。

否则先打表找规律，可以发现 X=(A-B)/2,Y=X+B 。

证明：如果 X 的某个二进制位是 1 ， Y 的某个二进制位为 0 ，那么可以交换它们，不影响答案。

所以 X 的某个二进制位是 1 ， Y 的这个二进制位也必须为 1 。

所以 Y=X+B 。又因为 X+Y=X+X+B=A ，所以 X=(A-B)/2 。

但这道题就这么做完了吗？似乎还差一点吧。

注意到原题下方有一个帖子提供了一组 hack 数据，可以分析为什么这份代码为什么会被 hack 。

因为 X+Y=A，X xor Y=B

则可以构造 X'=highbit(X),Y’< X’,A=X’+ Y’,B < X’，则 X’ xor Y’>=X’>B ，不合法。

这样的hack数据有很多，于是这个做法就寄了。

解决方案是在每次判断无解前重新判断一次构造出来的解法是否符合题目条件，如果不行的话就一样视为无解。

一组 hack 数据：

input:
7 1
wrong answer:
3 4
std:
-1

CF76E

因为某些原因不放。

CF1598D

分析：考虑补集转化。

首先不难得出从 n 个数里任意选 3 个的方案数有 n \times (n-1) \times (n-2)/6 种。

接下来去掉不满足条件的个数，即满足既有 a 相同，又有 b 相同的三组数的 方案数。

对每个 i 计算与 a_i,b_i 相同的 a,b 的个数，设存在两个数和 a,b 分别相同，因为 每两个数对都互不相同，所以不会重复也不会遗漏。

显然这两个数可以随便组合，设和 a_i 相等的数为 j ,和 b_i 相等的数为 k ,则不合法的方案数为 (j-1) \times (k-1) 。

把所有不合法的方案相加，然后用总方案数扣除即可。

总时间复杂度 \mathcal{O}(n) 。

CF1034A&&CF757B

首先把所有的数除以他们的 gcd ，然后再找一个质因子能被最多的数整除就可以了。最后只需要找到所有数里面出现次数最多的因子。 时间复杂度 \mathcal{O}(n^{3/2}) 或 \mathcal{O}(n \log{n}) 。

CF1415D

分析：当 n>66 时显然有解，次数为 1 。

可以证明，当三个相邻数的 highbit 相等时，可以通过将 前两个数异或破坏序列不降。

因为 highbit 最多只有 64 种取值，且序列不降，所以 n>66 时必定存在三个 highbit 相同的值排列在一起。

剩下的情况因为 n 很小，所以可以直接暴力求解，用前缀 和做的时间复杂度 \mathcal{O}(n^3) ，因为没有多测，可以通过。

CF690A3

看我题解，不贴。

CF1616H

分析：把数按照高位分类。

设在当前位 i 时分成两组 AB ，表示至少要从 AB 中各选一个，以满足 i+1 及以上的位都被填满。

把 AB 按照当前 01 位继续分类，得到