CSP2023 游记

CSP2023 游记

本来是写游记，现在发现好像成了复习博客。

Day -3

上午打了一场模拟赛，又垫底了。

好像是信心赛，但是只会前两道（恼了！）。

发现 accoders 在 CSP 前两天还有模拟赛，悲。

复习 Tarjan

注意：Tarjan 题目常见图不连通情况。

• low[u] 表示以 \(u\) 为根的子树中结点以及这些结点通过一条非树边能到达的结点的最小 dfn。

有向图：

1. 强连通分量：low[x] == dfn[x]

有向图中两个顶点可以互相到达，称为他们强连通；强连通分量是有向图的极大强连通子图。

一张图中所有强连通分量缩点后得到一个 DAG；设出度为 \(0\) 的点数为 \(x\)，入度为 \(0\) 的点数为 \(y\)，那么将一张 DAG 修改为一个强连通分量至少要加 \(\max \left\{x,y \right\}\) 条边。

void dfs(int x) {
	tot ++;
	dfn[x] = low[x] = tot;

	st.push(x);
	vis[x] = 1;

	for(int i = h[x];i;i = e[i].next) {
		int to = e[i].to;

		if(!dfn[to]) {
			dfs(to);
			low[x] = min(low[x],low[to]);
		}
		else if(vis[to])
			low[x] = min(low[x],dfn[to]);
	}

	if(low[x] == dfn[x]) {
		int res = 0;

		while(true) {
			res ++;
			int t = st.top();
			vis[t] = 0;
			st.pop();

			if(t == x)
				break;
		}

		if(res != 1)
			ans = min(ans,res);
	}
}

强连通分量一般用于缩点，例如受欢迎的牛。

无向图：

2. 割点：dfn[x] <= low[to]

由于 low[u] 可以理解为 \(u\) 子树中的点通过一条非树边能回溯到的最小 dfs 序，那么如果某个结点 to 不能回溯到 x 或其之前结点，点 \(x\) 为割点。

void dfs(int x,int fa) {
    // fa 表示父节点，用于判断根节点的 
    tot ++;
    dfn[x] = low[x] = tot;
    
    int child = 0;
    // 存该节点的子树个数，用来判断根节点是否为割点

    for(int i = h[x];i;i = e[i].next) {
        int to = e[i].to;
        if(!dfn[to]) {
            dfs(to,fa);
         
            low[x] = min(low[x],low[to]);
            
            if(low[to] >= dfn[x] && x != fa)
                cut[x] = 1;// 标记为割点
                // 这里特判了不是根节点 
            
            if(x == fa)
                child++;// 记录子树
        }

        low[x] = min(low[x],dfn[to]);
    }

    if(x == fa && child >= 2)
        cut[x] = 1;
        // 是根节点并且有两个或以上的子树
        // 一定是割点 
}

3. 割边：dfn[x] < low[to]

注意区分割边与割点的判断条件，当 dfn[x] == low[to] 时，\(x\) 是割点，但 \((x,to)\) 不是割边。

求割边不需要考虑根的情况。

Day -2

上午打了一场模拟赛，又垫底了。

横叉边有个性质：存在横叉边 \((u,v)\) 当且仅当 \(v\) 可到达 \(\operatorname{lca}(u,v)\)。

圆方树

广义原方树把点双看作方点，点看作圆点。

实际上是将点双内的边缩成一个方点，再从该方点向点双内其他点连边。

这样得到一棵树。

圆方树可以描述两点之间路径必经结点，原图任意两点之间所有割点等。

每个点双实际上缩成了以方点为中心点的菊花图，各个点双之间以割点相连。

一些性质：

• 圆点 \(x\) 的度数等于包含它的点双个数。
• 原图上直接相连的 \(u,v\) 包含于同一点双。
• 圆点 \(x\) 是叶子当且仅当它在原图不是割点。
• \(x,y\) 简单路径上的所有圆点恰好是原图 \(x,y\) 之间的所有必经点。

这些性质实质上表达的就是，圆方树完整地保留了原图的必经性。

晚上刷了一堆板子，打算明天模拟赛继续刷板子。

Day -1

上午打了一场模拟赛，又垫底了。

第一题签到题，签了个道就走人了。

考虑写点双、边双模板。

1. 点双联通分量：不存在割点的极大子图

孤立的一个点也是点双。

当 \(x\) 为割点时弹栈，栈顶到 \(to\) 都属于这个点双，割点也属于这个点双。

割点可能在多个点双内，不能弹栈；\(to\) 的子树内所有点双都处理了就可以弹。

void dfs(int x,int root) {
    tot ++;
    dfn[x] = low[x] = tot;
    st[++top] = x;

    if(x == root && h[x] == 0) {
        num ++;
        ans[num].push_back(x);

        return ;
    }
    
    for(int i = h[x];i;i = e[i].next) {
        int to = e[i].to;

        if(!dfn[to]) {
            dfs(to,root);

            low[x] = min(low[x],low[to]);

            if(low[to] >= dfn[x]) {
                num ++;
                int k;

                do {
                    k = st[top];
                    top --;
                    ans[num].push_back(k);
                }while(k != to);

                ans[num].push_back(x);
            }

        }
        else
            low[x] = min(low[x],dfn[to]);
    }
}

2. 边双联通分量：不存在割边的极大子图

考虑寻找割边，删去割边后剩下的若干个连通块实质上就是所有边双。

注意考虑重边的问题，两个点之间有重边也算边双。所以就不能像之前一样判点了，要判断边是否走过。

// cnt 初始赋为 1，fa 传 0
void dfs1(int x,int fa) {
    tot ++;
    dfn[x] = low[x] = tot;
    st[++top] = x;
    
    for(int i = h[x];i;i = e[i].next) {
        int to = e[i].to;

        if(!dfn[to]) {
            dfs1(to,i);

            low[x] = min(low[x],low[to]);

            if(low[to] > dfn[x]) 
                cut[make_pair(x,to)] = cut[make_pair(to,x)] = 1;
        }
        else if(i != (fa ^ 1))
            low[x] = min(low[x],dfn[to]);
    }
}

void dfs2(int x) {
    vis[x] = 1;
    ans[num].push_back(x);
 
    for(int i = h[x];i;i = e[i].next) {
        int to = e[i].to;

        if(vis[to] || cut[make_pair(x,to)])
            continue;
        
        dfs2(to);
    }
}

打了一遍树剖，写成 tag 为 \(0\) 才 Pushdown 了，恼。

下午接着打点分治。

Day 0

不跑操 + 提前发手机，直接双喜临门。

看大纲发现平衡树是提高组内容，临时复习 FHQ-Treap。