Day 1
noip模拟赛。
T1：
给出一个n，将其分解为\(\frac{a!}{b!}\)的方案。
由于阶乘的数值巨大,13的阶乘就已经爆int了，所以二分 + 枚举解决。
T2:
蜜汁构造题，思考10分钟后直接跳过。
T3:
数据结构题，考场想到86分的\(O(nlog^2)\)超劣解法，需要在线段树的每一个节点上开\(vector\)，查找时再在\(vector\)上二分。但是考场一直因为\(vector\)的边界与lower_bound的返回值疯狂Re。没调出来悲……
正解：对序列离散化+离线，重点是顺序遍历1~n，再用树状数组维护操作的时间编号。
下午数据结构。
写P7880 [Ynoi2006] rldcot，发现set的时间波动极抽象（可能是因为红黑树的原因），所以记得常数优化。
Day 2
noip模拟赛。
T1：
矩阵求（1，1）到（n，m）的回文路径数。
第一题就是DP，直接去世。
暴力枚举左上角和右下角 DP，复杂度 \(O(n^4)\)。 观察到只有\(x1 + y1 + x2 + y2 = n + m + 2\)的状态才有用，因此我们枚举 \(x1\), \(y1\), \(x2\) 即可得知 \(y2\)，复杂度降为 \(O(n^3 )\)。
由于在考场上直接去想\(O(n^3 )\)导致dp状态有问题，最后只拿到暴力分。
T2:
完全可做，但考场经验不足，开题顺序有问题，没时间写正解了……
T3：
又又又又是构造题……
下午扫描线。
主要思想：离线 + 数据结构
一维
（1）区间查包含点数：
离线，枚举每个位置对应的询问端点，树状数组+差分
（2）区间查包含子区间：
离线，将子区间\([l, r]\)看作二维中\((l,r)\)的点，当\([L,R]\)包含\([l,r]\)当且仅当\(L \leq l \leq r \leq R\)。在二维中表现为点\((L,R)\)在\((l,r)\)的左上方,所以从右往左遍历x轴，树状数组维护。
（3）维护与查询区间：
暴力：\(n^2\)枚举。
线段树：\(nlogn\)，离线，从左往右遍历R，对于当前R线段树的节点x，表示\([x,R]\)的信息,线段树的区间\([l,r]\)表示$[l,R],[l+1,R]……[r,R] $的信息，R++，思考转移。
网络流
可解决图论中多重贡献与不完全贡献的问题。
Dinic
注意事项：
1.建反边
bk[u].push_back(V[v].size());
bk[v].push_back(V[u].size());
2.dis,now数组清空
memset(dis, 0, sizeof(dis));
memset(now, 0, sizeof(now));
3.dis[S]赋值为1不为0
if(!dis[v] && flw[u][i])
如果赋值为0这会出大问题
4.1次bfs应跑完dinic
while(bfs()){
while(f = dinic(S, INF))
res += f;
}
5.关于当前弧优化
错误：
for(int i = now[u]; i < V[u].size(); i = now[u])
now[u]++;
正确：
for(; now[u] < V[u].size(); )
now[u]++;
因为当u的儿子v重新遍历到u且更新now[u]时， u这一层的i并未改变。（GGGG）
优化：
if(u == T || !flow){return flow;}
2.当前弧优化与判断res
for(int i = now[u], v; i < V[u].size() && res; i++)
if(!k) dis[v] = 0;
关于输出最大流方案：
图中bfs+dinic后的所有dis大于0的点。
对于净值的计算，即最小割，对于每个点计算min（入度权值和，出度权值和）。
二分图
trick：
（1）处于同一集合的点可以随意交换位置，所以A[i]——B[j]交换为A[j]——B[i]不影响最大匹配。
逆元
（1）递推题注意别在循环中求逆元\(O（nlogn）\)。
（2）关于逆元，\(\frac{1}{n} = \frac{1}{nm} *m\), 所以\(n^{-1}=m^{-1}n^{-1} * m\)。于是先求右端点逆元再从右往左推。
y[n] = mpow(mpow(a + b, n), mod - 2);
for(int i = n; i > 0; i--)
y[i - 1] = mul(y[i], a + b);
线性求逆元。
inv[0] = inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = mul(mod - mod / i, inv[mod % i]);
（3）也就是说逆元满足乘法的但部分性质，可像乘法一样使用。
（注）inv(n) 是 \(\frac{1}{n}\)，而不是\(n\)。
小细节
1
（1）滚动数组清空
（2）手动O(2)
#pragma GCC optimize(2)
2
（1）子树合并时先全部计算再全部合并
（2）\(l < i,j<r\) 时 \(i， j\) 可以相等
（3）在for中定义变量时注意类型（\(longlong\)）
（4）set不稳定注意卡常
3
（1）递推题注意别在循环中求逆元\(O（nlogn）\)。
（2）关于逆元，\(\frac{1}{n} = \frac{1}{nm} *m\), 所以\(n^{-1}=m^{-1}n^{-1} * m\)。于是先求右端点逆元再从右往左推。
y[n] = mpow(mpow(a + b, n), mod - 2);
for(int i = n; i > 0; i--)
y[i - 1] = mul(y[i], a + b);
线性求逆元。
inv[0] = inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = mul(mod - mod / i, inv[mod % i]);
（3）\(t = m / 2, m \neq 2 * t\)（当m为奇数时）。
4
栈：
可以用来解决类似消消乐的问题。
栈满足许多美妙的性质。
可维护一些等价元素间的删除、合并、顺序。
消消乐：
