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:这周做的最有意思的题，推荐给大家