Day 1
100 + 0 + 100 + 0，唉唉被绿题战胜了。
A QOJ2957
设 $dp[i][j][k][l][3]$ 表示现在在 $(i,j)$ 位置，走到第 $k$ 个数字串的第 $l$ 位，上一步是从左边/右边/上面过来的最小值。枚举下一步往哪走，判断是否存在数字串满足条件，随便转移一下即可。
B P6884
我们递归地计算每个子表达式的最大值。
假设一个表达式 $A$ 是由子表达式 $A_1,\cdots,A_k$ 构成。我们讨论一下两种情况：
- 子表达式由加号拼接。那么 $A$ 的最大值要么是所有子表达式的最大值加和，要么是 $L_k$。
- 子表达式由乘号拼接。如果我们不考虑取值限制，那么基本不等式就可以说明，每个子表达式都取 $L_k / k$ 时积最大。考虑取值限制，我们可以把子表达式的最大值从大到小排序，那取不到这个平均值的一定是一段前缀。于是依次找，$L_i > L_k / k$ 时，贡献为 $L_k / k$，$L_i \leq L_k / k$ 时，贡献为 $L_i$，然后把这部分从平均值中去除掉，也就是 $L_k$ 和 $k$ 减去 $L_i$ 和 $1$。
C
先考虑不带修。设 $i$ 吃到饭的时间是 $C_i = \sum_{j = 1 } ^ {i} T_j$，答案就是 $\sum(L_i - C_i) = \sum L_i - \sum C_i$。要最小化 $\sum C_i$。有一个类似排队打水的简单贪心是按 $T$ 排序，这样 $\sum C_i = \sum_{j = 1} ^ n(\sum_{k = 1} ^ j T_k) = \sum (n - j + 1)t_j$。所以答案就是 $\sum L_i - \sum (n - i + 1)T_i$。
修改也不难，对 $T$ 的值域开棵线段树，维护：该区间内任务个数 cnt；该区间内 T 之和 tot；把该区间里的任务单独拿出来按 T 排序的 $\sum C_i$，记作 cost。考虑 pushup，右儿子的每个任务的完工时刻会被左儿子拖延 $tot[ls]$，所以我们有 $cost[x] = cost[ls] + cost[rs] + tot[ls] \times cnt[rs]$。
然后直接单点修改全局查询就行了。
D Gym104639H
对于一个周期 $p$，如果他不是 $S_k$ 的周期，他也一定不是 $S_{k + 1}$ 的周期，所以可以二分每个 $p$ 的“影响范围“ $t_p$，也就是 $p$ 是 $S_p \sim S_{t_p}$ 的周期但不是 $S_{{t_p} + 1} \cdots$ 的周期。显然每个 $S_k$ 是最终字符串 $s$ 的一段区间，所以判断 $p$ 是不是 $S_k$ 的周期等价于判断 $[L_k, R_k - p]$ 和 $[L_k + p, R_k]$ 是否相等，哈希即可。
于是对于每组询问，问题转化成找到 $p_l \sim p_r$ 内最小的数 $x$，满足 $t_x \geq k$。把询问离线下来按 $k$ 排序，把周期按 $t$ 排序，把 $t_{p_i}$ 大于等于当前的 $k$ 的 $p_i$ 加到线段树里，查区间最小值即可。
P5304
假设我们把特殊点分成 $A, B$ 两个集合，新建 $s$ 连接 $A$ 中所有点，边权为 $0$，新建 $t$ 连接 $B$ 中所有点，边权为 $0$，则 $s$ 到 $t$ 的最短路就是 $A, B$ 集合点之间最短路的最小值。
思考：以什么标准分几次组，才能使得两个不同的点一定在不同的集合？
两个不同的数，一定有至少 $1$ 位二进制位是不一样的。所以可以利用二进制位。
我们枚举二进制里的第 $i$ 位，将二进制第 $i$ 位为 $0$ 的放在 $A$ 集合，$1$ 的点放在 $B$ 集合，然后再反过来试一次。如此跑 $\log$ 次最短路后，所有最短路的最小值就是答案。
P6190
线性代数——矩阵、矩阵乘法、广义矩阵乘法 学习笔记 - RainPPR - 博客园
首先从暴力 dp 入手，讨论一下。设 $f[k][i][j]$ 为在使用不超过 $k$ 次魔法的情况下，从 $i$ 到 $j$ 的最短路。
- $k = 0$：直接 floyd
$k = 1$：枚举每条边，钦定对其使用魔法，则有
$$ f[1][i][j] = \min\{f[0][i][j], \min\{f[0][i][u] + f[0][v][j] - w\}\} $$
$k = 2$：类似 floyd
$$ f[2][i][j] = \min\{f[1][i][k] + f[1][k][j]\} $$
后面以此类推，发现这是一个 $(\min, +)$ 矩阵乘法的形式，直接矩阵快速幂转移即可。
ABC216G
ABC282E
把球两两连边，边权是分数，跑一遍最大生成树就做完了。
AT_cf17_final_j
QOJ9904
P5633
https://www.luogu.com.cn/article/ym8ixzr8
加强版：你需要对 $k=1,2,...,deg[s]$ 都输出答案
P9531
Day 2
95 + 100 + 75 + 100，T1 和 T4 是去年 noip 计划原题，有点有点了。
A
考虑怎么样最优：把 0 个数最少的一行填满，再将其复制到不满的每一列。
注意一个 corner case：钦定先填第 $i$ 行，若不存在 $(x, i)$ 是 1，那么要先从 $(y, x)$ 移一个 1 过来，此时答案要 +1。
B
对于第二条限制，可以理解成在一个环上从 $x$ 出发顺时针转，先转到 $y$ 再转到 $z$。于是有三种情况：$x < y < z, \space z < x < y, \space y < z < x$。然后你会发现第一种是简单的，第二种第三种都不好单独计算。直接考虑把后两种情况合起来，随便画一下发现这其实就等价于 $a < c$ 且 $p_a > p_c$，中间放个 $b$ 满足 $p_b > \max(p_a, p_c)$ 或 $p_b < \min(p_a, p_c)$ 的方案数。于是我们令 $cnt1$ 为 $a < b < c$ 且 $p_a > p_c$ 的方案数，$cnt2$ 为 $a < b < c$ 且 $p_a > p_b > p_c$ 的方案数，这两种情况的答案和就是 $cnt1 - cnt2$。
C
D
CF487E
P4214
P9907
https://www.luogu.com.cn/article/zct5tghe
P2341
没题号
给定 n，问有多少 n 个点的有标号无向图满足无重边无自环，且所有点度数为偶数。
先把前 $n - 1$ 个点之间随便连边，方案数 $2 ^ {\frac{(n -1)(n - 2)}{2}}$。那么最后一个点此时的连边方案是唯一的：必须和前面的每个当前度数为奇数的点连边。
于是方案数就是 $2 ^ {\frac{(n -1)(n - 2)}{2}}$。
CF788B
P9731
Day 3
100 + 30 + 70 + 0，好难啊好难啊好难啊好难啊。
y1 是关键字，不要用 y1 当变量名。
A
注意到费用的计算和题目顺序无关，只和每个题被分到了哪个人有关。所以我们可以枚举 $A$ 分到了几个题，然后前缀和随便算一通就做完了。
Bonus Track：体积 <= 2 的 01 背包，除排序外线性做法：类似 ARC201B。
B
C QOJ9449
D
y1 是关键字，不要用 y1 当变量名。y1 是关键字，不要用 y1 当变量名。y1 是关键字，不要用 y1 当变量名。y1 是关键字，不要用 y1 当变量名。y1 是关键字，不要用 y1 当变量名。y1 是关键字，不要用 y1 当变量名。
P2279
贪心地找深度最大的未被覆盖的点，并在其祖父处设立消防站。
CF708C
P4516
P3354
P5904
P8352
QOJ8528
QOJ2562
P14080
删边 MST。
首先对原图跑一遍最小生成树。如果删了非树边，是没有影响的；只有删了树边，才有影响。删一条树边，必然要找一个边权最小的可以连起来这俩连通块的非树边，加到新的 mst 里。然后我们反过来考虑，考虑一条非树边，能够对哪些树边造成贡献。对于非树边 $(x,y)$，$x \rightarrow y$ 路径上所有树边删除之后都可以改成这个非树边替代。
考虑维护，首先树剖可以，但是 2log 的复杂度很菜。我们可以先把边按照边权排序，每次选最小的非树边出来，暴力覆盖这条 $x \rightarrow y$ 的路径，一边合并，一边把 $(u, \text{fa}_u)$ 用并查集合并起来，具体实现上，我们只要把边挂在深度较大的点上就行，记得不能按秩合并，要不然可能会把父亲挂到儿子下面，导致死循环。
考虑正确性：因为这已经是最小的了，所以后面的非树边覆盖这个树边都比目前更劣。考虑复杂度：因为一条边只会被合并一次，所以复杂度也是对的，只会跳 $O(n)$ 次。
实现起来细节还是不少的。
Day 4
100 + 100 + 40 + 40，最正常的一集。
A
我咋被 A 卡了这么久？？？我咋被 A 卡了这么久？？？我咋被 A 卡了这么久？？？
通过连续段来刻画状态，设连续段长分别为 $x_1, x_2, \ldots x_k$，那么好子串个数就是 $n = \binom{m}{2} - \sum \binom{x_i}{2}$。设等号后面的是 $f(m)$，显然 $x_i = 1$ 的时候 $f(m) \max = \frac{m(m - 1)}{2}$，至少要好子串最多的时候 $\geq n$，所以 $m$ 最小要 $ \geq \frac{m(m + 1)}{2}$。构造很容易想，相当于要找 $\sum \binom{x_i}{2} = \binom{m}{2} - n$，直接贪心就好了，找每次找最大的 $\binom{x}{2} \leq d$，把 $d$ 减去 $\binom{x}{2}$， 01 交替填就好了，记得最后还有若干个长度为 $1$ 的连续段。
B
首先一棵子树内一种颜色的数量是 $\lfloor sz / 2 \rfloor$ 或 $\lceil sz / 2 \rceil$。设 $f[u][0/1]$ 表示 $u$ 为根的子树内红色个数为 $\lfloor sz / 2 \rfloor$ 或 $\lceil sz / 2 \rceil$ 的最小代价。考虑怎么用子树信息更新 $u$，首先如果先不考虑红蓝个数限制，对于每个子树我们可以贪心地选择红和蓝中代价较小的，然后考虑限制的话可以用一个类似反悔贪心的方式，如果子树大小是奇数，就把这个子树中等于 $\lceil sz / 2 \rceil$ 的那个颜色变成另一个颜色的代价记下来，从小到大排序，如果一个颜色超出限制 $d$ 个就将排名前 $d$ 的变成另一个颜色，然后讨论一下 $u$ 选哪个颜色就做完了。
C
D
真是太妙了！！！1
首先考虑朴素 dp，直接做有后效性，考虑倒着 dp：设 $f_{i, 1/0}$ 为当前进行到第 $i$ 轮，本轮之前 $i$ 有没有被翻转的情况下，先手减后手分数的最大值（定义当前回合操作的玩家为先手）。转移是简单的：
$$ f_{i, 0} = \max(a_i - f_{i + 1, 0}, a_i - f_{i + 1, 1}) \\ f_{i, 1} = \max(a_i - f_{i + 1, 0}, -a_i - f_{i + 1, 1}) $$
然后考虑优化。首先注意到 $f_{i,0}$ 和 $f_{i,1}$ 的转移式是非常像的，具体来说只有右半部分 $a_i$ 的正负号不同，于是可以发现有 $f_{i,1}\le f_{i,0}$ 一定成立。所以第一个式子可以改写成 $f_{i, 0} = a_i - f_{i + 1, 1}$。
然后很妙的一步就是令 $g_i = f_{i, 0} - f_{i, 1}$，代入上面的式子就有 $g_i = \min(g_{i + 1}, 2a_i)$，也就是 $g_i$ 是 $2a_i$ 的后缀最小值。
考虑算答案：答案等于 $\frac{f_{1, 0} + \sum a_i}{2}$。 $f_{i, 0}$ 还是不好维护，令 $h_i = f_{i, 0}$，那么
$$ f_{i, 1} = h_i - g_i \\ h_i = a_i - f_{i + 1, 1} = a_i - (h_{i + 1} - g_{i + 1}) $$
一直往下代入就可以得到
$$ h_1 = \sum_{i = 1}^{n} (-1) ^ {i - 1} a_i + \sum_{i = 2} ^ {n} (-1) ^ i g_i $$
维护前半部分是简单的，后半部分是一个带系数的后缀最小值和，类似楼房重建地用单侧递归线段树维护即可。
CF2152G
QOJ6355
QOJ8049
草八牛称其为拔河背包。
QOJ7607
P5972
Gym103428C
P5244
Day 5
100 + 0 + 40 + 0，t4 过大样例得 0 分，t3 是 noip 计划原题但我没补过，棒棒糖。
A
有点 edit 的感觉了/ll
先观察，他是一个从 1 开始往两边扩展的过程，记中间 0 的连续段长度为 $x_i$，开头 0 的连续段和结尾 0 的连续段长度为 $a, b$，答案下界显然是 $ans0 = \max(\max\{\lceil \frac{x_i}{2} \rceil \}, a, b)$。但是你考虑 010 这种情况，这个时候他就只能往一边扩展，扩展一遍之后又可以变成两边扩展的问题，所以答案可能是 $ans0$ 或 $ans0 + 1$。然后我们讨论要不要 +1，首先假设答案就是 $ans0$，然后记一下 $c_i$，表示这个 0 连续段能承受几次，第一轮的时候左右两边单独的 1 不往这边扩展，然后对于每个单独的 1，因为我们是从左往右考虑的，贪心地，如果可以的话尽量优先往左边先扩展，否则再往右边扩展（感性理解一下，因为我们是从左往右考虑的，所以往左扩展是没有后效性的，往右扩展就要考虑下一个 1），如果两边都不能承受第一轮的时候不往这边扩展了，就说明需要 + 1。
B LOJ6509
C
刻画子树的一个重要方式是 dfn 序。
先求出每个点的 dfn 序，那么每个点的子树内所有点 dfn 序是连续的，记 $L_u, R_u$ 是 $u$ 子树内 dfn 序的最小值和最大值。然后画出一个 $n \times n$ 的二维平面，$(i, j)$ 表示 $i \to j$。
考虑枚举所有 $n\log n$ 对满足 $a_u \mid a_v$ 的 $(u, v)$，考虑两种情况：
- $u, v$ 互不为祖先关系：此时某个端点在 $u$ 子树内，某个端点在 $v$ 子树内的路径均不合法，相当于删除掉以 $(L_u, L_v)$ 为左上角和 $(R_u, R_v)$ 为右下角的矩形，和以 $(L_v, L_u)$ 为左上角和 $(R_v, R_u)$ 为右下角的矩形。
- $u, v$ 互为祖先关系：不妨设 $u$ 是 $v$ 的祖先，找到 $z$ 使 $z$ 为 $u$ 的儿子且他在 $u \to v$ 的路径上，此时一个端点在 $v$ 子树内，另一个端点不在 $z$ 子树内的路径是不合法的，形式化的，一个端点在 $[L_v, R_v]$ 内，另一个在 $[1, n] - [L_z, R_z]$ 的路径是不合法的，这也是一些连续的区间，所以也可以刻画为矩形。
于是对于不合法的情况扫描线求矩形面积并，合法的路径数就是未被矩形覆盖的面积。共有 $O(n\log n) $ 个矩形，所以复杂度 $O(n \log^2n)$。
D
观察到 $A|B|C \rightarrow C|BA \rightarrow BAC$，所以把中间一段移动到前面的代价是 2。
做一个类似快速排序的分治，取一个阈值，然后类似快速排序的，把小于阈值的都移动到前面，把一段移动到前面的代价是 2。然后就做完了。
CF3D
CF525D
CF1848F
CF1310D
CF2048C
首先因为首位为 $1$，为了让位数最多，肯定要选 $[1, n]$。然后找到从左往右第一个 $0$，要把他变成 $1$，枚举符合长度的字符串取异或 max 即可。
CF2046B
很聪明的题。
首先观察，最后的数列一定是单调不降的，证明显然。定义逆序对里较大的数为 A 数。我们每一次操作肯定都只是操作 A 数。我们把初始序列中的 A 数从小到大移到后面，此时数列就变成了两个单调不降的序列。然后我们在还没操作的数中寻找新的 A 数移到后面，它们一定比第一轮找出的 A 数中最小的一个数操作完后大。所以将两轮找出来的所有 A 数加一，直接排序即可。
CF2096D
CF1407E
CF1854C
CF1827B2
CF1572C
CF1842F
Day 6
100 + 60 + 100 + 0，这破分能榜一，无敌了。
已在熨斗模拟赛中见到 3 道 NOIP 计划模拟赛题和 1 道作业题，绷不住了。
A
操作相当于把每个数拉到 >= 一个数（记作 $Z$）的位置，考虑 $\log_k a_i$ 意义下，二分 $\log_k Z$ 的整数位 $x$，把整数位都拉到 $x$ 后剩下的次数把小数位最小的几个填了。
题解有一个更简单的做法是，在 $O(n\log_{k}{a_i})$ 次操作后所有数的位数都一样了，然后直接 $O(1)$ 填即可，前面部分可以用一个堆模拟。
B
C P12448
D CF1456E
P5490
扫描线板子。
P1856
扫描线板子。
P10814
离线二维数点板子。
P1972
区间数颜色板子。简单记一下不然天天忘。
对于 $[l, r]$，区间右端点确定时，对于同一个数字，我们只关心其最后一次出现的位置。于是我们把查询区间按右端点排序，往右扫，树状数组维护当前右端点为 $r$ 时 $i$ 是不是 $a_i$ 最后一次出现的位置，扫到 $r$ 时答案就是 $[l, r]$ 区间和。
P4137
区间 RMQ 板子。简单记一下不然天天忘。
对于 $[1, r]$ 显然你记一下每个数字 $x$ 第一次出现的位置 $p_x$，然后二分找第一个 $x$ 使得 $p_x > r$。考虑左端点右移一位，其实就是把左端点的 $p$ 改成其下一次出现的位置，所以预处理出每个数下一次出现的位置，把查询离线下来按 $l$ 排序，线段树维护 $p$ 即可。
CF377D
P4899
P8512
P5524
P4348
P8421
P8955
P3863
P7560
P8518
P11368
Day 7
70 + 100 + 20 + 75，随机化王朝了随机化王朝了随机化王朝了。
A
这个都没做出来，我好笨/dk
容易发现可以把 $a_i$ 对 $T$ 取模，不会影响答案。然后把这些数都可以放到一个环上，问题变成在环上选一个 $[0, m- 1]$ 的点 $A$，使得 $A$ 到所有 $a_i$ 的距离最大值最小。$A$ 到所有 $a_i$ 的距离最大值等于 $T / 2 - d$，$d$ 为 $A$ 的对称点 $B$ 与离 $B$ 最近的点的距离。然后你考虑最大化 $d$，其实就是 $B$ 在最长空段的中点时 $d$ 最大，记最长空段是 $len$，答案就是 $\lceil \frac{T - len}{2} \rceil$。
B
性质：树的中心到其他任意节点的距离不超过树直径的一半。
首先为了不影响连通性我们每次应该只删叶子。部分分启示我们分奇偶讨论，偶数的时候可以枚举树的中心，把和他距离 $\geq 2$ 的点删掉；奇数的时候先枚举钦定一条边 $(u, v)$，然后找和 $u$ 或 $v$ 距离不超过 $\frac{n - 1}{2}$ 的点。距离直接 bfs 预处理出来。
C
D P7216
正解巨大无敌恶心，完全不如随机化啊。
问题可以转化为把矩形分成 $k$ 组使每组交集非空。为了让交集不空，要让每个矩形选取与其交集最大的组加入。我们每次把矩形顺序 shuffle 一下，将前 $k$ 个分成 $k$ 组，对于后面的矩形，让每个矩形选择交集损失最小的组加入，最后检查每个组交集是否均为非空。