2025-08-11 模拟考试 in Xinyoudui

大傻逼信友队直接照搬atcoder原题赶紧去死吧，T3T4这么难

タイムライン

8:00—8:15 看题

8:15—8:30 写T1

8:30—9:00 写T2

9:00—结束 看T3T4，想题

得分

错误原因

• T2

  思路想错，错误地使用邻接矩阵，

• T3&T4

  思路错误，想了好久没想出来

题解这一块

T1 打绳结

洛谷：AT_abc293_d [ABC293D] Tying Rope

可以直接把绳子看成点，形成环，环的数量+1，不成环的数量直接用n，反正后面用不到了，成一个环n就减1

使用并查集

Code

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;  // 最大绳子数量+余量
int n,m;             // n=绳子数量，m=操作次数
int father[N];       // 并查集父节点数组，用于维护连通集合
int ans=0;           // 用来统计环的数量（代码中试图实现）
int a,c;             // 输入的两个绳子编号
char b,d;            // 输入的两端颜色，'R' 或 'B'

// 并查集查找函数，带路径压缩
int findfather(int x){
    if(x == father[x]){
        return x;
    }
    return father[x] = findfather(father[x]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;  // 读入绳子数和操作次数

    // 并查集初始化：每个节点自己是一个集合
    for(int i = 1; i <= n; i++){
        father[i] = i;
    }

    // 对每条连接操作进行处理
    for(int i = 1; i <= m; i++){
        cin >> a >> b >> c >> d;  
        // 读取输入：
        // a, b 表示绳子 a 的端点颜色 b ('R'或'B')
        // c, d 表示绳子 c 的端点颜色 d ('R'或'B')

        // 找出绳子 a 和绳子 c 对应的集合根节点
        int fa1 = findfather(a);
        int fa2 = findfather(c);

        // 非联通数量-1
        n--;

        // 如果两端不在同一个集合，合并集合
        if(fa1 != fa2){
            father[fa1] = fa2;
        }
        else {
            // 如果已经在同一个集合中，说明这条边形成了环，环数量加一
            ans++;
        }
    }

    cout << ans << " " << n;

    return 0;
}

T2 摇曳

考时想复杂了，其实就是dfs去遍历图

遇到障碍时，找它的儿子，如果有两个儿子，直接把障碍清空，因为怎么挪都不影响最终结果，不如直接删掉

如果只有一个，只能把障碍挪给那个儿子然后继续走

如果没有儿子，则走不通，回溯

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,ans,obs[N];
vector<int> a[N];
void dfs(int u,int fa){
    if(obs[u]){
        vector<int> em;
        for(int i=0;i<(int)a[u].size();i++){
            int v=a[u][i];
            if(v!=fa && !obs[v]){
                em.push_back(v);
            }
        }
        if(em.empty()){
            return;
        }
        if(em.size()==1){
            obs[em[0]]=1;
        }
        obs[u]=0;
    }
    for(int i=0;i<(int)a[u].size();i++){
        int v=a[u][i];
        if(v!=fa){
            dfs(v,u);
        }
    }
}
void solve(int u,int fa){
    if(obs[u]==1) return;
    ans++;
    for(int i=0;i<(int)a[u].size();i++){
        int v=a[u][i];
        if(v!=fa){
            count(v,u);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("swaying.in","r",stdin);
    freopen("swaying.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        obs[x]=1;
    }
    dfs(1,-1);
    solve(1,-1);
    cout<<ans;
    return 0;
}