NOI 模拟赛（I）
冲刺国赛5月2日第二场
\(t1\) 沉迷前缀和无法自拔，觉得扫描线是离散位置修改不好操作，没想到其实有零的情况只多了一点点
\(t2\) 在想回滚莫队，但是撤回操作不会很好地处理，并没有领会随机的意图……
\(t3\) 来者不善又是 \(FWT\)……
A. a
以 \(i\) 为右端点的最远左端点可以递推出来，虽然修改位置是离散的，但是只有 \(01\) 两个，用线段树可以很方便地维护出来（白学了半天线段树）
B. b
把询问划分为多个区间完全包含的序列，可以发现个数为 \(\sqrt n\) 的
对于每一个分别跑吉老师线段树即可
冲刺国赛5月4日第三场
考场上成功通过打表得到 \(t1\) 所有性质，写完还得自己造数据，还被hzoj的阴间重测方式坑成零分
\(t2\) 想错没有发现矩形的合并关系
\(t3\) 拿上错误的 \(n^2\) 和错误的特殊性质对拍拍过了……
B. 铃原露露
以 \(z
而如果采用启发式合并，同时枚举 \(x,z\) 的复杂度是可以接受的
对于剩下的问题就是矩形加，求空白和
通用的方法是线段树维护历史版本最小值个数和，不过由于矩形的特殊的位置，可以用普通线段树+并查集直接维护
冲刺国赛5月9日第六场
\(t2\) 通过打表发现 \(n=2k+1\) 时 \(ans=2Cat(k+1)\) 的特殊关系，通过修正原先推出的错误表达式懵出正确式子
\(t3\) 愣是一个小时每调对个 \(tarjan\)……
先来写一下题解的思路，首先形式化地刻画答案为 \(n-\) 左括号数\(-\)最大前缀和
枚举答案为 \(z\)，求出 \(\ge z\) 的答案，每次左右括号的选择刻画为格点上的行走方向，转化为了格点计数问题
C. 防御工事
缩点虚树没得说，这个细节着实多……
- 非割点军队当前点有一的贡献
- 同一点双中贪心选择一个
- 边并不能忽略，需要加入两个相邻割点（
还是说理解错题解了）
冲刺国赛5月10日第七场
B. 树上游走
考虑转移：
\(f[u][1]\)：对于子树父亲不能走，\(f[v][2]\)
设 \(sum=\sum_{v!=u}f[v][1]\)
\(f[u][0]\)：
- 进入子树后不返回，\(f[v][2]\)
- 返回
- 立即返回（儿子经过一次），\(\frac{1}{(d_v+1)d_u}(f[v][1]+sum)\)
- 走过一条链（系数 \(1-p_v-\frac{1}{d_v+1}\)）
- 只有一个儿子，\(a_u\)
- \(\frac{1}{d_u-1}sum\)
\(f[u][2]\) 和 \(p\) 类似，只不过总情况为 \(d_u+1\)
C. 树的同构
首先枚举一条分隔边将树分成两个连通块并分别指定两个连通块中的根是哪个
设 \(f[i][j]\) 表示第一棵树的 \(i\) 和第二棵树的 \(j\) 匹配，子树内最多匹配多少个
可以发现子树内的信息相当于是以 \(f[u][v]\) 为边权的二分图最大权匹配