Codeforces 894D
题意：给出一颗带边权完全二叉树，有$m$个询问，每个询问有$A_i,H_i$，求从$A_i$出发分别到其他点$x$的$H_i-dis(A_i,x)$和

待更，这题不好讲

Codeforces 879C
题意：给出一些位运算操作，求简化位运算。
可以发现所有操作都可以用三大操作完成。
那么假设输入二进制数全是0($a$代表的数)或者全是1($b$代表的数)
那么根据题目模拟一次，最后得到了处理的结果
那么可以得到，原二进制数上如果是0或者1，之后的结果有几种情况考虑：
1、这一位原来为0时变成了0，原来为1时变成了0：进行$and 1$可以完成
2、这一位原来为0时变成了1，原来为1时变成了0：进行$xor 1$可以完成
3、这一位原来为0时变成了0，原来为1时变成了1：不用进行
4、这一位原来为0时变成了1，原来为1时变成了1：进行$or 1$可以完成
(代码注释有对应情况，可以参照)
之后再一起操作就行了

hdu 4057
一样的思路，设$dp(i,j,S)$为考虑了$i$个字符，在自动机$j$点上，基因状态$S$时的最大权。
转移则$dp(i,v,S | zt(v)) = max(dp(i - 1, j, S) + \sum val_i \in zt(v))$
注意$\sum val_i \in zt(v))$，$S$如果相应位置有则不用累加

Codeforces 892C
题意：给出$n,x$，求构造$n$个不同的数使得其异或和为$x$.
注意两个特判，具体看代码。
Xor的性质：$x ⊕ 0 = x, x ⊕ x = 0$
那么我们可以构造出$n-3$个数，分别为$1,2,…,n-3$，并记录异或和$a$
然后剩下三个数，分别输出两个不同的极大数(比$n$大), 以及他们的异或和与$a$的异或值

这样相当于前面的被后面的异或和抵消(异或和满足右结合律)，然后两个不同的极大数是为了防止异或和重复

Hdu 2457
和Bzoj 1030思想差不多，就是方程不一样
这里方程是设$dp(i,j)$为考虑了$i$个字符，在自动机的$j$点上的最小代价
$$dp(i,v) = min(dp(i,v), dp(i-1,j)+(c != S_i))$$
其中$v$点是$ch(j, c)$(不存在则走失配边，直到有为止)，即从$j$点转移到$v$点
$S$是带修理的主串

bzoj 1030
题意：构造主串长为$m$，使得主串包含所有的$n$个模式串，求主串有多少种可能性。

首先可以转化问题，主串的所有可能性个数$26^m$，所有求出不包含所有的$n$个模式串的主串可能个数，补集转化即可($26^m-$不包含个数)。
然后多模式串想到AC自动机，方案数想到DP。
先把模式串建一个AC自动机，然后每个点如果是串的末尾，则该点标为危险点(即说明根到这个点路径非法，危险点不转移)，注意如果失配边指着危险点，那这个点也是危险的。
然后设$dp(i,j)$为考虑了$i$个字符，现在在AC自动机$j$点上的方案数。
$$dp(i,v) = (dp(i,v) + dp(i-1,j))$$
其中$v$点是$ch(j, c)$(不存在则走失配边，直到有为止)，即从$j$点转移到$v$点
注意$dp(i, x)$中每个$x$互不影响，即没有先后关系，所有$dp(i)$都是从$dp(i - 1)$转移而来的，AC自动机上的点只是作为一个方向指引
如果主串字母出现不在AC自动机上的字母，那么v是会到根节点(0)

Codeforces 892D
题意：给出一个$a$数组，要求一个$a$的排列$b$，使得两个数组任意位置元素的和不同。
做法：使$b$中每个数都大于$a$(最大值必须对应最小值)，那么就能保证两个数组任意位置元素的和不同。
证明：
1、$b$中每个数都大于$a$，那么两个数组任意位置元素的和不同
2、最大值对应最小值为什么对？因为$k$小于$n$。显然在$a$中不选完所有元素，就算包含了最大值，也不会相同。

模板及讲解

AC自动机是什么

由Aho-Corasick发明的一种多模式串匹配算法，基本思想为在Trie上KMP。

AC自动机解决什么问题

AC自动机解决多模板匹配文本串问题。复杂度$O(\sum len_i \times$ 字符集大小$)$
($\sum len_i$ 即为所有模式串总长(可能比Trie树大小大)，字符集大小为出现的字符种类个数)

AC自动机的实现

例题：Hdu 2222

题意：第一行输入测试数据的组数，然后输入一个整数n，接下来的n行每行输入一个单词，最后输入一个字符串，问在这个字符串中有多少个单词出现过。

原理 (求失配函数)

AC自动机是在Trie树上加上失配边完成的。如图所示为加入hers, hehe, he模式串的情况。

可以看出在5到6(已经匹配heh如果)失配，则回到1。6失配同理。
与KMP算法有类似之处，所以AC自动机的失配函数与KMP相似。
AC自动机失配函数由BFS可以求得。具体可以看下列代码

代码实现

程序主要函数：$insert$(插入单词), $find$(进行匹配), $getFail$(求失配函数)
其中$insert$(插入单词)为Trie树部分。

坑点：
1、 sz初始化为500000不是500000 + 5
2、ch从0开始清空

$Day 0$
晚上什么也没有复习……考试前该复习的也复习了……和学长们一起玩了一晚上……

$Day 1$
早上吃完饭就到六中考场了，然而今天的解压密码：
Bu%Wangchu&xin!!!
不忘初心，好的。
t1一看居然不会？smg，赶紧看T2，去年的D1T2是最难的，今年D1T2一看我还以为要写编译器qaq，结果一看是暴力然后毫不犹豫就想DFS了……
然后看T3，暴力分可以拿30……
然后手速把T3写完过了，不管直接打T2
然后写了一大串代码……谁叫我打DFS呢……这不就是stack模拟吗……蠢了
然后之后大样例过不了，代码魔改来都看不懂了，然后果断放弃看T1。这个时候考试时间已经过了一大半了
看了看T1，毫无思路，然而暴力分也只有30分（今年noip真tm暴力分少啊）
然后做死想二分优化暴力，这不是有序数列二分个鬼啊。最后到时间了。
Day1期望分数：0+30+30=60完败。
出来之后问dalaoT1居然打表找规律？$ab-a-b$??当时我就炸了，然后发现t2的暴力也很多人切了，感觉这次要GG。
晚上继续颓。

$Day 1$
又来到考场，解压密码stm什么alphaGo……
t1什么鬼立体几何？好吧仔细一看就是图论水题。10min秒过。
t2这什么鬼怎么连暴力都不会打？跳
t3暴力分有40还是50吧，直接就打了，当时脑子炸了什么都想不出来。
然后发现t2 10%的数据可以求树的重心，然后就打了(直接暴力都行打什么重心啊)
然后就GG了，一直看t2怎么解。中途算暴力复杂度还算错了
Day2期望分数：100+10+40=150
出来之后T1貌似有人不会？然后居然t2可以prim水……而且据说暴力70？我复杂度算错了没打……
真的完败……这次分数线肯定比上次高
下午回校。

综测：Day1:35分，Day2:150分
连二等都没有，真的是要反省一下了。

Day1
T1：不要忘记了水法打表找规律
T2：暴力要打过，能枚举解决就不要搜索
T3：暴力要做对，不要挂
Day2
T1：多做题才能见题型
T2：暴力的时间复杂度不要误算，谨慎地算
T3：要多想正解，不要脑子僵化
整体：考场上不要紧张，要沉着，不要患得患失，要好好分析问题，切勿粗心/想当然

caioj 1114
边权型树形DP，选$Q$条边等价于选$Q+1$个点。
那么边权转到点权上，做个普通树形背包即可