做题笔记
flag：暑假之前做完近五年的省选题
当前进度 32/256
现在是鸽在这了
1.10
[HEOI2016/TJOI2016] 排序
给出一个 \(1\) 到 \(n\) 的全排列，\(m\) 次操作，对区间 \([l,r]\) 升序或降序排序，最后询问第 \(q\) 位置上的数。
一种二分的离线做法非常妙
二分最终答案 \(mid\)，把大于等于 \(mid\) 的数都赋为 \(1\)，小于 \(mid\) 的都赋为 \(0\)。这样区间排序就转化为区间查询 \(1\) 的个数，区间赋值。复杂度 \(O(m\log^2n)\)。
题解还有线段树分裂的做法，不会，等我学完再来写，可以做到 \(O((n+m)\log n)\)。
1.11
[HEOI2016/TJOI2016] 游戏
二分图的最大匹配，很套路一个模型。
二分图匹配两个要素：
-
“0”要素：节点能分成独立两个集合，每个集合内部有 0 条边
-
“1”要素：每个节点只能与一条匹配边相连
所以可以把每行、列的连续的一段看成节点，对于每个格子，在它所在的行段、列段之间连边。因为刚学最大流，所以写的 dinic，没调试一遍AC，泪目。
[HAOI2016] 食物链
难得一道省选大水题。前几天在谷群有人讨论食物链来着，还真有这么一个题。
以后做生物找食物链条数的题，当同学都在 dfs 爆搜，我就可以用 DP 做到 \(O(n)\)（雾）
1.12
[HNOI2016] 序列
给你一个序列，每次询问一个区间 \([l,r]\)，求其所有子区间的最小值之和。
莫队，处理这个 f[] 还是挺有技巧性的，不看题解想不出来。
以移动右端点为例，预处理
f[i]=a[i]*(i-pre[i])+f[pre[i]]; //pre[i]是i前面第一个比它小的数的位置（单调栈）
移动右端点，计算贡献
inline int calcr(int l,int r){
int p=st_query(l,r); //ST表做rmq
return (p-l+1)*a[p]+f[r]-f[p];
}
\(O(n\sqrt n)\) 就过掉了这题。当然也可以二维数点做，但有莫队谁写那玩意
1.13
[HNOI2016] 树
没啥高科技东西就是像模拟一样。但我主席树也写挂 LCA 也写挂导致调了2个多小时。
1.14
[JLOI2016/SHOI2016] 侦察守卫
做题经历：
这不就树形 DP？然后不会。
看一眼题解，妙啊，状态是这么设计的！然后还不会。
再看亿眼题解，妙啊，是这么转移的！然后写挂了。
最后几乎是照着题解打了一遍，大概是会了（？）
1.15
[ZJOI2017] 仙人掌
给你一个图，问有多少不同的加边方案把它变成仙人掌。
先把原来环上的边去掉变成一堆树。
每加边形成一个环，就相当于覆盖了树上的一条链（仙人掌上的割边可以看成重边构成的环），问题就转化成有多少种不同的方案把树上所有的边不重不漏的覆盖（这样才保证形成的是仙人掌）。
注意到只有链经过点时是切断还是选择一条边走出去会影响答案。
记度数为 \(i\) 的点对答案贡献为 \(f_i\)，就有
\[\begin{cases}f_i=1 &i=0,1\\f_i=f_{i-1}+(i-1)\times f_{i-2} &i\ge 2\end{cases} \]答案就是 \(\prod f_{deg_i}\)。感觉比昨天那个好理解多了，这题我觉得都不配叫 DP
判断仙人掌这个第一次遇到，调了好长时间最后是因为多测没初始化淦。
bool vis[maxn];
int pos[maxn],stk[maxn],top,dfn[maxn],idx;
bool dfs(int x,int e){
stk[++top]=e,pos[x]=top;
vis[x]=true;
dfn[x]=++idx;
for(int i=head[x];i;i=edge[i].next){
if(i==(e^1)) continue;
int y=edge[i].to;
if(vis[y]){
if(dfn[y]>dfn[x]) continue;
edge[i].del=edge[i^1].del=1;
deg[x]--,deg[y]--;
for(int j=pos[y]+1;j<=pos[x];j++){
if(edge[stk[j]].del) return false;
edge[stk[j]].del=edge[stk[j]^1].del=1;
deg[edge[stk[j]].to]--,deg[edge[stk[j]^1].to]--;
}
continue;
}
if(!dfs(y,i)) return false;
}
top--;
return true;
}
1.16
[ZJOI2017] 树状数组
原问题能转化为：长度 \(n\) 的序列初始都是 \(0\)，\(m\) 个操作，在区间 \([l,r]\) 随机选一个数加一，询问两个位置上数奇偶性相同的概率。
\(x\) 与 \(y\) 相等的概率记作二元组 \((x,y)\)。可以用二维线段树维护（矩形区间修改，单点查询）。
设之前 \(x,y\) 相等的概率为 \(p\)，一次操作不改变它的概率为 \(q\)，则操作后 \(x,y\) 相等的概率为 \(p\times q+(1-p)\times (1-q)\)。
设修改区间为 \([l,r]\)，分类讨论：
-
\(x\) 在 \([1,l-1]\)，\(r\) 在 \([l,r]\)，变化的概率 \(1-q=\dfrac{1}{r-l+1}\)
-
\(x\) 在 \([l,r]\)，\(y\) 在 \([r+1,n]\)，变化的概率也是 \(1-q=\dfrac{1}{r-l+1}\)
-
\(x,y\) 都在 \([l,r]\) 中，变化的概率 \(1-q=\dfrac{2}{r-l+1}\)
\(x=0\) 的（前缀是否等于后缀）还要单独讨论，若 \(y\) 在 \([l,r]\) 中，不变的概率为 \(q=\dfrac{1}{r-l+1}\)，否则一定改变了 \((q=0)\)。
有意思的是，这个概率的叠加满足结合律，线段树不用下传标记（这大概就叫标记永久化？），代码十分简洁。
这是我第一次写二维线段树，照着题解敲了一遍，感觉比什么树状数组套主席树好写多了（
int mul(int p,int q){ //概率叠加
int res=(ll)p*q%mod;
res=(res+(ll)(1-p)*(1-q)%mod)%mod;
return (res+mod)%mod;
}
void modifyy(int &p,int l,int r,int x,int y,int v){ //第二维修改
if(!p){ p=++tot;tr[p].val=1; }
if(x<=l&&y>=r){
tr[p].val=mul(tr[p].val,v);
return;
}
int mid=l+r>>1;
if(x<=mid) modifyy(tr[p].lc,l,mid,x,y,v);
if(y>mid) modifyy(tr[p].rc,mid+1,r,x,y,v);
}
void modifyx(int p,int l,int r,int lx,int rx,int ly,int ry,int v){ //第一维
if(lx<=l&&rx>=r){
modifyy(rt[p],1,n,ly,ry,v);
return;
}
int mid=l+r>>1;
if(lx<=mid) modifyx(p<<1,l,mid,lx,rx,ly,ry,v);
if(rx>mid) modifyx(p<<1|1,mid+1,r,lx,rx,ly,ry,v);
}
int queryy(int p,int l,int r,int x){ //第二维查询（单点查询）
if(!p) return 1;
if(l==r) return tr[p].val;
int mid=l+r>>1;
if(x<=mid) return mul(tr[p].val,queryy(tr[p].lc,l,mid,x));
return mul(tr[p].val,queryy(tr[p].rc,mid+1,r,x));
}
int queryx(int p,int l,int r,int x,int y){ //第一维
if(l==r) return queryy(rt[p],1,n,y);
int mid=l+r>>1;
int tag=queryy(rt[p],1,n,y);
if(x<=mid) return mul(tag,queryx(p<<1,l,mid,x,y));
return mul(tag,queryx(p<<1|1,mid+1,r,x,y));
}
1.17
周末。。颓了一整天没做题。
1.18
[CQOI2017] 小Q的棋盘
一棵树，从跟出发，问走 \(n\) 步最多经过多少点，重复经过只算一次。
又是 DP，f[i][j] 表示从 \(i\) 出发走 \(j\) 步最多经过点数，g[i][j] 表示从 \(i\) 出发走 \(j\) 步并回到 \(i\) 最多经过点数。则有转移
f[x][j]=max(f[x][j])
1.19
[SDOI2017] 序列计数
快速幂，算一个卷积，从而优化朴素 DP，可能这就叫生成函数（？）不太会
1.20
[SDOI2017] 新生舞会
费用流，
以后二分范围一定要认真算！！否则多跑了十多次费用流直接 T 飞。。
1.21
写whk作业==
1.22
[CQOI2017] 老C的方块
最小割，妙啊！