cf1200构造15道

最近做构造，想对比下先做后看答案归纳，留下思路之后直接看答案归纳，然后再统一检测，还有直接看答案，归纳，检测三种方法哪种效率高些，于是先做个十五题试试第一个方法，花3天写了15道构造，等到归纳的时候已经有点忘了，要看答案来回忆一下，感觉是不如留思路之后对照答案。但是最终还是能归纳出一些简单东西，效果还是可以的。
1.B. Same Parity Summands
Problem - 1352B - Codeforces
#分类构造 #数论 奇奇得奇，奇偶得偶
题目提到：如果有多个答案，请打印其中任何一个，可以考虑构造

已知一个数n，求是否能够把n分解成k个的奇偶性相同的元素
如果k个元素有共同的奇偶性，k个元素相加可以看作是k乘一个奇数或偶数。
且k个元素相加等于n，可以看作k与一个奇数偶数的乘积等于n
因为奇偶数相乘根据情况有不同结果，所以分类构造。
2.B. Sorted Adjacent Differences
Problem - 1339B - Codeforces
#直接构造 #排序
序列构造涉及到大小关系时要排序。
已知n长度的序列，要对这个序列排序使得从第一项到最后一项相邻项差值的绝对值递增。
如果要构造一个相邻项差值递增或递减的序列，可以考虑用一个有序的数组，中间元素往两边差值递增。两边元素向中间差值递减
两边往中间，则两个数的差值越来越小。
3.B1. Palindrome Game (easy version)
Problem - 1527B1 - Codeforces
#回文串 #博弈 #构造 #字符串
有一个字符串，有两种操作，
1.选择一个0变成1，
2.反转这个字符串，如果原本是不回文的。
每次翻转消耗一美元，消耗美元数量少的获胜，求获胜方。
修改回文串单个元素，可以考虑奇数长度时，n/2+1这个元素自己与自己回文这个点。
博弈，从小情况开始讨论，往后的复杂情况可以被拆分成小情况
4.C1. k-LCM (easy version)
Problem - 1497C1 - Codeforces
#最小公倍数 #分组构造 #lcm
三个数相加，和为n;
lcm（a,b,c) <= n/2;
让lcm内的元素满足某条件，可以考虑：
1）元素互质时，lcm等于乘积
2）元素相等
3）元素为1，2，4与其倍数
5.D. Districts Connection
Problem - 1433D - Codeforces
#图论 #归纳构造
有n个地区，属于ai个匪帮，要把这些地区用n-1条无向边连接起来，同一匪帮的两个区域不能直接通过一条边连接，求是否有解决方案。
同一匪帮不能连在一起，则容易想到只有一个匪帮则无解
此时数学归纳，尝试讨论2个匪帮，可以把一个全部连到另一个，然后另一个全部连到前一个。
3个匪帮，因为匪帮间相互独立，所以第3个匪帮也可以实行像第一个匪帮的操作，全部连到另一个匪帮即可。
6.B. Jumps
Problem - 1455B - Codeforces
#归纳构造
对0第i次操作可以+i，或者-1，求得到一个n的最少操作数。
考虑一直+i，直到>=n，然后考虑把其中一些操作换成-1，来凑出一个n
比如如果得到n+2，可以少掉一个+1的操作，然后多一个-1的操作。此时分析这种操作的前提，因为得到的是中间的值，所以要往两边归纳。往后看，因为i的差值只有1的所以可以得到n+3，n+4……n+k。
往前看，得到n +1 时，由于+1已经最小，所以只能另外构造，化成n+2-1的情况，比n+2多一步，要i+1步。
如果是n+1，就只能凑出n+2之后再-1了。
7.D. Corrupted Array
Problem - 1512D - Codeforces — 问题-1512D- Codeforces
#排序 #分类构造
序列构造涉及到大小关系时要排序。
有一个n+2个元素的数组b，这个数组b中
n个元素是a中的元素，1个元素是a的总和，1个是任意加入的元素。
要构造一个a数组

总和一定是比a中所有元素都要大的，
b数组排序之后，就可以把这个总和元素锁定在n+1和n+2的位置，
因为新加入的元素大小未知。所以要讨论
x > sum
x < sum
分类构造，看是否能满足前缀和的要求。
8.C. Mocha and Hiking
Problem - 1559C - Codeforces
#图论 #分类构造
有n+1个村庄，2n-1条有向边，有n-1条是从1连接到n的，其余n条是连接前n个村庄n+1村庄的。
求构造一条路线，经过所有村庄，每个村庄只经过一次。

由于每个村庄只能去一次，且道路是从1到n的，
所以只能从1开始，或者从n+1开始，然后去到1
对于什么时候去n+1，
只有三种情况：
1.直接从1到n，然后去n+1结束，ar[1] = 1
2.从n+1开始，然后去到1，再一直走到n ar[n] = 0;
3.从1开始，中间i点去到n+1，然后返回i+1点。 ar[i] = 0 && ar[i+1] = 1;
发现如果不满足1，且不满足2时，必然会满足3.所以必定有解。

9.C. A-B Palindrome
Problem - 1512C - Codeforces — 问题-1512C- Codeforces
#回文串 #字符串 #模拟 #直接构造
1-n下标回文串模拟时常用i，n-i+1的指针，
回文串构造一般要考虑奇数长度的中间点。
有一个由0，1，？组成的字符串，以及0的个数，1的个数
？是未知的0或1
求是否能构造出满足条件的字符串。首先先判断一遍已知的串是否已经可以确定不是回文串了，
找到数字，然后看另一边是否相同或者为？，如果是？就改成一样的数字，否则如果不相同就无解。
然后，还有一些可以直接消掉的问号要替换成回文的数字。
然后统计处理好的串里的数字数量，直接sa–sb–就行，如果得到了负值就是无解了。
然后遍历字符串，找到？并修改。
上面的操作不用考虑特殊中间点，这里的替换就要了。因为是一边替换，一遍修改数量
可以考虑通过i 是否 = n-i+1来判断是否是中间点。如果此时sa，sb不是奇数的话就是无解了，否则谁大于0谁上。
其他的情况，谁大于2谁上，然后把？？？为什么是大于2的上，然后把回文串两边都修改了，前面不是已经把已有的数字给减了一遍吗。如果这里修改的一边是数字，一边是？怎么办
这里卡壳了。
回看了一遍题目和代码懂了：前面处理已经把串i和n-i+1回文的形式了，所以这里遇到一个？就可以直接把n-i+1也修改，并且sa-=2；

10.A. Common Prefixes
Problem - 1384A - Codeforces — 问题-1384A- Codeforces
#直接构造 #字符串
有一个长度为n的序列ai，要用小写字母构造n+1个字符串，第i和i+1个字符串的公共前缀长度为ai
首先考虑长度，找到最大的ai，字符串要构造的最大长度就是ai了
i+1个串然后只要在i的基础上，在ai处把字符修改一下就会有一个与i长度为ai的公共前缀。

11.B. Reverse Binary Strings
Problem - 1437B - Codeforces
#直接构造 #字符串
有一个偶数长度的01串，1和0各有n/2个，可以对字串反转，求让串变成101010或101010的交替形
式的最小操作次数。
翻转操作，只有两端的元素排列会被改变，所以，每次操作必然可以让连续的1或0减少一个长度，然后让一个0和1配对。
总共要配对的次数就是所有1的连续段长度或0连续段长度的最大值。
12.B. Before an Exam
Problem - 4B - Codeforces — 问题-4B- Codeforces
#直接构造
有一个天数，还有一个总学习时长，和每天最大学习时长和最小学习时长限制。
要把学习时长分配到每天，
构造一种方案让每天的学习时长符合要求或无解输出NO

因为数据比较小，只有1e2级别，所以直接让每天的学习时长从最小值开始逐个递增，直到够时长然后打破循环输出。
考虑这种操作的前提条件是总时长在最小学习时长的总和和最大学习时长的总和之间。

13.B. M-arrays
Problem - 1497B - Codeforces — 问题-1497B- Codeforces
#直接构造 #数论
有一个长度为n的数组和一个数m，定义了一个m数组，如果数组里相邻的元素的sum可以被m整除，或者数组只有一个元素，则被称为m数组。要求对数组划分，使得每一个数组都是m数组的最小数组数量。

把数组里的全部元素取余后用哈希统计数量，就得到了方便用来研究整除关系的数据。
首先余数为0的全部分在一个数组ar，如果有则res++
然后遍历1-m/2，如果ar[i] == ar[m-i] ，则这两种情况可以全部放在一个组里。res++，前提条件是ar[i],ar[m-i]存在。
如果ar[i] != ar[m-i] ，则可以分出部分在一个组，因为只是相邻总和被m整除，所以可一个多分一种元素出去。多出来的部分单独成组。res += abs(ar[i] - ar[m-i]);

divisible.可分的

14.B. Paranoid String
Problem - 1694B - Codeforces
#字符串 #归纳构造
当时完全看不懂的题，现在看答案看懂了。
有一个字符串，定义paranoid字符串，一个长度为m的字符串，如果有子串为01就可以把子串替换成1，如果为10就可以把子串替换成0。若可以通过m-1次这样的操作来获得一个长度为1的字符串，就把这个长度为m的字符串叫做paranoid字符串
求给定字符串中有多少个paranoid字符串

首先可以知道长度为1的子串肯定是paranoid字符串，所以字符串有多长就至少会有多少个paranoid字符串
然后增加长度，发现如果新增的数和前一个数不同，包含这个新增数的所有子串就一定是paranoid字符串，
构造出一种操作，遍历字符串，当前ar[i] != ar[i-1]，则 += i + 1，就是在原来的基础上再多加一个长度，会新增i + 1个子串。子串数量是1 * 2 * 3 * …… * n + 1（对于0到n-1下标的字符串）
不太确定
否则如果相同的话，就是新增了一个长度为1的子串。

15.B. Prinzessin der Verurteilung
Problem - 1536B - Codeforces
#枚举 #暴力 #字符串
有一个字符串，定义mex为字典序中不是给定字符串子串的第一个字符串，
枚举字符串然后find函数查询就行。