CF1383DE（F卡常了）

AtCoder Beginner Contest 174(atcoder) pros:6/6/6 rk:536

atcoder abc 174

cf round 661

Codeforces Round 659 1E

标签：dp

题意：有一个01串S，长度为n，每次可以选相邻两个数，将这两个数替换为他们的或运算值，求n-1次操作内能够得到多少个不同的串（mod1e9+7）。

思路：考虑对于每个合法结果，一定存在一个最小的i使得我们可以通过操作s[1-i]得到这个字符串。令f[i]表示最短匹配为s[1-i]的串数，分别考虑这样的串下一个填0和填1进行转移。

 设原串为p，则
 填1：p+1的最短匹配一定是s[i]向后找的第一个1
 填0：若p的最短匹配是s[1-i]，则s[1-i]的末尾0数一定和p相等，因此若s[i+1]是0，则最短匹配的位置是i+1，否则设s[1-i]末尾0数为k，最短匹配是i后面第一个连续k+1个0。

这样就可以O（n）计算f[1-n]，注意并不是所有f[i]都可以作为答案，因为后缀0数不能超过s串的后缀0数

comment:这周做的最有意思的题，推荐给大家

cf 1380e Inverse Genealogy

tag：构造 分治

题意：对给定的n,k，构造一颗完全二叉树使这棵树的n个节点中，k个点满足其一个儿子所在子树大小是另一个的至少两倍

题解：

观察一下后可以发现符合题意的树的这些性质：

1.有奇数个点，且k不大于(n-3)/2

2.当且仅当2^x=n+1时，可以有k=0

3.(n,k)可以向(n-2,k-1)转化

又可以发现，k=1时，只要n+1≠2^x,按顺序从根向下在每层放满点就可以满足要求，问题变成怎么放点能使(n-2*k+2,1)转变到(n,k)

对n-2*k+2≠2^x的情况，我们要在不破坏之前结果的情况下构造。由(n-2*k+2,1)的构造可以知道满足题意的点所在的位置，在维护之前大小关系的情况下放点。 n-2*k+2=2^x时，不存在(n-2*k+2,1)的构造，可以先提前留下几个点，然后当做上面的情况继续构造，最后将这些点放在不影响结果的位置

comment：有点麻烦的构造题。。没有看到能比较好的做最后一步转化的方法

cf 1382e mastermind

tag：贪心

题意：给n,x,y和一个长n的数组，数组元素的大小为1到n+1间的整数，求另一个数组，元素大小同样在1到n+1，两个数组元素相同的位置有x个，重新排列后两个数组最多有y个相同位置的元素相同

题解：首先对出现的元素进行计数，显然要把x的指标优先给数量多的元素

这样还剩下n-x个元素，对于这n-x个元素，两个数组在不重新排列前不能有匹配，对于一某种元素c，假设它有k个，如果2*k>n-x，那么必然有一部分元素要变成其它的元素，n个位置有n+1种元素，所以这个用来替换的元素是一定存在的，而如果出现这样的情况，n-x这一部分在重排之后至多能匹配2*(n-x-k)个，也就是要2*(n-x-k)>=y-x，化简得2*n-x-y>=2*k，不满足则无解

对于有解的情况就比较简单了，对n-x这部分的元素排序，然后旋转(n-x)/2之后放进去，再把n-y个位置的元素换成不存在过的元素就可以了

comment：很妙的题，尤其是对于无解的判断