我好菜啊……
4-10
炸了炸了……
T1
我算是想出来了，但是考场上没有调出来，一个是因为感觉比较工业所以总是写一会纠结一会要不要写下去，另外也是因为有些细节我稍微想复杂了一些. 大概思路是，从小到大枚举$a _S$，与此同时从大到小枚举$b _S$，每次就尝试把$b _S$减少1，也就是删掉$b _x=b _S$的$x$，然后看看还有没有点数不小于$k$的联通块. 维护联通块大小的话可以用lct：每条边的权值看成两个端点$b$的较大值，很容易证明整个联通块上只有最小生成树上面的边是有用的，这个就是简单的lct问题了.
最小化$\max\{a\}+\max\{b\}$这样的问题，经常要从小到大枚举$a$，然后求$\max\{b\}$的最小值，这是我以前就知道的. 求$\max\{b\}$的最小值的时候，以前我做的题都是可以直接求的，而在这道题里面可以从大到小枚举，每次尝试将其减小直到不可行，这个思路我以前没有想到过.
T2
我已经注意到一个很关键的地方，就是强联通块的数量+1=划分的方案数，这里划分指的是把点划分成$S$和$T$两个集合（可以为空），对$\forall x\in S,~y\in T$有$(x,y)\in E$. 可能是T1做得不顺利，我没有想到将其写成$x+1=\sum _{S\cup T=U,~S\cap T=\emptyset}\prod _{x\in S}\prod _{y\in T}[(x,y)\in E]$的形式（$U$为所有点构成的集合），这样两边再求一下期望就可以得到$E(x)+1=\sum _{S\cup T=U,~S\cap T=\emptyset}\prod _{x\in S}\prod _{y\in T}\textrm{Pr}((x,y)\in E)$，考虑到输入只会给定m条边，其它边都是$\frac{1}{2}$，可以记$f _{x,y}=2\textrm{Pr}((x,y)\in E)$，即有$E(x)+1=\sum _{S\cup T=U,~S\cap T=\emptyset}2^{-|S|(n-|S|)}\prod _{x\in S}\prod _{y\in T}f _{x,y}$.
考虑怎么算这个东西，分开考虑输入给定的边构成的每个联通块，那么任何一个联通块的点数都不超过20，让$g _i=\sum _{S\cup T=U^\prime,~S\cap T=\emptyset,~|S|=i}\prod _{x\in S}\prod _{y\in T}f _{x,y}$，点数很少可以直接枚举$S$然后暴力计算出来（这里$U^\prime$代表一个联通块里的所有点构成的集合）. 让$h _i=\sum _{S\cup T=U,~S\cap T=\emptyset,~|S|=i}\prod _{x\in S}\prod _{y\in T}f _{x,y}$，容易发现$h$就是每个联通块的$g$的卷积，同样可以暴力计算，最后答案即为$\sum h _i2^{-i(n-i)}$.
4-11
AK辣！不过能A掉T2也是因为数据很水，要卡还是能卡成50分的.
T1
水题
T2
我用奇怪的分治AC了，让solve(l,r,hl,hr)表示处理$[l,r]$这个区间，区间左右的石柱（即$l-1$和$r+1$）高度为$h _l$和$h _r$. 那么如果$\max _{l\le i\le r}\{a _i\}\le\min\{h _l,h _r\}$，就可以直接返回答案，否则找出区间中最高的石柱，然后向两边分治. 在数据随机的情况下，这么做是$\mathcal O(q\log n)$的.
其实只要让$a _i$单调就可以卡掉这个做法……正解是记$h _i$为第$i$列的最高位置（包括水），那么易知$h _i$是单峰的，而答案就是$\sum(h _i-a _i)$. 用两个set来维护$h _i$就可以了，具体细节有一点多，大概是维护$a _i$从左到右和从右到左的LIS，设其下标序列为$S _1,~S _2$，那么$\sum h _i=\sum a _i(S _{1,i+1}-S _{1,i})+\sum a _i(S _{2,i}-S _{2,i+1})-n\max _{i=1}^n\{a _i\}$（$S _1,~S _2$都要包含$0$和$n+1$）.
c++的reverse_iterator也不知道发生了什么完全不能用，浪费我一个下午……
T3
cf原题
4-12
辣鸡题意不清……不过也是我没认真读
T1
按$a$排序，相同的话坐标较小的排在前面，然后$f _i=\max\{f _j+\frac{(i-j)(i-j-1)}{2}\}$，把括号拆开之后发现对每个$j$都是关于$i$的一条直线，用lych线段树维护即可，虽然是$\mathcal O(n\log^2 n)$，但常数比较小，用io优化可以卡过去.
然后我就拿了18分，原来可以TM一个都不选.
T2
首先可以想到拆开每一位，那么每次操作就是模2，循环卷积意义下乘$f(z)=1+\frac{1}{z}+\cdots+\frac{1}{z^{k-1}}$. 这个可以直接用FFT来做，不过$\log$太多了……我只拿了60分. 注意到模2意义下多项式有一些很好的性质，比方说$f^2(z)\equiv f(z^2)\pmod{2}$. 于是$f^{2^t}(z)$都是很好求的.
这个时候可以发现其实没有必要使用多项式，进行$2^t$之后的结果就是$y _i=\oplus _{j=0}^{k-1}x _{(i+j\cdot 2^t)\mod{n}}$（这是因为$f^{2^t}(z)=\sum _{j=0}^{k-1}z^{-j\cdot 2^t}$）. 然后这个可以对每个环求前缀和从而$\mathcal O(n)$求出来，总的时间复杂度为$\mathcal O(n\log T)$.
T3
可以写出一个暴力的dp方程$f _{i,j}=\max\{f _{k,j-1}+\text{val}(k,i)\}$，这里$f _{i,j}$表示只考虑$r _w\le i$的区间，选$j$个点的答案. 我一开始的想法是决策单调性dp，但这样是两个$\log$的，事实上$\text{val}(k,i)$可以用线段树来维护，当$i$增加的时候只需要做一个后缀加.
关键应该是把$m$优化掉. 如果取消$m$的限制的话，dp方程的第二维可以直接去掉，这样复杂度里的$m$就没有了，这种时候可以使用这样一种套路：记选k个点的最优解为$\text{ans}(k)$，那么有$\text{ans}(k+1)-\text{ans}(k)\le\text{ans}(k)-\text{ans}(k-1)$，那么可以记$c(k)=\text{ans}(k)-\lambda k$，那么$c(k+1)-c(k)=\text{ans}(k+1)-\text{ans}(k)-\lambda$，即$\text{ans}(k+1)-\text{ans}(k)=\lambda$的时候$c(k)$取到最大值，那么二分这个$\lambda$，使$c(k)$取最大值时$k=m$，即可得到答案为$c(m)+\lambda m$. $c(k)$相当于每选一个点要付出$\lambda$的代价，问最大收益，可以用一个类似的dp来解决. 具体实现起来还有一些细节. 现在复杂度是$\mathcal O(n\log n\log x)$，据说常数比较不能AC.
接下来只能考虑优化dp了. 注意到对$x< y$，一旦$f _x+v _x\le f _y+v _y$，那$x$求再也不能成为最大值了，于是我们可以维护$f _x+v _x$的差分，一旦某个位置非负，那就可以把前面的位置合并进来，这个用并查集来维护. 有几个细节，一个是具体实现的时候我们应该求出最大化收益的时候选出的最大点数，所以差分刚好为0要合并前面的时候，还要注意处理一下. 另外，应该让$f _0+v _0=\lambda$，这样在此处转移就相当于一个点都不选的情况（区间从1开始）. 第一次写起来真的挺恶心的……这种一堆区间然后dp的问题用左闭右开区间似乎会方便一点？
4-13
炸了炸了……
T1
强行线性基硬搞的话$\log$应该太多了所以过不了. 我们把询问离线，按右端点排序，那么就是要维护$f(j,i)$表示$j$到$i$的线性基，支持把$i$右移. 首先注意到$j$左移的时候，相当于不断往线性基里面加数，所以不同的$f(j,i)$只有$\mathcal O(\log a)$个，考虑维护这些线性基和它们的端点，每次$i$右移的时候，存在一个$j _0$，对$j< j _0$，$f(j,i)$不变，对$j\ge j _0$，$f(j,i)$相当于插入一个数，直接维护就好了. 这样的复杂度是$\mathcal O(n\log^2 a+q\log a)$.
上面那个做法的瓶颈在于维护$\mathcal O(\log a)$个线性基. 这些线性基的左端点肯定是线性无关的，从右到左线性基的变化其实就是依次加入这些端点，所以可以考虑把这些端点放入一个线性基里面，而且只维护这个线性基. 这么做的问题是，放进线性基里面就不能区分它们的位置了，所以没办法查询，这里要用到一个套路，如果$x< y$，那么所有包含$a _x$的查询肯定包含$a _y$，所以把$a _x$异或上$a _y$肯定不会有影响，所以我们维护线性基的时候可以多维护一个位置，插入一个数$x$的时候，如果到了某一位有数，就把位置靠后的放入线性基，靠前的异或上靠后的然后继续往下看. 插入成功了之后不能用较小的数的去消这个数，也不能用这个数去消较大的数.
感觉讲不清楚，贴段代码吧……
1 | inline ele getv(ele x,ele i){ |
这整一套思路都非常巧妙非常神仙啊，先当做查询区间线性基的一个套路记下来吧.
T2
恍惚间回到了GDKOI2018 D1T1……GDKOI的时候，我写的是一次更新一整段线路，这回一开始也是，结果都死活TLE卡不过去，后来改成每次只更新下一个站就飞快地AC了……叫我整段小天才！
T3
题目可以转化成给你$r$组边，每组至多选一条，问不出现环的情况下最多选多少条边. 考虑每次增加一组边，然后钦定一条加进去，如果没有出现环就不管了，否则的话枚举删掉环上的一条边，再尝试把跟它同组的另一条边钦定加进去. 这就跟找增广路一样. 复杂度$\mathcal O(r^3)$.
4-14
神仙题神仙题……
晚上打了场计蒜客的比赛，进了前200似乎有衣服拿？其实我发挥得挺差的，G没注意到会爆long long，又不知道unsigned long long已经到了$10^{19}$，结果耽搁了好久. B用bitset存边表但是没有清空，每次只是把邻接矩阵读进来，这样多组数据后一组的n比前一组小的时候就没有清空，后面and起来再算1的个数的时候就会出问题. C就是一个很简单的FWT，不知道为什么没想到.
T3
终于知道这种问题怎么做了！
首先不考虑取的树的个数的限制，那么答案就是循环卷积意义下$[x^k]\prod _{i=0}^{n-1}(1+x^i)$. 因为DFT本身就是循环卷积，所以可以考虑用IDFT来算，记$f(x)=\prod _{i=0}^{n-1}(1+x^i)$，答案就是$\sum _{i=0}^{n-1}f(\omega _n^i)\omega _n^{-ik}$.
$x^n-1=\prod (x-\omega _n^i)$，这是因为你把$\omega _n^i(i=0,1,\ldots,n-1)$代入，两边都是0. 让$x=-1$，即有$1-(-1)^n=\prod(1+\omega _n^i)$，那么答案就可以继续化为
记$s(n,k)=\sum _{\gcd(i,n)=1} \omega _n^{ik}$，后面那个东西就是$s(\frac{n}{d},k)$，可以莫比乌斯反演搞出来.
现在考虑怎么加上取的个数的限制，有一个套路，就是多加一个元，即计算$[x^ky^m]\prod _{i=0}^{n-1}(1+x^iy)$，这里只有$x$是循环卷积，把$x$看成主元，使用几乎完全相同的推导，得到答案是$[y^m]\sum (1-(-y)^{n/d})^ds(\frac{n}{d},k)$. 二项式展开需要组合数，可以分段打阶乘表来解决.
HNOI
为什么没有日期呢？因为我忘了是哪天了.
D1T1
这个做法真神仙！
从后往前考虑每个操作，如果某个位置and了0或者or了1，那么前面的操作就无关紧要了，或者说这一位已经被确定下来了. 于是可以把每个二进制位上的$n$个操作从后往前看成一个01串，然后插到一棵trie里面，考虑在trie里面从上往下走，如果这一步是and，那么整个左子树里的位置都被确定下来了，否则整个右子树里的位置都被确定下来了. 而你走到NULL或者一个叶子，就意味着所有的位置都确定下来了，于是本质不同的方案只有$\mathcal O(nm)$个，把这些方案都找出来，然后把他们按照钦定哪些位置为1分类，存到hash表里面，询问的时候就可以直接在hash表里面查.
如何hash位置集合？给每个位置分配一个$[0,2^{64})$的整数作为权值，位置集合的hash就是所有位置的权值异或起来，可以证明这样冲突的概率很小.
D1T2
首先是把序列倍长，很容易（据说这其实是难点）推出要最小化$i+\max _{i\le j\le i+n-1}\{T _j-j\}$，这个可以用单调栈很容易地dp出来，接着可以发现对答案有贡献的$T _j-j$一定是最右边的一个，它左边第一个大于它的，以此类推……然后这就非常楼房重建了. 我考场上头铁想用线段树维护结果没写出来. 楼房重建可以分块啊！贼好写啊！sbwhj！理论上每个块的大小为$\sqrt{n\log n}$的时候跑得最快，但是似乎把块只开$\sqrt n$跑得要快很多，看来以后各种分块还是要看数据调整块的大小. 还有一些小优化：如果有一块最大值比右边的最大值小，那就可以直接跳过而不需要在块内二分；最后有很多块可以不在块内二分就跳过，因为$i > n$的时候对答案没有贡献.
D1T3
kernelization真的太妙了，贴个链接.
4-17
可能是正好太困了，发挥极差.
以后一定要记住题目难度与顺序无关. 一场比赛T4一样可能很可做，T1该弃还是要弃，没有必要慌，像今年GDKOID2，像今天的T4，似乎今年HNOID1T1也是一天里面最难的.
对拍有的时候也是不靠谱的，像T1我就有错没有拍出来，所以肉眼检查、自己出数据也是很重要的，特别是给自己程序加了个优化之类的时候，一定要想清楚，我T1炸了也有一部分原因是这个.
T1
成功读错题，不知道为什么产生了一种错觉，代价加起来不会超过$P$. 这是一个典型的树上背包问题，让$f_{i,j}$表示以$i$为根的子树里代价恰好为$j$的最大收益，我以前一直只会把子树的$f$卷起来来转移，不过启发式合并一发还是可以水过去的. 事实上可以用$f _{i,j}$表示dfs序上只考虑$i$以前的点，代价恰好为$j$的时候的最大收益，那么选$i$就把背包转移到dfs序上下一个点，否则就跳过整棵子树，也就是dfs序上的整段.
T2
想复杂了. 旋转的时候中序遍历不变，子树权值和只有两个点会被改变，每次询问就是中序遍历上一段区间的乘积.
T3
一眼就能看出来是跟$g(n)=n^m$卷起来做杜教筛，关键是怎么求$m$次方的前缀和. 不知道为什么我以前听说的方法都是满页数学公式，各种多项式，反而不知道这么一个简单的方法：显然这是一个$m+1$次的多项式，把它在$0,1,\ldots,m+1$处的点值线性预处理出来，然后就可以插值了. 因为选出的点的特殊性，分母处的$\prod _{1\le i\le n,~i\neq k}(x _k-x _i)=k!(m+1-k)!$，预处理阶乘之后可以$\mathcal O(1)$求出来. 最后一点空间卡得很近，出题人想强迫你写多点求值，但是可以各种卡常卡空间+预处理$\mathcal n^{\frac{2}{3}}$的答案+预处理更大范围内的$m$次方前缀和压线A掉. 卡空间的方法大概有这么几个：筛$\mu(i)i^m$的时候不额外用一个数组来存是否是质数，而是直接使用存答案的数组，一开始全部置为-1，那某个位置不为0的时候显然就已经被筛掉了；存质数的数组只需要开到$\mathcal O(\frac{n}{\ln n})$.
T4
简单计数题，把$(0,0)$也看成不合法的向量，容斥一发，计算不考虑不合法向量随便走的方案数时，可以发现两个坐标是独立的，于是分开来dp，再用前缀和优化一下转移.
4-18
还是很困……又挂一场. 希望只是困的问题吧……
T1我已经想到了做法，但是没有注意到可以离线，而在线的标准做法太难打，就打了个水法，结果就被卡掉了. 说到底还是我的基础不够扎实，没有想到可以离线来简化问题.T2的式子我推了太久，也导致了T1我没时间打正解，如果基础再扎实一点，再冷静一点，应该能推得更快，能注意到更简洁的做法，所以以后在考场上还是需要更平稳一点的心态，思考再细致一点，不要无脑往一个方向钻，当然太困了没办法集中精力也是原因之一，当时想边界情况的时候就死活想不清楚.
T1
其实就是要求每个子串出现次数的平方和，如果$n=1$的话后缀自动机随便做，有多个的话其实就是要建一个广义后缀自动机然后依次加入每个字符串，但是带修改的时候，直接暴力维护每个节点代表的串的出现次数是会被卡的. 这道题可以离线把整个广义后缀自动机建好，再用树链剖分来维护parent树，如果强制在线的话就只能上LCT了. 据说有$\mathcal O(L\sqrt L)$的水法？
T2
考场上把式子推了出来，但是比标算繁琐一些，而且不够时间写分治FFT了，就只好交了一发暴力的dp，结果看错了范围，最后还交错了程序……
感觉像这种题，要你算一个绕来绕去的奇奇怪怪的东西，很可能会有优美一些的意义，比方说这道题，每次操作的时候还要去掉这个数，把其他的数乘起来，就显得很难表示，我直接硬推也推出来了，但是就麻烦了很多. 事实上可以注意到，每一轮的伤害其实就是$\prod A _i$的减少量，所以只需要求最后$\prod A _i$的期望，推出来就是$\prod A _i-\frac{k!}{n^k}[z^k]e^{nz}\prod(A _i-z)$，非常地好算.
我考场上推出来的做法是记$f(z)=\prod(A _i-z)\sum\frac{1}{A _i-z}$，然后计算$\sum \frac{[z^r]f(z)}{n^{r+1}}\sum _{i=0}^{k-1}i^{r\downarrow}$，这里$\sum _{i=0}^{k-1} i^{r\downarrow}=\sum _{i=0}^{k-1} \frac{(i+1)^{r+1\downarrow}-i^{r+1\downarrow}}{r+1}=\frac{k^{r+1\downarrow}}{r+1}$，这个求和的方法我考场上一时慌张居然没想到……我好菜啊……
有没有dalao愿意看看我这个做法对不对啊.
T3
肯定只有两端会往回走，中间都是一个方向上的，然后应该可以dp出来. 细节好多不想写……
T4
神仙题. 输出Infinity有20分.
4-19
开始的时候还是困，头昏脑涨地想了一会，然后开始头铁码T3，等码出来+卡常卡进去之后头非常疼，时间也不多了，结果其他题的暴力没有打好. 以后可能还是要调整一下策略，说不定需要先稳住暴力分再去码正解？
以后考前一定要尽量休息好.
T1
首先是一个最小割模型的套路，如果有若干个物品，第$i$个有$p _i$种决策方案，分别会得到一定的收益，决策之间有一些制约关系. 可以把$i$拆成$p _i-1$个点$a _{i,0},a _{i,1},\ldots,a _{i,p _i-2}$，相邻两个点连边，源点向$a _{i,0}$连边，$a _{i,p _i-2}$向汇点连边，割掉一条边就代表一种决策. 决策之间的制约关系，像某个点的决策编号比另一个点靠前，某个点的决策编号至少比另一个点靠前$k$位之类的，就可以通过在某些点之间连边来体现. 以假定选取获得了所有正的收益，边权即为这么决策得不到的收益，然后算最小割即可. 回去要好好看一下网络流的各种模型.
这道题里面，对每个$x _i$，可以认为它有3种决策：在最大子段前，在最大子段里，在最大子段后. 对于给定的每条边$(u,v)$，可以看作$u$的决策编号不能在$v$之后. 这样就能转化为最小割模型来做了.
T2
考场上我已经想到了用莫比乌斯反演转化为求$k|\gcd(u,v)$的路径条数，结果没好好想下去.
可以发现有平方因子的因数都是没有贡献的，而$10^6$以内的数最多有$c=7$个素因数，所以每个数最多有$2^c=128$个对答案有贡献的约数. 先考虑没有修改的情况，预处理出$S _d$表示权值被$d$整除的边的集合，对于每个非空且满足$\mu(d)\neq 0$的$S _d$，用一个并查集统计答案就可以了. 注意到每条边之多出现在$2^c$个满足$\mu(d)\neq 0$的$S _d$中，复杂度为$\mathcal O(2^cn\alpha(n))$.
考虑在线，我的第一反应是按时间分治，可是这个东西好像不能很方便地加边，更不用说撤销. 注意到$q$非常小，因而受到修改操作影响的边也非常少，可以把$S _d$中受操作影响和不受影响的边分开来存，对于每个$d$，先只把不受影响的边加进去，然后枚举$q+1$时间点，对每个时间点，加入受影响且边权被$d$整除的边，统计答案再撤销，去计算下一个时间点. 因为要撤销所以并查集不能路径压缩了，复杂度为$\mathcal O((n+q^2)2^c\log n)$.
T3
数位dp的做法还是比较容易看出来的，正解非常神仙.
T4
先坑着.