重庆外培游记

· · 个人记录

记录生活没有什么用，不如记录知识。

回顾过去的一年，无论在文化课还是竞赛我都是非常失败的。尤其是竞赛，虽然都没怎么花费精力，但是对于有脚就行的 tj 省一和省队竟然都能放走，越想越失败，人输不过如此吧。看 NOI 游记越看越痛。。

我每天无所事事的程度甚至经常让我怀疑生活的乐趣，如果一个人颓废了，那他真的会觉得活着很无聊。我就是这样啊。

Day1 全局平衡 DDP

主要讲了全局平衡二叉树和动态 DP，说了很多例题，可是我根本听不进去，因为我用了一上午才搞明白这个全局平衡二叉树。主要是没写过树剖平衡树。

全局平衡二叉树，这里不讲线段树实现了。

对于树剖，有两种处理方式，一种是对于每个重链单独维护数据结构，另一种是把所有链连续的放到一起，整体处理。第二种更方便处理子树修改，但全局平衡二叉树是第一种。

正常的树剖对于大多数操作都是双 log 的，但是由于我们用的是平衡树，所以可以用一种很特殊的平衡方式，让我们在多个平衡树上跳的时候能保证整体复杂度是单 log 的。

对每个重链单独建平衡树，按照权值，而权值就是 siz[x]-siz[son[x]]，也就是所有轻儿子的子树大小加 1，注意必须加 1。注意不是直接按照权值本身的大小建平衡树，而是权值在重链上的前缀和（可看代码），这样我们每次从平衡树上的节点网上跳的时候，不管虚边还是实边，子树大小一定会翻倍，于是我们就把这个 log 从每条链上转移到了整棵树上，实现了消 log的操作，当然这都是静态操作。

建树代码：

int sbuild(int x,int y) {
    if(!x||fa[x]==y) return 0;
    int sum=0,anx=0,i;
    for(i=x;i&&fa[i]!=y;i=son[i]) sum+=val[i];
    for(i=x;i&&fa[i]!=y;i=son[i]) 
    {
        anx+=val[i];
        if(anx*2>=sum) break;//这就能保证平衡性了 
    }
    T[i].ls=sbuild(x,fa[i]);//分开递归建树 
    T[i].rs=sbuild(son[i],y);
    if(T[i].ls) Fa[T[i].ls]=i;//实边要认父认子 
    if(T[i].rs) Fa[T[i].rs]=i;
    pushup(i);
    return i;
}

int build(int x) {
    if(!ed[x]) return x;
    for(int j=x;j;j=son[j])
        for(int i=h[j];i;i=e[i].nx)
            if(e[i].v!=fa[j]&&e[i].v!=son[j]) {
                int p=build(e[i].v);
                //虚边的连接要改为平衡树根节点与原父亲的连边 
                Fa[p]=j;//虚边认父不认子 
                g1(j)+=f0(p);
                g0(j)+=max(f0(p),f1(p)),g00(j)=g0(j);
            }
    int rt=sbuild(x,ed[x]);
    T[rt].f=T[ed[rt]].f*T[rt].sm;
    return rt;
}

全局平衡二叉树常与树上动态 DP 连用，动态DP很好理解，就是把 DP 式子转为矩阵，把修改操作转化为链操作。

例题会补。

Day2 zkw线段树

除了动态开点，zkw 可以解决任何线段树能解决的。说下 zkw 基本操作，不深入研究了，大概率用不到。完全二叉树，一般要记一下最底层第一个节点。支持区间修改区间查询，注意标记永久化，位运算优先级！！

Day3 最小生成树

关于图论这一块，我其实欠缺很多，很多只会打板子，稍微扩展一下就不会了，需要刷题。 （必须锐评 hf 啥也不讲）

Borůvka's algorithm

我们先回顾一下 prim 和 kruskal 。prim 类似 dijkstra ，一个节点一个节点往里加，然后把边扔堆里（和 dij 的区别是一个扔的是直接连的边，一个扔的是单源最短路）。kruskal 更直接，把所有边排序，用并查集维护连通块，从小到大枚举边，没连的就连。

Borůvka 就是结合一下，每次操作，找出每个连通块向外的最小边，然后把连通块合并，复杂度 log 级。Borůvka 的优点是对于边权依靠点来计算的情况，如 w(e(x,y))=f(x,y) 的情况，固定点 u，找点 u 所在连通块外一点 v 使得 f(u,v) 取到最小值往往是不用暴力枚举的。

异或最小生成树：

看到异或我竟然没有第一时间想到 Trie 树，很失败。 具体做法：用一个Trie 树维护所有点，再用多个 Trie 树维护每个连通块，每次遍历每个点，找到不在连通块里的异或最小值，然后再整个连通块考虑向外的最小边，合并连通块时合并 Trie 树，这里应该需要启发式合并？ 总复杂度双 log。 Trie树不熟，贴下代码。（我一开始并查集写错了。。） 一定要去重 ~~（我看的讨论区）~~，不然会死循环。 ```cpp #include<bits/stdc++.h> using namespace std; const int N=2e5+2; inline int qr() { int k=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {k=(k<<1)+(k<<3)+(ch^48);ch=getchar();} return k; } int c[N*60][2],siz[N*60],idd[N*60],tot; void insert(int &p,int x,int dep,int id) { if(!p) p=++tot;++siz[p]; if(dep==-1) return (void)(idd[p]=id); insert(c[p][x>>dep&1],x,dep-1,id); } long long ans; int ask(int p1,int p2,int x,int dep) { if(dep==-1) return idd[p2]; bool nx=x>>dep&1; if(siz[c[p2][nx]]-siz[c[p1][nx]]>0) return ask(c[p1][nx],c[p2][nx],x,dep-1); else if(siz[c[p2][nx^1]]-siz[c[p1][nx^1]]>0) return ask(c[p1][nx^1],c[p2][nx^1],x,dep-1); printf("%lld",ans);exit(0); } void merge(int &p1,int p2) { if(!p1||!p2) return (void)(p1=p1+p2); siz[p1]+=siz[p2]; merge(c[p1][0],c[p2][0]); merge(c[p1][1],c[p2][1]); } int n,a[N]; int Rt,rt[N],mn[N],to[N]; int f[N]; int find(int x) { return f[x]==x?x:f[x]=find(f[x]); } signed main() { n=qr(); for(int i=1;i<=n;i++) a[i]=qr(); sort(a+1, a+1+n); n=unique(a+1,a+1+n)-(a+1); for(int i=1;i<=n;i++) insert(Rt,a[i],30,i),insert(rt[i],a[i],30,i),f[i]=i; while(1) { memset(mn,0x7f,sizeof mn); for(int i=1;i<=n;i++) { int v=ask(rt[find(i)],Rt,a[i],30); if((a[i]^a[v])<mn[f[i]]) { mn[f[i]]=a[i]^a[v]; to[f[i]]=v; } } for(int i=1;i<=n;i++) { if(find(i)==find(to[find(i)])) continue; merge(rt[f[to[f[i]]]],rt[f[i]]); ans+=mn[f[i]];f[f[i]]=f[to[f[i]]]; } } return 0; } ``` [最小公倍树：](https://www.luogu.com.cn/problem/P8207) 与上题类似，边权为点权 lcm。 为啥我感觉其实 borůvka 的题往往都可以用传统做法做啊。 先口糊 borůvka 的做法（总觉得复杂度不太对）：把每个数分解质因数，然后让他的每个质因子，像它自己连一条边。然后每个连通块往外找最小边的时候，就枚举这个数的质因子，再通过质因子往外找其他包含这个质因子里面最小的不在一个连通块里的。我总觉得复杂度最坏 3log？ 还是 kruskal 的方法好理解，枚举公因子连边，显然对于含有同一个公因子的数，只需要让他们与最小的数连边就好了，根据调和级数（话说我今天才知道这玩意），我们总共最多建 nlogn 条边，于是就解决了。写代码用时 6min。 ~~（我不会告诉你我因为数组大小重交了 5 次）~~ [线段树分治：](https://www.luogu.com.cn/problem/P5787) 关于时间的分治，后面要用到，学一下。 做这道题首先是判断二分图，有一个很容易忘了名字的东西，叫扩展域并查集，其实就是把一个点 p,拆成 p 和 !p ，然后每次连边 u，v 就把 u 和 !v 连起来，把 v 和 !u 连接起来，判断同理。 我一开始没有太理解线段树分治和暴力的区别，xht 的题解很清晰，其实差别主要就在删边后的判断上，线段树分治对时间分治后，如果在一个节点已经不满足二分图，那么它下面的所有叶子节点一定不满足，这里就省去了判断！也就是说当我们递归进一个节点的时候，它之前的边一定保证了它满足二分图。而暴力在进行撤销操作删边的时候，我们只能再次 $O(n)$ 的判断是否合法，而且暴力在对已经不是二分图的边进行 merge 时也会出问题。线段树分治很神奇！ 代码实现非常优雅，需要背板： ```cpp struct Eg{int u,v;}; vector<Eg>eg[N<<2]; typedef pair<bool,int> P; stack<P>st; int n,m,k; #define ls p<<1 #define rs p<<1|1 int f[N*2],h[N*2]; inline int fd(int x) { while(f[x]!=x) x=f[x]; return x; } inline void merge(int x,int y) { if(x==y) return ; if(h[x]<h[y]) swap(x,y); st.push(P(h[x]==h[y],y)); h[x]+=h[x]==h[y];f[y]=x; } void update(int p,int l,int r,int u,int v,int L,int R) { if(l>=L&&r<=R) return (void)eg[p].push_back((Eg){u,v}); int mid=(l+r)>>1; if(mid>=L) update(ls,l,mid,u,v,L,R); if(mid<R) update(rs,mid+1,r,u,v,L,R); } void dfs(int p,int l,int r) { int o=st.size(),mid=(l+r)>>1; bool flag=1; for(int i=0;i<eg[p].size();i++) { int u=fd(eg[p][i].u),v=fd(eg[p][i].v); if(u==v) { for(int j=l;j<=r;j++) puts("No"); flag=0;break; } merge(u,fd(eg[p][i].v+n));merge(v,fd(eg[p][i].u+n)); } if(flag) { if(l==r) puts("Yes"); else dfs(ls,l,mid),dfs(rs,mid+1,r); } while(st.size()>o) h[f[st.top().second]]-=st.top().first,f[st.top().second]=st.top().second,st.pop(); } ``` ~~我肯定不会说我这题交了10遍才过~~ [城市建设:](https://www.luogu.com.cn/problem/P3206) 学了线段树分治还是不会的神仙题。 题解都没证明，就说了做法。有时候一些很显而易见的做法复杂度却是惊人的正确？ 我只能想到一种感性的证明方法。 先说做法：线段树分治，然后对于当前的区间 $[l-r]$，先把这些边设为负无穷，判断一下其他有哪些边是必选的，再把这些边设为正无穷，判断一下有哪些边必不选。 感性证明：这个负无穷正无穷本质上是吧那些与 $[l-r]$ 这些边相连的点无关的边确定下来，对于一个区间 $[l-r]$ 它们最多连 $2(r-l)$ 个点，而与这些点无关的其他边的存亡都可以确定下来，因此不确定的只有与这 $2(r-l)$ 个点有关的边。整张图一共 $2.5n$ 条边那么我们就可以均摊地认为此时边的规模缩到了 $5(r-l)$？ 调了好久，拍子真是个好东西！！我这个设计的很奇怪，我看题解的递归函数参数都很少，我直接把 vector 递归进去了。代码太长，放个[链接](https://www.luogu.com.cn/record/list?pid=P3206&orderBy=0&status=&user=%E8%81%8A%E6%9C%BA&page=1)。 [powertree](https://www.luogu.com.cn/problem/CF1120D) 很妙秒的一道题，我们把操作转为修改差分值，每个点只要可以被修改到差分值，就可以了，修改一个节点相当于把它子树里 dfs 序的最小的差分值挪到 dfs 序最大的那个点上，那么就可以把每个点对应的子树的 dfs 序所在位置连边，跑最小生成树。 kruskal 重构树，在补。 lct，在补。 ## Day 4 最短路 单源：dij，spfa。全源：floyed。 先讲一个小 **trick**，就是对于边权非常小的情况，我们求单源最短路实际上可以优化掉一个 log，就是用桶排代替 dij 里的堆排，[水题](https://www.luogu.com.cn/problem/CF843D) ~~(然而我交了好几次才过）~~ 这题要注意特判如果 add 值太大显然是不可取的，就不要往桶里放，不然会 RE（不要问我怎么知道的）。~~10 秒时限还要开 200 个数据点，不愧是 cf。~~ **同余最短路**，以前没听过，其实也算是个像差分约束一样的小 trick，把形如由几个整数组成另外一个整数的问题抽象成图论问题。具体就是选其中一个数（一般是最小的，因为剩余系最小），把它的每种余数当成一个点，然后枚举其他数字建边，跑最短路，看最少用多少就可以到达这个余数。 [板题](https://www.luogu.com.cn/problem/CF986F)（cf 很多评级都很水啊，可能是翻译简化了题面的缘故）。 ~~我质因数分解写挂了~~，这题纯有病，我一开始疯狂 MLE#11 结果看题解才知道两个质因子也得特判。结果两个质因子的特判 exgcd 求特解还会爆 longlong，最后一个数据点还得特判 k==1,明明一个板子整这么多没用的卡人，下头题真无语。真无语！！！！！！！！！！！！ ~~我 tm 一个人交了将近一页。第一次做题做破防（~~ [有意思的题](https://www.luogu.com.cn/problem/CF715B) 最短路变式，我想的是先把每个点的最短路的区间求出来，下界和上界更新的时候都取 min，然后判断 L 在不在 s 的最短路区间，如果在，那就尝试在最小值的基础上往上加，还是类似 dij 的更新，不懂为啥数据量这么小时限这么大（然而我 ad 更新把自己搞晕了），[代码贴一下](https://www.luogu.com.cn/record/117927906)。 [P3654](https://www.luogu.com.cn/problem/P3645) 这题我做的非常失败，一开始我想的是对于每只狗子直接向他能跳到的所有点建边跑 dij，就是把每个点本身当成一种状态，这样点少边多，显然如果 $p$ 太小就会 T，于是我又乱搞双向 dij，结果过不了样例，才发现是单向边，看了题解没仔细想就想把题解 hack 了，结果我造的数据题解就跑了 0.04s。我还是太菜啊。 正解超级简单，把每个点每种狗设为一种状态，证明引自题解：设狗的跳跃能力为 $j$，对于所有的 $j>\sqrt n$，总状态数是 $m\sqrt n$ 个，对于所有 $j<\sqrt n$，总状态数是 $n \sqrt n$ 个,而每个状态最多会连两条边，这就做完了（去重用 bitset 很巧妙）。 [最短路计数](https://www.luogu.com.cn/problem/P1606) 和普通的最短路计数不一样，这个题有边权为 0 的边，更新路径条数的时候就会出现混乱，我睡了一觉然后想了一个办法，就是用 set 维护到达每个点的最短路最后一个需要代价的点有哪些，然后更新的时候就用这个更新来判断路径是否重复。注意这个时候每个点可能要重复更新，当然次数肯定不会太多，如果最短路相等每次我们标记一下是否更新了 set，如果更新了就再进一次堆。 核心代码： ```cpp else if(d+pl==dis[xx][yy]) { bool flag=0; for(set<int>::iterator j=s[p(x,y)].begin();j!=s[p(x,y)].end();j++) if(!s[p(xx,yy)].count(*j)) s[p(xx,yy)].insert(*j),f[p(xx,yy)]+=f[*j],flag=1; if(flag) q.push((P){d+pl,xx,yy}),vis[xx][yy]=0; } ``` ## Day5 图论杂项 [树的同构](https://www.luogu.com.cn/problem/P5043) 树哈希，没学过，梳理一下外星人的题解： 有根树的最小表示：每次进入一个子树，加一个左括号，回溯加一个右括号，对于多个儿子节点，按照字典序排序。可以证明一个有根树对应一个最小表示。时间复杂度最坏 $O(n^2)

无根树：暴力枚举根，然后取 min，复杂度三次方。对于这题，我们可以找到重心再转有根树，因为重心最多两个，所以复杂度二次方。

拓扑排序

例题可能不在洛谷上，口糊一下 ppt 上的题。

CodeForces 730E

给出 n 个队封榜时的分数 a[i] 和揭榜时的变化分数 d[i]。揭榜时，由于分数变化，这个队的名次会变化，设这个变化量为 t 然后问如何安排揭榜顺序，使得 sum(abs(t)) 最大

1\leq n\leq 100$，$1\leq a[i]\leq 100$, $-100\leq di\leq 100

原来拓扑也很有意思。 这种题我们只要想到让任意两个队之间产生一种先后关系就好了。

考虑任意两个队伍 i，j，我们设 a[i]>a[j] 如果在任何时刻 i 的值都比 j 高或者无论谁先变化排名变化次数都是一次（就是 i 减 j 加并且变化值都大于本来分数的差值或者只有两个人都变化完排名才会变），那么就没有先后顺序之分。在有先后之分的情况下再连边，只有两种情况需要考虑顺序，如果 i 和 j 同加，那么显然 j 先加更好，如果同减那么显然 i 先减更好。

这个条件不可能成环，所以拓扑即可。

BZOJ 3355

约翰的 N 头牛排成一行挤奶时，有确定的顺序。他拥有 L 条关于奶牛顺序的信息，所有的信息都写成“A在B的前面”这样的形式。请帮助约翰删除尽可能多的冗余信息，但要保证能推出原有的顺序。

n≤1500$，$l≤10000

我们考虑暴力添加每一条边，然后判断这条边是否冗余，显然加边应该按照一定的顺序，先把每个点拓扑排序，然后给边排序，按照重点的拓扑序从小到大，如果相等再按起点的拓扑序从大到小。为什么呢，首先我们考虑有哪些边会被删除。

这个图显然左边那个边可以被删掉，但如果我们先加入左边的边，那就无法将其删除。所以我们要拓扑排序，很明显下面那个点的拓扑序最靠后，所以我们就应该先加入终点拓扑序小的边，然后对于下面这两条边，显然我们应该让起点拓扑序最大的边加入，因为加入起点拓扑最大的边有可能会更新起点拓扑序更小的边，而反过来则不能，得证。

欧拉路（欧拉回路）

小学思维题学的内容。

欧拉回路 的简单判断：

有向图：所有点入度 = 出度

无向图：所有点度数为 2

欧拉路 的简单判断：

有向图：有两个点 出入度差 1

无向图：有两个点度数为奇

求欧拉回路的做法

逐步插入，对于一个点枚举每个邻点，然后删除这条边，把这个点加到栈里。由于每个点可能回遍历很多次，所以需要加入一个我在网络流学会的优化，当前弧优化！复杂度 O(n+m)。

void dfs(int u) {
    for(int &i=head[u];i;i=e[i].nx) {
        int cur=i;
        if(vis[abs(E[cur].id)]) continue;
        vis[abs(E[cur].id)]=1;
        dfs(E[cur].v);
        st.push(E[cur].id);
    }
}

丁香之路 欧拉路神题，又是看题解才会的（我纯 FW）。

显然对于一种走法，除了起点和终点，其他点 deg \bmod 2=0，这正好符合欧拉路的判定。假设我们现在的起点和终点分别是 s 和 t，那么如果对于必走的那些边来说，如果有一个点在 [s-t] 之间，那么显然让 s 连小的这个点，t 连大的这个点是最好的，如果这两个点都比 t 大，那么就让这两个点多连一次，然后让 t 和 s 分别连这两个点里面最小的点一次。

于是我们想到了正解，我们先把必走的 m 条边连上，然后给起点和终点的度设为 1，然后从小到大枚举点权，如果这个点的度为奇数，就让他和比它大的里面最小的那个度为奇数的点连边，这样我们就达成了欧拉路的条件。可图可能不连通，于是我们需要再跑一遍最小生成树，让答案加上树边权和的二倍。

我们发现对于刚才的第一种情况就是这种操作，而对于刚才的第二种情况，我们就可以看成是 s 向 t 多连了一条边，然后 t 向那两个点里最小的点连了两次，结果也是一样的。神题哇！

Day6 模拟赛

被薄纱的一天，四道题。T1 签到构造题，我用了半个小时写了 70 分的做法，没细想正解，想先把每个题都看看，开 T2，发现是最短路变式，开始设计 dij 的状态，一开始变量越设越多，卡了一会。我就去看 T3 和 T4，T3 不会，我总以为 T3 会和计算几何什么的有关，直接放弃了，T4 感觉和某些洛谷月赛题很像，也不太会。此时我认为 T2 更有把握，我换了一种方式，用四个变量维护了答案，写了一段时间，写的过程中想出了 T1 正解，但是没来得及写 T1，我把 T2 写完以后前三个样例一遍过，非常开心，然后样例 4 就 WA 了，突然发现已经剩不到半个小时了。我发现当最短路长度相等的时候，答案更新有点问题，开始魔改，剩5分钟，由于 4 个参数分类讨论很多，我最后都没添加完那个 if，加了一半，就放弃了。很可惜 T1 正解没补，后面两题完全白给。

最终 T2 还是过了点数据，我看题解就是设计四个参数维护，估计和正解差不太多，T1 也想对了（就是没写满分做法），但是 T3 听说是最短路？最短路我没写出来就太失败了。

成绩：

完全被吊打的尸骨无存，那个天津英华2是我，其他的英华人（当然国赛的除外）都在下面，这就是差距啊。

青春易逝，还是不要干没什么意义的事情吧。