K Kate’s 2021 Celebration
LYF 签到
M Miser
签到题 但由于脑子原因没读懂洋文wa了好几发
E Easy Measurements
WD 好像是简单题
A Almost Balanced Tree
LYF & WD 树、构造
题意：给一堆1和一堆2，每个当一个节点，要求搞成一颗树，使得左右子树的重量（指权值和）最多差1，输出方案
解：(引用LYF)
可以发现一个性质：只要某个子树中有2，就可以把这个2放在子树根节点
证明：考虑相邻两棵子树之差和2的位置，有三种情况
- 相邻两个子树和相同；
- 相邻两棵子树和差1，且2在较大的那棵子树
- 相邻两棵子树和差2，且2在较小的那棵子树
前两种情况比较显然，第三种情况可以把这个2和较大子树中任意一个1交换，变为第二种情况
有了这个性质之后可以得到一个填充策略：如果子树中还要填2，那么可以直接把这个2填在子树根上，可以保证是最优解之一，也就是优先填2，2填完了或者总和=1的情况才填1。
当知道了子树之和以及子树根节点的值以后，根节点的左右子树之和也分别可以确定了，对于左右子树，采取同样的策略
从根结点开始bfs，bfs过程中如果发现没东西能填了（1不够了）就直接输出-1
C Color the Tree
WD
D Down We Dig补
WD&ZRC
题意：给定一个$8\times n(n\le300000)$的01矩阵，从最上面一行(一行8个数，但所在位置是一维的，即在第几行)开始出发往下走，两个人轮流走。对于每一步，假设当前处在第$i$行，则可以走到$j-i\le difference(a[j],a[i])$的所有行，其中$difference$表示01矩阵中第$i$行和第$j$行相同的位数（显然这个位数小于等于8）。轮到要走的人走不了了就输了。问只有最上方一行、只有最上方两行……有全部n行情况下的必胜状态。
解：
如果只考虑全部n行情况下的推导，其实非常方便，就是常规sg函数的博弈题。如果题目是从下往上加，也非常方便，因为推导时候算出来的都还可以用。但是题意这样每次向下加一行就会影响到上方所有行的必胜状态。不太好做。
注意到题目的一个特性就是有一维很小，只是8，而且每次最多也只走8行。考虑状压的可能性。设$f[i][x]$表示第$i$行下方的必胜状态为$x$时$i$的必胜状态，则可以算出状态数共有$n\times 2^8\le76800000$个，即使全都推出来也不会爆炸。然后递推的过程脑子想想是显然的，每次只需要暴力求出后八行的胜负情况结合上面的结果向下递推即可。但是实现是艰难的，细节比较多，因此比赛时最后还是wa了。
L Lookup Performance补
LYF会补的