Day1
差不多晚上才到，去吃了火锅，菜里都有花椒，晚上在寝室整理自己的东西，了解了一下制度。
Day2
上午先做了一下昨天的题目，难度还行，补了 \(Ice-cream Tycoon\) 和 \(New Year and Conference\)，下午是金天讲课，知道了许多有意思的DS转换，难度为单峰。
中午和yjf和hhx去外面吃饭，吃的云吞，迟到了，以后中午再也不去外面了。
Day3
朱富海教授给我们上课，从中国剩余定理讲到群论等一堆，就一开始的听懂了 (╬▔皿▔)╯，后来就自习了。
Strange Limit
题目大意
给你 \(p\) 和 \(m\) ，求 \(p^{p^{p^{p……}}}\ mod\ m!\)
思路
有 \(n\) 个 \(p\)， \(n\) 为无穷大,也就是递归里套一个指数循环节，然后因为 \(n\) 趋向于无限大，那么当前要 \(mod\) 的 \(x\) \(\mu (\mu (\mu (m)))\)，也在一直缩小。
如果当 \(p\ mod\ x=0\) 的时候，就是返回个 \(p^p\ mod\ x\)，再往上就是 \(0\) 的几次方了，已经没有影响了。
GCD Determinant（SP4195）
题目大意
有 \(n\) 个正整数 \(a_i\) 和一个 \(n\times n\) 的矩阵，矩阵中 \(i\) 行 \(j\) 列的元素为 \(gcd(a_i,a_j)\)，求矩阵的行列式。
思路
结论为 \(\phi a_1\times \phi a_2\times \phi a_3 \times ……\times \phi a_n\)。
(可以先暴力算出矩阵的行列式，然后消掉)
Remainders Game（CF687B）
题目大意
给定 \(n\) 个正整数 \(c_i\) 和 \(k\)，假设你知道一个数 \(x\)，问能否从 \(x\ mod\ c_i\) 推出 \(x\ mod\ k\)。
思路
用中国剩余定理，所以我们知道只要 \(c_i\) 中包含了所有的 \(k\) 的质因数就可以推出，但把每个数全部分解质因数明显不可以，其实只要 \(c_i\) 的最小公倍数 \(mod\ k=0\) 就可以了，注意每次还要 \(mod\ k\)。
Day4
上午考试，下午讲题
T1
签到题，能发现 \(T=2S+1\) 所以在 \(T\) 中肯定出现了 \(S\)，我们就在 \(1,2,n,n-1\) 的位置扫一边，看看其他位置是否存在，最后判个重。
也可以 \(hash\) 做，就是把上面的方法的扫变成的判哈希值，但考场很多人被卡了。
T2
这题挂了，我将问题离线化，然后先把边连起来，权值为连边时间，然后预处理出两两相连的， \(map\) 维护时间，对于每个两两相连，我们分别找出连接它且不连接另一点的点，相连，权值取 \(max\)，对于每次询问，答案为权值前缀和。
正解为将每个互相关注的的看成一个集合，如果分别有边相连，就把这两个集合合并，用 \(set\) 维护答案，合并用启发式合并即可。
T3
考场没想出来，这里拜谢zyb爷爷场切
一眼dp，我们不妨设 \(f_{i,j}\) 为 \(A\) 菜已经完成了 \(i\) 道，\(B\) 菜完成了 \(j\) 道，它的转移式就为 \(f_{i,j}=max(f_{i,j-1},f_{i-1,j}+sum_{i-1,j})\) 其中 \(sum\) 为前缀和。
但是 \(O(nm)\) 肯定是不行的，考虑一行的 \(f(x)\)，明显它肯定具有单调性，所以我们差分一下，差分数组肯定是非负的。
设这个差分数组为 \(d_i\)，我们如果在 \(i\) 处加了正数它对后面是没影响的，但是加了一个负数使得它变成的负数，就会使得后面的全变成 \(0\)，所以我们可以用线段树二分实现
下午还是朱富海教授讲数论，这次讲的更开放了，更听不懂了，自习得了。
Day5
上午是丁晓漫讲图论，似乎是讲的最好了，学到了竞赛图（”完全有向图“），它的性质不少，能够解决形如多人打比赛的问题，还有重环用异或使它们变成一个环，满足奇偶性，学到了不少好思路。
Fairy（CF19E）
题目大意
给出一张无向图，求删除一条边后此图变成二分图的所有删边种类 \((n\leq10^4)\)。
思路
虽然看起来 \(O(n^2)\) 能过，但其实是过不了的，我们知道，判断二分图的一种方式是判断有无奇环，所以问题变成了删去一条边后图中有无奇环，如果有环重合，可以用类似异或的逻辑将中间重复的取消，在看成一个环，明显发现只有偶环+奇环=奇环，然后就做完了。
Connecting Cities(AT_keyence2019_e)
题目大意
给定 \(N\) 个点的完全图图，每个点有权值 \(A_i\)。对于任何点 \(i\) 和点 \(j\)，这两点之间的边权为 \(w_{i,j} = A_i + A_j + D|i - j|\)，其中 \(D\) 为给定的常数，求最小生成树的大小。\((N\leq 2\times 10^5,A_i,D\leq 10^9)\)
思路
还是用 \(prim\) 或 \(Kruskal\)，但这题不可以全部连边，可以发现有些边是不必要的，先考虑把式子简化，我们如果确定这两个 \(i\) 和 \(j\)，可以变成 \(A_i+D\times i+A_j-D\times j\)。
既然 \(i\) 和 \(j\) 独立出来，那么只需要选出，右半部分 \(min{A_i+D\times i}\) 所对应的 \(i\)，左半部分 \(min{A_j+D\times j}\) 所对应的 \(j\)，将 \(j\) 与右半部分所有点连边，\(i\) 同理，这样边就只有 \(O(nlog_n)\)，最后跑 \(Kruskal\)。
Tournament(CF878C)
题目大意
有 \(n\) 个人，每个人都有 \(k\) 种能力值 \(a_{i,1}，a_{i,2}……a_{i,k}\)。
定义淘汰赛的规则如下：在没被淘汰的人中选出两个 \(i\) 和 \(j\)，并选择 \(d\in [1,k]\)。如果 \(a_{i,d} > a_{j,d}\)，则 \(j\) 淘汰；否则 \(i\) 淘汰（保证所有的 \(a_{i,d}\) 互不相同）。直到只剩下一个人没有被淘汰，则这个人是最终的胜者。
对于每个 \(i\)，需要求出如果初始参加比赛的人是 \(1,2,...,i\)，这 \(i\) 个人里有多少人可能成为最终的胜者。
\(n\leq 5\times 10^4,k\leq 10\)
思路
我们考虑两个选手之间的关系，如果一个选手能在某一项运动中战胜对手，那么就从他自身向对手连一条有向边。这样显然会出现很多环，于是可以缩点，将整张图缩成一条链。那么显然入度为零的环中包含的点数即为最后可能成为冠军的人数。
Day6
上午考试。
T1
\(T1\) 诈骗题，难度排序T4>T1>T3>T2，开了3h没开出来，直接暴毙。
先推式子
\[a_j\leq a_i+p-\sqrt{|i-j|} \]把 \(p\) 放一边
\[a_j-a_i+\sqrt{|i-j|}\leq p \]即对于每个 \(i\) 求
\[p=\max\limits_{1\leq j \leq n} \{a_j-a_i+\sqrt{|i-j|}\} \]考虑如何优化，发现答案具有单调性，所以我们可以分治找到每个答案。
T2
猫树
考虑对于每个区间记一个 \(f_{i,j}\) 表示 \(i\) 开头 \(j\) 结尾的不下降子序列数量。
然后可以滚一遍前缀和。
但是猫树的空间很爆炸，所以考虑离线处理猫树的整个操作。
T3
4399上有类似的游戏
结论为答案肯定是一直左右左右走，且如果走到走过的路一定不优。
所以我们对一个邻块连一条权值为 \(2\) 的边（来回一次），如果有冰块，向它的另一方向直到冰块都连一条权值为 \(1\) 的边。
最后跑遍最短路。
T4
逆天题，略。
这里我不得不提到 \(ChiFAN\) 了，考完疯狂hack别人，推销自己的，结果保灵，不好评价。
下午丁晓漫讲网络流，大部分建模都想得出，听到了几个不一样的建模，以及多个点捆绑的贡献如何建图。
Day7
去熊猫基地玩了，下午去抓娃娃（确信），抓了40大洋没抓出一个，zyb 20yuan抓五个，tnnd。
Day8
上午冯施源讲的杂题选讲，主张CF选题不选小于3300的，这是来成都遇见的第二个逆天老师。
T1卡常了我2h，似乎是 vector 常数过大，但试了还是 TLE 算了，又困难的做了几题。
Day9
上午考试，三黑一紫，你确定这是noip模拟赛？！。
T1
考场写寄了。
看题面就是一个01背包板子，发现 \(n\leq 10^6\)。
如何优化这个板子呢，发现售价异常的小\((\leq 300)\)，所以我们从这里入手。
我们对于每个售价进行决策单调性分治来进行优化即可。
T2
没开ll导致的，开了就A了。
我的做法是在随机数下比较优秀。
我们先想暴力，先更新再算区间和。
这个更新我们可以先预处理出哪些点需要更新，区间和我们用树状数组来维护。
复杂度在于更新次数，只要数组是一个降序排列的就寄了，但 JOI 似乎没卡，但洛谷上有人提出了此做法，于是加入了hack数据，所以这个做法在AT是能过的，但洛谷上不行。
T3
这里给出思路
我们考虑老鼠怎样走才是最优的，先设陷阱房为根节点，利于操作，一定是它走到了一个叶子节点，我们将它路上的岔路全分掉在把它放出是最优的，请自行证明。
老鼠很明显只能走一条岔路，所以它一定会选择最优的，但这条最优的有可能连接着老鼠的出生地，也有可能是先往上走一段路再走岔路。
这样我们就可以树形dp了。
(但我不会了)
T4
简单来说就是删去一些边问它是否还是二分图。
像极了一个线段树分治板子，这个做法也是可行的
但此题整体二分更为简单，但判断二分图仍是问题，所以我们想到使用可撤销扩展域并查集维护即可。
下午是冯施源讲字符串，先讲的关于kmp的好题，刷新了我对kmp的认知，它的kmp数组可以干许多事情，border也可以通过kmp快速求解。
然后讲的AC自动机，发现大部分人都不会，fsy直接嘲讽会平衡数为什么不会AC自动机啊，终于听懂的AC自动机的fail指针了，好耶。
中间休息时fsy竟然在打图寻，肯定没ykc强
Day10
下午还是冯施源讲字符串，上来先讲的后缀自动机，而后题目大多数和后缀自动机有关，完全听不懂qwq。
动物园(P2375)
题目大意
给一个字符串，定义 \(f_i=max\{x|S_{1...x}=S_{i-x+1...i},x\leq i/2 \}\)
求出每个 \(f_i\) \(n\leq 10^6\)
思路
可以发现 \(f_i\) 的定义类似kmp中的 \(nxt\) 指针，所以我们先利用kmp求出不符合 \(x\leq i/2\) 的 \(f_i\)，然后我们可以倍增出小于等于的 \(f_i\) 即可，复杂度 \(O(nlog_n)\)
字符串的匹配(BZOJ 1461)
题目大意
定义 \(\{a_i\}\)，\(\{b_i\}\) 相同，当且仅当它们离散化之后相同。
给定 \(a_1,...a_n\) 以及 \(b_1,...b_m\)，找到所有位置 \(p\) 使得 \(a_p,...a_{p+m-1}\) 和
\(\{b_i\}\) 相同。\(m\leq n\leq 10^5\)
思路
看起来就是kmp，但是我们无法直接知道一个数的排名，所以可以用树状数组或线段树来维护一个数的排名。
SZA-Template(P3426)
题目大意
Byteasar 想在墙上涂一段很长的字符, 他为了做这件事从字符的前面一段中截取了一段作为模版。然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列。一个字符可以被喷涂很多次, 但是一个位置不能喷涂不同的字符。做一个模版很费工夫, 所以他想要模版的长度尽量小,求最小长度是多少 \(n\leq 10^6\)
题目大意
首先能发现这个一定是这个字符串的 \(border\)，并且知道长度大于 \(|s|/2\) 的 \(border\) 一定都为等差数列，且一个字符串的所有 \(border\) 就是kmp中\(nxt\)。
Country(BZOJ 2061)
题目大意
有 \(n\leq26\) 个字符串变量，它们可以包含其他的字符串变量，也可以包含小写字母（这些变量用大写字母表示）。
举个栗子：A=greatglorycorrect，B=xx，C=leadusgo，D=ABC，E=DDDDdjh ，F=EEEEEgoodbye，数据保证定义是无环的。
给定一个小写字母组成的模式串，求某一个变量所代表的字符串里这个模式串出现了几次。模式串长度, 每条描述的长度 \(\leq 100\)
思路
很明显我们要把所有的大写字母改成小写字母，但暴力改肯定不行，尝试优化这个暴力，也就是记忆化搜索，对于每个大写字母，我们递归下去，对于一串小写字母，我们直接kmp查找即可。
Substrings in a String(CF914F)
题目大意
单点修改，每次问一个串 \(T_i\) 在 \(S[l,r]\) 中的出现次数。\(n,q,\sum{|T_i|\leq 10^5}\)
思路
看起来像一个字符串科技题，但标签打了二进制，可以用 \(bitset\)，我们用 \(ans\) 存下所有可能的左端点，当处理第 \(i\) 个字符时，\(res\&=(b[c[i]]>>(i-1))\) 即可，其中 \(c\) 为待匹配字符串，最终的 \(res\) 就是匹配的所有左端点，然后我们求出合法区间内 \(ans\) 中 \(1\) 的个数即可。
Day11
上午是罗凯讲杂题选讲，难度明显正常了，主要是一些好的idea
Animals and Puzzle（CF713D）
对于每个点可以算出以它为左上角最大的正方形。
二分答案，判左上角一个区间内的最大值。
Broken Tree（CF758E）
这题我和hhx想出了一个书上dp的做法，从叶子节点上传递这个点可以剪的值
如果传到一个点这个点承受不住就把传到这个点的值减去，如果这个值到了负数就输出无解。
如果有解，我们从叶子节点先减即可。
Omkar and Landslide（CF1392F）
可以发现 \(f_{i+1}-f_i\) 最多有一个为 \(0\) 其他全是 \(1\)，所以我们可以在一开始就能确定这个值
Day12
上午考试，三道计数题，出题人是不是……
T1
我们对每个点进行拆点，每个方向拆一个，然后每个点假定都有镜子来跑bfs，可以证明如果一个点被遍历多次，这个点一定是不优的。
T2
我们设 \(f_{i,j,0/1}\) 表示到第 \(i\) 个位置时，目前有 \(j\) 个被选入匹配,但是还未选定匹配谁的 \(s\)。
若第 \(i\) 个位置是 \(s\) 中的元素，那么：
\[dp_{i,j,0}=dp_{i-1,j-1,0}+dp_{i-1,j,0}+dp_{i-1,j,1} \]\[dp_{i,j,1}=dp_{i-1,j-1,1} \]若第 \(i\) 个位置是 \(t\) 中的元素，那么：
\[dp_{i,j,0}=dp_{i-1,j+1,0}\times (j+1) \]\[dp_{i,j,1}=dp_{i-1,j,1}+dp_{i-1,j+1,1}\times (j+1) \]最后答案就是 \(dp_{n,0,0}+dp_{n,0,1}\)
T3
考场全推这题去了，只推出了 \(O(n^2)\)
答案就是欧拉数 \(\langle n,k-1 \rangle\)
T4
毒瘤，没改。
下午lk讲杂题选讲
Choosing Subtree is Fun
二分答案，然后变成求包含一个区间的最小联通子图。
按 dfn 排序即可。
Sources and Sinks（CF1036G）
对源点的每个子集S，记 \(f(S)\) 为S能到达的汇点集合。
则如果存在S不是全集，且 \(|S|≥|f(S)|\) 答案就是NO。
反之对每个汇点都可以归纳证明能到达所有其它汇点，答案是
YES。
Lenient Vertex Cover（CF1680F）
直接线段树分治。
但这里lk讲了另一种做法：
如果一开始不是二分图的而删一条边是的话，说明这条边在所有奇环的交。
考虑 \(dfs\) 树，易知只有树边和返祖边，而我们只用考虑一条返祖边
和树边得到的这些简单环。
然后数上差分即可。
Day13
上午张隽恺讲dp，主要讲的dp状态如何设。
先介绍了每种dp的常见的想法和状态如何考虑，然后再看几道例题给我们思考。
也是收获不小
Day14
主要讲的dp的转移优化。
每种优化都先给我们讲解再看题目，就是难度……。
中途lk也来听，说了句，如果这题是我想的这样，你确定这不是NOI？
斜率优化题感觉很难想到是斜率优化qwq。
四边形不等式好用，但是只能打表证。
分治和单调栈也是一个好选择。
总结
想题的方向和深度提高了一个档次（还有正确性）
见识到了许多大佬（与我们一起吃饭，考场场切黑博弈论的巨佬，以及宿舍对面的两位银牌爷等等）。
但是cd的火锅里的花椒太多了