貌似这次每试4题……
Day1
T1 裸AC自动机…… 规模极度奇葩的10^7,也就是要在1秒内要读入20MB的东西还要把AC自动机建起来还要回答查询内存还只有256M尼马这不是坑爹吗…… 貌似后来评测时候出题人也意识到了不靠谱，只测了规模10^6的数据。
T2 题目大概说要把一个图的点划分成两个点集，使得两个导出子图的每个点都有偶数度数。可以考虑某个点属于哪个子图，然后发现要满足的条件就是异或方程组…… 于是高斯消元…… 规模2000，但只要压60位，1秒内卡过没问题。貌似数据再次出问题，后来重测了
T3 物理题…… 给定起点和终点，要求找一条类似最速降线的东西…… 各种乱搞…… 貌似题目没说清楚到底中途能不能低于终点然后再回上来…… 我理解错题意了但还是骗到不少分囧……
T4 给定一个棋盘(N<=8,M<=2^31-1)，其中一些格子被挖掉了(<=100)…… 然后每个好的格子上站着一个小盆友，要和上下左右中的两个小盆友拉手，不可以自己拉自己的手…… 问有多少种方案…… 看到N<=8显然状压，然后M规模大就是矩乘…… 推出矩阵乱搞。但是爆搞的话复杂度是(2^8)^331100的，不可接受…… 然后想到一个方法就是，连续一段矩乘的时候，其实不需要快速幂…… 先倍增预处理出matrix的幂是2次方幂的结果，然后发现矩乘时候只是一个向量连续乘O(lgM)个矩阵…… 那显然如果快速幂先把后面lgM个矩阵乘起来就傻掉了…… 直接一个一个乘过去，每次都是一个向量乘以一个矩阵，于是时间复杂度就变成(2^8)^231100了，可以接受…… 但发现倍增预处理那部分还是(2^8)^3*31的，照样被卡（不知道用时间复杂度低于3方的那些奇葩矩乘能不能卡过去……）…… 然后就不会了…… 标程貌似用了一个奇怪的方法，把矩阵边长变成了2^7，然后再倍增搞…… 没仔细看标程 UPD: JZP大神跟我讲了标程为什么矩阵只有100多…… 因为最后必然是很多回路，所以考虑某一列，只有偶数个1的状态是有效的，这样有效状态就只有100多了。
Day2
T1 给定一个带权无向图G，然后要你找一条边e，要求最大化G加上e这条边后的新图的最小权值的割边的权值。先边双联通缩点，然后发现得到一棵树，然后二分答案，然后考虑加上一条边e的效果就是e的两个端点的路径上所有边都废了。于是就转化成了，一棵树上能否用一条链覆盖一些给定边。这个可以树形DP各种乱搞O(N)能判出来。于是就O(NlgN)了。当时我对拍完后才发现系统栈太小，点数1W就直接爆栈，然后离考试结束只有不到半个小时了，感觉改非递归会蛋疼致死而且时间也不一定够，又感觉评测机设计不咋的，于是果断程序开头加上{$M 1000000000}…… 果然评测软件没有发现我这个非法行为…… 于是就90分了，有个点TLE了…… 貌似数据弱，直接双联通缩点后输出树上第3小边权值就能AC尼马
T2 比较水的题目。3方DP显然，然后对着转移式子乱YY乱推倒，然后YY出来可以用部分和各种乱搞优化掉一维。于是平方了…… 取模的数P<=255没看出意图。估计可能可以得到一个n*P的做法，不过n^2的做法对于给定的时限已经足够了，就没细想
T3 乱搞题…… 首先发现长度N的一个环，任意染M种颜色，本质不同的方案数（旋转重合视为本质相同）就是裸Polya，答案就是1/n sigma { M ^ gcd( n , i ) } 1<=i<=N…… 然后这一步就算可以了。下一个问题就是长L的环染色，相邻颜色不同的方案数（不允许旋转），这个我考场直接找规律…… 然后发现是个递推式，于是直接矩乘就行了…… 到这一步就有80分了…… 100分的话N的规模有10^9，这也是可以处理的（虽然考试时候我没想到）…… 我们任务就是求sigma{M^gcd(n,i)},于是枚举N的约数，然后gcd(n,x)=k的x的取值数量就是欧拉函数…… 然后就没有然后了……
T4 数据结构题…… 题目比较麻烦，就是给定一个不超过2行，不超过3列的黑白棋盘…… 然后每行、每列都有一个按钮，按一下就会导致这一行（列）反色。然后定义某个棋盘状态是“不好”的。然后你被要求维护一个按钮序列，定义这个序列里某个元素a[X]是“不好”的，当且仅当从第一个数顺次按按钮按到第X个数后，得到的棋盘状态是“不好”的。然后被要求支持区间修改和查询某段区间内有多少个元素是“不好”的。 首先显然一个按钮按两次等于没按…… 然后发现按按钮的状态只有2^5种…… 然后每一种都决定一个棋盘状态…… 然后发现按钮状态的合并就是异或…… 于是用线段树维护，每个节点维护一个长度32的数组表示当前区间的前缀能得到某个状态的数目。区间修改就是懒标记，查询就是各种乱搞…… 可以做到O(32lgN)…… 也可以块链，这样就是O(sqrt(N))，因为没有32这个常数，实际速度貌似差不多…… N=100W不用怕，因为操作只有12W，关键点只有24W，离散掉就不TLE不MLE了……