CF1383DE（F卡常了）

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

atcoder abc 174

没有专题

没有比赛

补题（板子） 牛客第五场B
链接
题意；给边带权的树，可以连边或删边，要求始终连通且形成的环异或和=0，求最后图的最小权值和
思路：对原图的树，可以把边权用所连点的权值异或和来表示，转化成异或最小生成树
类似的模板题：链接

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 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：很妙的题，尤其是对于无解的判断