【算法竞赛】水CF构造题

简单的说明

我太弱了，水水构造tag的题去。 大概只写写思路（毕竟构造题） 打*的是自己想没直接出来的。 发布时间，最早为20220814-14:14，现在为最新水题时间。

1325/A EhAb AnD gCd

发现x->(1, x-1)一直合法。

1454/A Special Permutation

要求全不在自己位置上，那就全都前移，1在最后

1353/A Most Unstable Array

分成n == 1, n == 2, n >= 3讨论。 因为 ai 的值为非负数，那么差值的和最大为m*2，分开还是一个数不影响。 n==1，为0 n==2，只有一边，为m n==3，m*2

1343/B Balanced Array

因为前半是偶数，后半是奇数，且前后总和要相等，所以当n为4的倍数的时候才有解 [1,n/4] -> 2i, [n/4+1,n/2] -> 2i+2, [n/2+1, n] -> 2*i+1

1348/B Phoenix and Beauty

题意：长度为n的序列，在其中插入若干的数（1~n，可以插在开头与末尾），使得它在任何一段长度为k的连续子串的和相同。

假设选择的序列为[l,r],那么按照题意，它要和[l+1,r+1]相等，因为[l+1,r]一样，所以a[l]与a[r]相等，因此，这样从小到大比过去，我们发现，只有a数组中不同的数小于等于k时，才有解。 并且，我们可以很快找出一个可行解。把有的数都放入一个数组b中，不足k个随便用其他数（1~n）补足。重复n遍，是符合题意的。这样相当于在每个数的前后插入一系列数，使其成为那个序列。 （我不知道为什么我vector搭配queue的方式模拟会MLE qwq）

*1365/C Rotation Matching

题意：给你两个全排列的序列，能够任意对这两个序列进行左移与右移x位（最左的移到最右，最右同理），求两个序列在若干次操作后最大的（ai==bi）匹配数。

显然，向左移与向右移是类似的，向左移1位，等同于想又移n-1位；同样，移动a序列与移动b序列也是一样的，所以只需要操作一个序列，向一个方向移。 因为每个数，有且只有相应一个要匹配的数，所以，可以通过每个数需要移动的次数，来表明这些数是在整体移动了几轮后匹配上的。（若移动的次数为负数，按照上述论述，只需要+n即可） 最后，再统计每个数的移动次数，出现频率最高的轮次的次数就是答案。

1375/C Element Extermination

题意：给你一个长度为n的全排列，按照ai<ai+1(1 <= i < n)，可以删去ai或者ai+1的规则删除，输出是否最终可以只剩下一个数。

一开始，容易想到当a1为1或者an为n时，必然成立，但是观察到，最后一个样例并不是这样，也成立，所以进一步思考成功的本质。 我们可以发现这肯定首先时a1<an，下证a1<an时必然成立。 因为a1<ai的话，可以删去ai，使得a1的下一个数必然小于a1，同理可以让可能有的a2下一个数小于a2。 这样操作完，我们再操作an，因为a1<an，那么中间这些数显然也小于an，都可以通过操作一一删去，就是可以成功。 所以，只要a1<an，这个全排列就是成功的。

B. Plus and Multiply

题意： 设定一个只要x在集合中，x*a和x+b就在集合中。（初始有1） 给出n, a, b，请问n在不在这个集合中。

思路： 把+b看成+y*b（y取自然数） 那么xa可以看成(x0 + y*b)*a，也就是ax0 + yab。 多次后，因为两个操作顺序不定，但是b之前一定只是一个系数y，为(a^x)1 + yb，即a^x + y*b。 考虑到数据范围可控，我们枚举x的可能值，看n-这个值后是否能被b整除即可。

注意！特判a == 1的情况。

B. Codeforces Subsequences

题意：

思路：

给codeforces这个字符串加入若干字符，使得新的字符串中codeforces作为子序列出现的次数大于等于k。

我们不难发现平均的去放是最大的。 先看两个数的情况，大的数加一，结果增加的是小的数； 而小的数加一，结果增加的大的数。 10个数同理，得证。 1~n个位置循环去放，知道cnt[i]的乘积>=k

C. Team

题意： 有n个0，m个1，求一个可能的序列，使得0不相邻，1不三个连一起，若不存在输出-1.

思路： 首先是无解的情况，先约束0的数量，01010...1010是0最多的情况，n > m+1无解； 再约束1的数量，110110...11011是1最多的情况，m > n * 2 + 2无解。

再代码小小的分类讨论即可。

D. Epic Transformation

题意： 给出一个a序列，经过若干次选择两个相异的数删除后，求最小的序列大小。

思路： 不难想到，最终序列的大小，只与出现次数最多的数的次数有关，因为其他的数，都可以与最大的数匹配减小。 这个临界值为总数的一半。 当n为偶数时，最小值为max(0, mx * 2 - n)； 当n为奇数时，最小值为max(1, mx * 2 - n)。

G. Special Permutation

题意： 给出n，找出长度为n的排列，使得相邻两数的差值[2,4]

思路： 根据样例，发现若为4的倍数，可以以4为循环节，一直走下去，所以，不妨给n%4做分类讨论，特判第一段，且使其末位，可以和后面的循环节形成合法相邻。 循环节 3 1 4 2 余0 3 1 4 2 余1 5 3 1 4 2 余2 5 3 6 2 4 1 余3 7 4 2 6 3 5 1

*[C. Number of Ways] (https://codeforces.com/problemset/problem/466/C)

题意： 给n个数，在不打乱顺序的情况下，找到i, j(1<=i<j<n)使得1,i[j+1,n]的区间和相等的取法有多少

思路： 一开始想着用一个式子解决，但实际需要模拟。 容易发现，整个数列的和不能被3整除时，是没有答案的。 从后往前记录后缀和等于res/3的点，把他们的cnt赋值为1，再从后往前做累加操作，得到i位置以后，能符合res/3的个数。 再从前往后累加，只要满足，最终答案加上cnt[i+2]（只要确定了开头和结尾的和为res/3中间的和必然为res/3，但也要为其有一个位置，所以是cnt[i+2]

D. Same Differences

思路： b[i] = a[i]-i，然后记录b[i]的各个值出现的次数，结果就等于值次数的选两个的组合，即cnt*(cnt-1)/2（我采用map实现记录）

A. XXXXX\

思路：

1. a[i]都能被x整除，无解
2. sum不能被x整除，n
3. sum能被x整除，但a[i]不全能被x整除，从左到右和从右到左遍历找到第一个不能被x整除的a[i]的位置，用来更新res,即res = max({res, p - 1, n - p});