Codeforces Round #732 题解

AquaMoon and Two Arrays

因为要求每一次操作后数都要大于 (0), 于是我们每一次选一个大于其目标值的数把它减一,选一个小于其目标值的数把它加一即可。

AquaMoon and Stolen String

我们发现答案串的每一个字母显然出现了奇数次,而其他字母也只能出现偶数次,于是我们把每一列出现奇数次的字母提出来就是答案了。

AquaMoon and Strange Sort

显然每一个数的初始位置与最终位置的距离必然为偶数。

于是偶数位置的数交换后还是只能在偶数位置,奇数位置的数交换后还是只能在奇数位置。

于是我们把偶数位置的数排一遍序,奇数位置的数排一遍序,如果原数组有序了,那么说明可以。

(实在是不知道为啥比赛的时候有一堆树状数组做法啊)

AquaMoon and Chess

我们发现一次移动可以看作是这样:我们把 (i) 要跳过的 (1)(i) 跳的方向移动一格,(i) 位置的 (1) 只往它要跳的方向移动一格,这样效果是一样的。

于是我们发现操作变成了选相邻两个 (1) 把它们往左/右移动一格(但 (1) 不能重叠)。

于是我们相邻两个 (1) 分一组,并且分出尽可能多的不相交组。

我们再魔改一下这个操作,我们只移动这些组,每次移动相当于把移动方向的下一个数移到这个组后面去,可以发现操作还是等价。

于是我们发现问题变成了把若干个全 (1) 组往里面插入,随便组合数一下就行了。

AquaMoon and Permutations

首先如果一个数在一列只出现了一次,那么它所在的排列必然要在答案中。

于是我们不断提出这样的排列,把与它在同一位置有公共元素的排列删掉,由于原来的答案排列都能配对至少一个新增排列,所以每确定一个排列,都至少有确定的排列个数这么多个排列被删除。

于是我们每一次排列数减至少两个,值域减小一个,递归成子问题。我们这么做,直到每一个数在一列中均出现两次。

然后我们来证一个奇妙的东西(证明可能不太严谨):当每一列,每一种数仅出现两次时,新增排列组可以取出若干互不相交的集合,原排列组也对应取出若干互不相交的集合使得,把任意一些对应集合互换,得到的排列组依然是拉丁方,并且这些集合是极小的,那么任意一种方案都可以通过这些替换来得到。

(A) 数组为刚开始的排列组,(B) 为新增的排列组;

且我们存在:

[S_i={B_{x_{i,1}},B_{x_{i,2}},dots,B_{x_{i,m}}} ]

[T_i={A_{y_{i,1}},A_{y_{i,2}},dots,A_{y_{i,m}}} ]

其中 (S_i) 可以替换 (T_i)

若存在 (S_icap S_j = X)(T_icap T_j = Y(i e j))(|X|,|Y|) 不同时为空。

我们令 (S_i) 中排列的第一个数形成的集合为 (M_i)(S_j)(M_j)(T_i)(N_i)(T_j)(N_j)(X)(M)(Y)(N),则显然 (N=N_icap N_j)。由于 (A) 中的第一位两两不同,如果 (|X|>|Y|),则显然 (|M_icup M_j|=|M_i|+|M_j|-|M|<|N_i|+|N_j|-|N|=|N_icup N_j|),发现替换后数的种类变少了,不可能替换成功。

(|X|<|Y|),由于 (|N|=|Y|),则 (N) 中一定有数不出现在 (M) 中的。则它们一定要出现在 (M_isetminus M)(M_jsetminus M),出现了三次,矛盾。

(|X|=|Y|),如果 (M) 中有数重复,则还是有数出现三次。可推得 (M=N),且 (M_isetminus M=N_isetminus N)(M_jsetminus M=N_jsetminus N) 中。第一个数是这样,其他的数也同理。则可以分为三个集合 (S_isetminus X)(S_jsetminus X)(X) 来取代 (T_isetminus Y)(T_jsetminus Y)(Y)

因此任何一种替换都可以由若干不相交的极小的替换的组合而成。而这些极小替换直接显然独立,任意一种组合的替换都是合法的。

于是我们随便挑一个排列,存在一个排列与它配对,把它删掉,或者把与它配对的排列删掉,再缩小排列组,最终得到的集合是一样的(因为被删除的集合肯定是原排列的某集合和它的替换集合)。我们把它删掉,缩小,把答案乘 (2) 就行。

这样复杂度就能 (O(n^2)) 了。

AquaMoon and Wrong Coordinate

我们发现我们差分一下,就能发现哪一行有问题,因为每一行的和必然为等差数列,把差不对的提出来就行。同时我们可以知道这一行正确的和是什么。

然后我们发现我们要找具体是这一行的哪一个不对,于是我们求出每一行的平方和,原数组平方和是 (sum_{i=1}^n x_i^2),运行 1s 后应该为 (sum_{i=1}^n x_i^2+2x_iv_i+v_i^2),差分一下是 (sum_{i=1}^n 2x_iv_i+v_i^2),于是差分数组应该是等差数列,我们直接把差分数组再差分,得到 (sum_{i=1}^n 2v_i^2),然后用这个把不对的位置修正一下,于是我们得到了这一行位置正确的平方和。我们知道正确的和与平方和,就很容易逆推出哪一个出了问题了。

AquaMoon and Time Stop(easy/hard)

这是一道数据结构练习题。

我们发现我们可以按时间扫描,把这一时间的每个位置的答案都搞出来。

我们发现当一个被禁止的区间出现时,中间的所有位置答案全部变成无穷。

当一个被禁止的区间消失时,会有若干区间又空了出来。我们用这个区间两侧的区间的答案来更新中间的答案(如果两侧区间都是无穷就不用管它,所以至多只有两个这样的区间)。我们发现有这么两种情况:

一个是两侧的区间分别贡献了中间区间的一点答案,答案显然形成了两段等差数列。

一个是一侧的区间就贡献了所有答案,甚至会影响另一侧的区间。

当一段区间两侧不出现区间增删的情况,我们发现经过若干秒它自己的答案直接平移秒数这么多格,然后在左边补一个等差数列,右边多的直接删去。

我们发现操作都是形如插入/删除等差数列的形式,于是我们直接用平衡树维护即可。

对于上面的情况二,我们直接暴力修改被影响的区间,因为每次只会加常数个区间,修改会删除若干区间,消耗时间是删除区间的个数,于是复杂度是 (O(nlogn))

AquaMoon and Potatoes

以下是老K的神仙做法()

我们先直接把 (b)(c) 换掉,然后变成了 (b_i=a_j=c_k)

考虑一个简单的线性 DP:

for i=1 to x:
 ans+=s2[c[i]];s2[a[i]]+=s1[a[i]];++s1[b[i]];

然后我们设置 (sqrt n) 个断点,每个断点把 (s1,s2,s3) 暴力存下来。

对于每一块,我们把答案 (s1[x],s2[x],s3[x]) 写成向量(每个值都记一个向量),经过中间一串数相当于左乘矩阵。

修改我们直接把这一段的矩阵暴力改掉,把后面块被影响的向量也暴力改掉。

查询我们整块的部分对于每一个值已经有答案了,求和就行,零散块只会影响 (sqrt n) 个位置的值,暴力改掉就好。

复杂度 (O(nsqrt n)),比较好写(也许),还可以强制在线()

UPD: 注意常数(

原文地址:https://www.cnblogs.com/invisible-eyes/p/15003033.html