R1
rk10-。220pts。
T23 都读错题。浪费了将近 60 分钟。改。
T2 对于组合的掌握仍然不够熟练。找规律考虑每个点的贡献，应该使用 0/1，而不是原数。转化过后可以在 01 矩阵上找规律了。（现在还是没搞懂那个原理）
=》 组合 \((i, j)\bmod 2 = 1\)，当前仅当 j 在二进制下是 i 的子集，根据这个高维前缀和。
T4 的套路：乘法构造可以根号分治。（<= sqrt 表示当前 mul；<= 2sqrt 表示还要多少 mul）
R2
rk20+。90pts。绑点要求不挂分的能力。
T1 这种小傻逼题目要加强练习。必须做出来。
部分分打完过后一定对拍，不要依赖大数据，假的。（T3 分层图+lsh错 3 个点挂 0）
T2 的 ODT get 到了，新知识。
T3 感觉是道很好的题，通过性质优化最短路的选择。反正我思考了很久。
不骄不躁，不气馁，做好每一步就是。
R3
rk6。265pts。
还好 T1 对拍了，不然要挂惨。
T4：被兔子骗了，一眼分块。和弹飞绵羊真的太像了。
考虑：记录 i 在块外的第一个节点 Fa[i]，然后按照树剖 LCA 求两点 LCA 即可。同时维护小块 LCA fa[i]。
对于修改：整块维护修改次数，如果修改次数 >= sqrt n，那么一定会跳到块外，标记即可；否则直接暴力重构。
注意暴力重构后还要重新更新一遍 vis。
时间为 ： \(n^{3/2}\)
T3 是个抽象题。
T12 的简单思维花的时间有点久，需要多练。不过好在 T2 最好想出来了，说明刷的 CF 还是有用的，实力尚在。
R4
rk9。202pts。
T1 求最短路边数，裸题。但是理解题目用了很久，需要增强阅读理解能力。
T2 错在 dp 的状态设计，其实认真想一想根本就不用记录上一个的具体值。相对关系定下来，i-2 和 i 没有任何关系。到这里就可以放心优化了。
这里对于重复的 change 处理是新 trick！
T3 神秘题，n3 居然没有 n4 快。我们应该看看 n2log的做法。to be updated……
T4 我的 dp 少打了一维（使得看就知道是错误的），不然结合特殊性质就是 55 分，直接进 rk5。主要是最后 5 分钟慌了，但是为什么要慌呢。稳住！
R5
rk16? 120pts。
思维场 & 数学场。
T1 对树形 dp 不够熟练啊。下面我们来逼一下自己一行一行地阐述代码。
void dfs(int x, int fa) {
siz[x] = 1; dp[x][0] = dp[x][1] = 0;
// dp 初始化 给 0/1 表示只考虑这个数本身的
// 又由于到了父亲才能计数，所以暂时给 0，与 inf 区分
val[x] = a[x];
for(auto r : G[x]) {
int to = r.first, V = r.second;
if(to == fa) continue ;
dfs(to, x);
for(int j = 0;j <= num; ++j) g[j] = inf;
// 当前的子树更新答案，为了防止错误，单独开一个数组记录
// 主要是为了区分【子树内】和【子树外】的。
for(int i = min(num, siz[x]);i >= 0; --i)
for(int j = 0;j <= min(siz[to], num) and i + j <= num; ++j)
g[i + j] = min(g[i + j], dp[x][i] + dp[to][j] + V * abs(val[to] - (j + sum * siz[to])));
// 加的这一坨是当前子树所必须代价
for(int j = 0;j <= num; ++j) dp[x][j] = g[j];
siz[x] += siz[to]; val[x] += val[to];
}
}
T2 就是个 sb 思维，说明还需要多练。并且敢想。
标签：NOIP,int,T4,T2,T3,T1,模拟,初三,dp From： https://www.cnblogs.com/Lovely-Cat/p/18172638