考试LIST [2020.09]
2020.09.05
$\texttt{Location:NOIP2020}$
得分：$\texttt{130/300,Rank3}$。
[09.05]-错误
$\texttt{T1}$ 很快想到了正解，写得却很慢，浪费了很多时间。
$\texttt{T1}$ 空间计算不准，导致差点爆 $0$。
$\texttt{T2}$ 多种情况的树形 $\texttt{dp}$ 少算了一种情况，导致 $\texttt{WA}$。
$\texttt{T3}$ 部分分策略错误。选择先刚了 $\texttt{1h+}$ 的正解，暴力一分没写，又写了很久的随机化，最后少拿了 $\texttt{10pts}$ 的部分分。
[09.05]-部分正解
$\texttt{T1}$
最大子矩形裸题，直接悬线法。
$\texttt{T2}$
多状态树形 $\texttt{dp}$，对每一种节点形态设一个状态做 $\texttt{dp}$。注意考虑一个点拉下去一条链，再接着两条链的情况。
$\texttt{T3}$
考虑费用流。发现对于第 $i$ 个通过的鸟，后面有 $n-i$ 个等待，因此可以对每一个洞，拆成很多时刻，不同时刻对总时间的贡献是不一样的，具体来说就是乘上一个时间戳。
这样边数太多了，但是我们发现如果一个洞还没有一只鸟通过，那么显然时间戳第 $2$ 及后面的边都没必要连。所以我们可以直接用 $\texttt{SPFA}$ 找到增广路后暴力更新 $1$ 的流量，然后对那些跑满了的点继续动态加边。
复杂度比较玄学，不过貌似是 $O(nmp)$。
2020.09.06
$\texttt{Location:NOIP2020}$
得分：$\texttt{300/300,Rank1}$。5个并列
[09.06]-错误
做题策略不够好，先肝了好久的 $\texttt{T1}$，脑袋糊掉了，导致后面写题很慢。
[09.06]-部分正解
$\texttt{T1}$
直接设 $dp[n][k]$ 为把 $n$ 个相同的弹珠分进 $k$ 个相同的盒子里的方案数。
为了保证不重复，令弹珠个数单调不减。
考虑最左边那个放多少弹珠，枚举一个 $i$ 为这里放多少个弹珠，那么后面所有位置最少都要放 $i$。但我们的 $\texttt{dp}$ 不好处理放 $0$ 个的情况，因此我们可以先在最左边放 $i$ 个，后面每个位置放 $i-1$ 个，然后去掉最左边那个继续 $dp$。因此有方程：
$$dp[n][k] = \sum_i dp[n-i-(i-1)\times (n-1)][k-1]$$
发现 $i$ 的枚举是有界限的，类似于调和级数，因此直接记忆化即可。
$\texttt{T2}$
点分治板子，加个 $\texttt{set}$ 判断一下就可以了。
$\texttt{T3}$
这题很有意思，写下题面：
给定 $n$，求有多少正整数对 $(a,b)$ 满足 $a,b\le n$ 且 $\texttt{gcd}(a,b)=a\texttt{ xor }b$。
$n \le 10^7$。
我们发现对于二元组 $(a,b)$，不妨令 $b \le a$，有 $\texttt{gcd}(a,b)\le a-b$，这个直接更相减损。$a \texttt{ xor } b \ge a-b$，也就是最差情况下 $b$ 的所有为 $1$ 的二进制位 $a$ 都为 $1$，此时答案最差，为 $a-b$。因此如果他们相等，那么这个值一定要等于 $a-b$。
考虑枚举 $c=\texttt{gcd}(a,b)$， $a$ 显然是其倍数。暴力枚举其倍数，然后考虑到 $gcd(a,a-c)=c$，因此 $b=a-c$。然后又 $a\texttt{ xor }b=c$，所以只需要判断 $a\texttt{ xor }c$ 是否等于 $a-c$ 即可。
复杂度 $O(n\log n)$。
2020.09.12
$\texttt{Location:NOIP2020}$
得分：$\texttt{250/300,Rank2}$。
[09.12]-错误
$\texttt{T1}$ 没有 $\texttt{\#define int long long}$，然后少开了几个地方的 $\texttt{long long}$，成功 $\texttt{100 -> 60}$。
$\texttt{T2}$ 提答的部分分复制错了一个数字，然后就挂了一个点。
[09.12]-部分正解
这场三道题的名字分别是 $\texttt{tsm,ihp,qmras}$。
惊奇地发现翻转一下变成 $\texttt{mst,phi,sarmq}$。于是就是正解了......
$\texttt{T1}$
发现就是一个最小生成树的板子再套一个 $\texttt{nim}$ 的板子，只是需要支持加边。$n \le 5000$，加边 $\le 1000$，因此可以每次对 $\texttt{mst}$ 中的 $n-1$ 条边和新加的 $1$ 条边做一次 $\texttt{Kruskal}$，然后暴力重构最小生成树。
或者直接 $\texttt{LCT}$。
$\texttt{T2}$
显然的是：
$$\sum_{d|i} \varphi(d)=i$$
也就是：
$$1 * \varphi=\text{Id}$$
这是 $\texttt{Phi}$ 的性质。所以这个 $f$ 就是 $\varphi$，直接线性筛一下即可。
对于后面两个提答的部分分，直接单点求 $\texttt{Phi}$ 。
$\texttt{T3}$
建出 $\texttt{SA}$，然后求出 $\texttt{Height}$。显然的是，在 $sa$ 数组中排名 $i,j(i\le j)$ 的两个后缀之间的 $\texttt{lcp}$ 是：
$$\min_{i\le p\le j} \texttt{Height}[p]$$
如果定义以上为 $(i,j)$ 的权值的话，我们需要的就是所有权值 $\le k$ 的二元组的权值之和。
考虑设置 $dp[i]$ 为二元组第二个是 $i$ 的权值和。每个位置 $i$ 向前找，找第一个 $\texttt{Height}[p] < \texttt{Height}[i]$ 的位置 $p$，那么 $p$ 及往前的所有 $\min$ 都与 $\texttt{Height}[i]$ 无关。然后 $[p+1,i]$ 的话，每一个点的 $\texttt{Height}$ 都 $\ge \texttt{Height}[i]$。因此他们对答案的贡献都是 $\min(\texttt{Height}[i],k)$。
找 $p$ 的话，直接 $\texttt{st}$ 表二分即可。
2020.09.13
$\texttt{Location:NOIP2020}$
得分：$\texttt{240/300,Rank1}$。
[09.13]-错误
$\texttt{T1}$ 做法锅掉了，暴力也出现了同样的问题，因此没拍出来。所以不是拍了很多组就万事大吉了。
$\texttt{T3}$ 差点又少开 $\texttt{long long}$ 了......
$\texttt{T3}$ 神仙 $\texttt{rhdeng}$ 数组开大了，因此以后要手算内存！！！
[09.13]-部分正解
$\texttt{T1}$
首先可以发现，子弹个数不会增加，实际上，打到 $\texttt{bonus}$ 的砖块最后相当于花费 $0$ 的代价拿到他的贡献。
但是打这样的砖块，至少需要有一颗子弹！！！ 我就这么错的
不难发现，只有一列无法在已经打了分配的所有子弹后，无法继续打接下来的 $\texttt{bonus}$ 砖块。因为其他的列都可以从这一列先借一颗子弹，打到所有能打到的 $\texttt{bonus}$。
因此我们可以考虑设 $dp[i][s][0/1]$ 为：考虑前 $i$ 列，一共花费 $s$ 颗子弹，前面是否出现可以借子弹的列的最大贡献。令 $val[i][j]$ 为：第 $i$ 列打 $j$ 个砖块对答案的贡献，$c[i][j]$ 为：第 $i$ 列打 $j$ 个砖块所需要的子弹颗数。
那么有：
对任意列 $i$ 任意一个 $j$ ，都有：
$$dp[i][s][1]=dp[i-1][s-c[i][j]][1]+val[i][j]$$
也就是如果之前已经有可以借子弹的列，那么这一列可以取 $\texttt{bonus}$。
对于任意列，打到一个非 $\texttt{bonus}$ 的砖块的 $j$，有：
$$dp[i][s][1]=dp[i-1][s-c[i][j]][0]+val[i][j]$$
意思是，如果这一列不是 $\texttt{bonus}$ 结尾，那么别的列就可以从他来借子弹。
对于任意列，打到一个 $\texttt{bonus}$ 的砖块的 $j$，有：
$$dp[i][s][0]=dp[i-1][s-c[i][j]][0]+val[i][j]$$
意思是，这一列打到一个 $\texttt{bonus}$ 结尾，且前面所有的列都没有可以借子弹的，因此借子弹的列一定出现在后面。
最后的答案就是：
$$\max_{i=0}^k dp[m][i][1]$$
也就是一定要出现一个可以借子弹的列。当然第一维可以滚掉。
还有个想法，可以枚举哪一列作为借子弹的列，然后从左往右、从右往左各维护一个 $\texttt{dp}$ 数组表示可以借子弹时候的情况，然后把两个 $\texttt{dp}$ 数组再做一遍背包。没打 不过应该没问题？
$\texttt{T2}$
首先有以下等式：
$$(a+b+c)^2=a^2+b^2+c^2+2ab+2ac+2bc$$
那么有：
$$ab+ac+bc=\dfrac{(a+b+c)^2-(a^2+b^2+c^2)}{2}$$
同时有类似的柿子：
$$(a+b+c)^3=a^3+b^3+c^3+3a^2b+3ab^2+3a^2c+3ac^2+3b^2c+3bc^2+6abc$$
可以得到：
$$abc=\dfrac{a^3+b^3+c^3+3(a+b+c)(ab+ac+bc)-(a+b+c)^3}{3}$$
现在考虑对于一个幂 $p(p\ge 4)$，假设我们已经知道 $\le p$ 的所有次幂的答案，那么：
$(a^p+b^p+c^p)(a+b+c)$
$=a^{p+1}+b^{p+1}+c^{p+1}+ab^p+ac^p+a^pb+bc^p+a^pc+b^pc $
$=a^{p+1}+b^{p+1}+c^{p+1}+a^{p-1}(ab+ac)+b^{p-1}(ab+bc)+c^{p-1}(ac+bc)$
$=a^{p+1}+b^{p+1}+c^{p+1}+(a^{p-1}+b^{p-1}+c^{p-1})(ab+ac+bc)-(a^{p-2}+b^{p-2}+c^{p-2}) \times abc$
因此如果令 $a^i+b^i+c^i=S_i$，那么有：
$$S_{p+1}=S_p\times S_1 - S_{p-1}\times (ab+ac+bc)+S_{p-2}\times abc$$
直接递推即可。由于需要输出分数，因此还需要维护一个分数类。
$\texttt{T3}$
看到异或，就要想 $\texttt{Trie}$ —— 鲁迅
很简单的 $\texttt{01Trie}$。每次考虑一个新数 $a_i$，之前所有数字自低位向高位加入 $\texttt{01Trie}$。
每次考虑数字 $a_i$ 某一位与字典树中数字对答案的贡献，显然对于自低向高的第 $p$ 位，其贡献为 $2^{p-1}\times s$，其中 $s$ 是满足前 $p-1$ 位与 $a_i$ 相同，这一位与 $a_i$ 不同的数字个数。这个在字典树上表现为：从根向下查询，如果现在要向 $\texttt{v}$ 儿子 $\texttt{v=0/1}$ 走，那么与 $a_i$ 在这一位构成 $\texttt{lowbit}$ 的数字个数即为：$siz[ch[x][!v]]$，应该很显然。
时间复杂度 $O(n\log\texttt{值域})$。
2020.09.19
$\texttt{Location:NOIP2020}$
得分：$\texttt{170/300,Rank2}$。
[09.19]-错误
$\texttt{T1}$ 写 $\texttt{LIS}$ 写挂了，常数太大。
$\texttt{T2}$ 正解，但是常数太大被卡了 $\texttt{30pts}$。
$\texttt{T3}$ 简单题，但是花费的时间太多了。
[09.19]-部分正解
$\texttt{T1}$
考虑使用哈希或者 $\texttt{map}$ 的方式把字符串映射成数字，然后跑 $\texttt{LCS}$。但是正常的 $\texttt{LCS}$ 复杂度下线貌似是 $O(n\times m)$，无法通过。
发现有一个序列没有相同的元素，称其为 $\texttt{S}$，另一个为 $\texttt{T}$，可以把 $\texttt{T}$ 中，每一个值表示为 该值在 $\texttt{S}$ 中的出现位置，跳过那些没出现过的值，因为他们显然不在 $\texttt{LCS}$ 中。然后对新的序列跑 $O(n\log n)$ 的 $\texttt{LIS}$。
$\texttt{T2}$
莫队板子。
直接套一个线段树维护最长的连续值域长度即可，每次单点 $\texttt{+1 -1}$，很好写。
注意常数！！！
可以考虑开个桶，每次记录每一个点上被加多少次，只有在 $\texttt{0->1}$ 或者 $\texttt{1->0}$ 的时候才更新线段树。
还有可以根据离散化之后的 $\texttt{vector}$ 的 $\texttt{size}$ 来分块，貌似快一些。
$\texttt{T3}$
首先注意：所有的物品都只能买一个！！
首先将所有物品从大到小排序，然后可以发现：如果钱无法购买物品 $i$ 了，那么 $i$ 以前不论是已经买过或是没买，都买不了了。所以考虑枚举最小的，不买的物品，那么比他更小的物品都要买，即一个后缀和的形式，前面的就是一个背包了。
还需注意一点，以上枚举的所有情况都是至少有一个不买的情况，但是如果所有的物品都能买下，那么答案 $\texttt{+1}$
2020.09.20
$\texttt{Location:NOIP2020}$
得分：$\texttt{230/300,Rank3}$。
又$\texttt{AK}$失败了西八
[09.20]-错误
$\texttt{T1}$ 的结论没有及时推出，数学方面还是菜......
$\texttt{T3}$ 满分想法只有 $\texttt{30pts}$，实现貌似有问题。
[09.20]-部分正解
$\texttt{T1}$
设现在的概率是 $P$，选的人概率分别是 $p_1,p_2...p_k$。
考虑新加入一个点 $p_x$，他会让答案变成：
$$P\times (1-p_x)+p_x\times \prod_{i=1}^{k}(1-p_i)$$
变一下成为：
$$P+p_x\times (\prod_{i=1}^{k}(1-p_i)-P)$$
由于 $P$ 和之前选的 $p_1,p_2...p_k$ 都固定，所以这个柿子在 $p_x$ 越大时就越大。
把 $p_x$ 从大到小排序，依次判断是否加入即可。
感性理解
$\texttt{T2}$
直接树形背包即可，设 $dp[0/1][x][i]$ 为从 $x$ 出发，向下走 $i$ 步，最后回到/不回到原点，能获得的最大价值。
注意一下树形背包其实是 $O(n^2)$ 的。
$\texttt{T3}$
考虑将所有边按照其权值下界排序，枚举下界。
每次枚举一个下界，把所有下界 $\le$ 他的全部加入，然后看上界最大可以是多少时，$1$ 和 $n$ 仍然联通。
这个东西可以跑最大生成树，同样可以并查集。
如果追求更优秀的复杂度，可以直接上 $\texttt{LCT}$。
2020.09.26
$\texttt{Location:NOIP2020}$
得分：$\texttt{300/300,Rank1}$。
其实格式错误了一题kk
[09.26]-错误
$\texttt{T1}$ 的换行写成了空格......眼瞎......
[09.26]-部分正解
$\texttt{T1}$
$\texttt{sbt}$，第一问数叶子，第二问直接模拟。
$\texttt{T2}$
考虑使用 $\texttt{ExKMP}$，或者叫 $\texttt{Z Algorithm}$。
这个东西可以在 $\mathcal{O}(n)$ 求一个字符串 $S$ 和另一个字符串 $T$ 的每一个后缀的 $\texttt{lcp}$，当然 $T$ 可以等于 $S$，称其为 $\texttt{Z}$ 函数。
$z[i]$ 表示以第 $i$ 个字符开始的后缀与整个串的最长公共前缀长度。首先显然可以暴力跳，但是为了充分利用之前的 $z$，做出以下的优化：
令 $l,r$ 为当前已经得到的匹配中，右端点最大的区间为 $[l,r]$，如果现在的 $i \le r$，那么可以令 $z[i] = \min(z[i-l+1],r-i+1)$，可以这样理解：首先 $[l,r]$ 与 $[1,r-l+1]$ 相同，所以从 $i$ 开始的后缀 和 从 $i-l+1$ 开始的后缀有相同的前缀，但在 $r-i+1$ 之后的部分超出限制，不能确定，因此取 $\min$。然后直接暴力匹配，同时更新 $l,r$ 即可。尤其注意特判 $z[1]=n$，因为不特判就没法保证 $\mathcal{O}(n)$ 的复杂度了。
那么现在考虑用每个后缀与自己的 $\texttt{lcp}$ 来记录答案。发现对于一个 $z[i]$ ，其对答案的贡献是 $\lfloor \dfrac{z[i]}{2} \rfloor$ ，意思是这个后缀和原串的最长公共前缀为 $z[i]$，偶数长度的就是 $\lfloor \dfrac{z[i]}{2} \rfloor$。
$\texttt{T3}$
分层图 $\texttt{Dijkstra}$ 。注意 $k$ 条边不一定用得完，在总边数 $m < k$ 的时候根本用不到 $k$ 条边，特殊判断即可。
2020.09.28
$\texttt{Location:NOIP2020}$
得分：$\texttt{300/300,Rank N/A}$。
请假了
[09.28]-错误
保龄选手......
[09.28]-部分正解
$\texttt{T1}$
柿子里的绝对值不太爽快，排序之后删掉：
$$x_i-x_j \ge w_i + w_j$$
换一下位置变成：
$$x_i-w_i \ge x_j+w_j$$
这可以看作两个区间：中心为 $x$，半径为 $w$，也就是 $[x-w,x+w]$。然后这两个区间代表的点之间有边也就是这两个区间不相交（可以在端点重合）。$\mathcal{O}(n\log n)$ 随便搞。
$\texttt{T2}$
对于任意 $a \le x$ ，有 $x \mod a \le \dfrac{x}{2}$，所以一个数字 $x$ 能被模 $\mathcal{O}(\log x)$ 次变成 $0$。线段树记录区间 $\max$ 和区间和，如果区间 $\max$ 大于等于模的数就暴力进去改。
时间复杂度待补
$\texttt{T3}$
定义 $f(n,k)$ 为 $[n+1,2n]$ 中，二进制下恰好有 $k$ 个 $1$ 的数字个数。
考虑 $f(n,k)$ 到 $f(n + 1,k)$，发现区间从 $[n+1,2n]$ 到了 $[n+2,2n+2]$，少了一个 $n+1$，多了 $2n+1,2n+2$，注意到 $2n+2=(n+1)\times 2$，那么 $2n+2$ 只不过是在 $n+1$ 后面加个 $0$，不改变 $1$ 的个数。因此 $f(n,k)$ 到 $f(n+1,k)$ 单调不减。
然后就可以二分了。
现在考虑 $f(n,k)$ 怎么求。
考虑直接求 $1-n$ 的满足条件数字个数，然后减一下。每次考虑从每一个 $1$ 断开，然后就可以组合数了，例如 $101001$ 可以分成：
$$[0,100000),[100000,101000),[101000,101001),\{101001\}$$
然后用类似数位 $\texttt{dp}$ 的方式组合数即可。答案可能很大，注意调整二分上界。