journal

· · 个人记录

3.1

a.m 复习 （学习） 网络流 ： 最大流（最小割），费用流，最大权闭合子图

p.m（练习题目： Construction of a tree

美食节 （分层动态加点费用流：加 入当前增广的下一层边)

Biologist （操作连锁：最大权闭合子图）

总结 : 号爸那边在模拟题，然而还没有人给我发题，于是在某谷上找点网络流的题单写

感觉网络流还挺常用，就是不看题解就不知道咋建图，ww

3.2

网络流模型建立练习

（练习题目：奇怪的游戏 （SCOI2012) (二维 邻点操作黑白染色跑网络流 )

附：最大流中 

if(x==t||!in) return in;// 加（！in) 会快很多（泪目）

支线剧情 （最小费用可行流：边有流量上下界—> 补流思想

80人环游世界 （对点强制要求过 v_i 次 ： 利用费用流特性连边 -inf 强制流满

add(i,i+n,m,-inf);sum+=m;
--------------------------------
while(spfa()) ret+=dis[t]*mi[t]; 
    print(ret+sum*inf);

总结 ： 充分了解算法实现原理和成效才方便建立模型以及魔改

3.4

a.m 网络流模型建立练习

（练习题目：志愿者招募 （一面对多面的转化问题 )

​ happiness 带限制的权值 max= sum - 最小割

p.m 号爸的题

​ 棋盘游戏 （黑白染色，二分匹配 ： 所有最大匹配中都被匹配的关键点 —— > 二分图最大匹配关键点）

远行 (动态维护树直径：前置知识 <u>LCT</u> 用于维护点间距离 Link Cut Tree（超强数据结构：练习题目Tree II ） )

总结 ：splay 真是太好用了 ， 虽然比 treap 难写一点 ...

感觉LCT挺实用的，虽然但是，写出来太痛苦了（第一次写 debug 三小时 ww），之后还是敲一点例题练一下熟练度

3.5

a.m LCT 练习

洞穴勘测 ( Find 函数用于确定是否在一个连通块)

p.m 模拟赛

总结 ： T1 和之前写过的题很像，顺利地切了

$T3$ 把强制在线的转化内容看错了，导致样例没看懂， （大悲 ## 3.6 a.m $LCT$ 练习 [魔法森林](https://www.luogu.com.cn/problem/P2387) （ $LCT$ 维护最小生成树 ： 把 $x$ 转到根 只能用 $splay$ 不能用 $Root$ ,还没搞懂为啥 [树点涂色](https://www.luogu.com.cn/problem/P3703) （ $access$ 的应用 ：神题啊！！！ 吐槽一下我的 之前的 $LCA$ 之 $while$ 写法 ，$re$ 直接让我 $debug$ 俩点 $new 
int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

p.m 补题

Card Deck Score 生成函数，系数推导

3.7

a.m LCT 练习

网络 (多颗 LCT 大水题 

v[x]=___;   splay(x);  // 单点fix

注意出错点

vd link(int x,int y){Root(x);fa[x]=y;return；} //no xie fa[y]=x

p.m NNT 复习 （G_i =332748118 , Mod = 998244353 , G =3

（数组大小开 4 倍 ！！！

学习 ： 分治FFT f_i=\sum_{j=1}^if_{i-j}g_j ,f_0=1可以用多项式求逆解决 证明

多项式求逆 （ 傻XUAN看得懂的数学证明

（练习题目 ： 简单计数