【推荐】全力冲刺2023年信息学CSP-J/S之：ARC164 - B 又爆零了

小码匠

发布于 2023-08-31 15:38:41

1970

发布于 2023-08-31 15:38:41

文章被收录于专栏：小码匠和老码农

碎碎念

这个问题爆零后我和老码农都没解决，代码看了N遍，还是一头雾水，后来在洛谷上向学长请教，才恍然大悟。谢谢学长的指点。

为什么要认真梳理这个话题

爆零是每一个oier几乎都曾经遇到的问题；
爆零是每一个oier在CSP-J/S赛场上最不希望被自己碰到的问题；
爆零是可能让一位优秀的oier遗憾终生的旅程。

期待本次梳理能让每一位看到文章的oier少犯低级错误，驰骋CSP-J/S赛场，打出自己应有的水平。

本系列文章强烈建议多读几遍，时刻提醒自己，让爆零哪凉快哪呆着去！！！

题目

题目原文请移步下面的链接

https://atcoder.jp/contests/arc164/tasks/arc164_b
- 参考题解：https://atcoder.jp/contests/arc164/editorial

题解

思路

这道题还是有些难度的，赛场我没AC，当时想到了需要用并差集判断。
这道题我分享了2位大佬的代码，都是我喜欢大佬，大佬的码风飒飒的。
这道题的重点是跟大家分享爆零的过程，思路不是重点。

小码匠代码

这份代码：AC：20、WA：26，当时最苦恼的是样例我本地通过了，然后老码农的另外一台电脑本地也通过了，但提交上去就是WA。当时瞪着代码看了半天，不知道原因。

大家注意best_coder方法这行代码。

    bool is;

完整代码

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

struct UF {
    vector<int> fa;

    UF(int n) :
            fa(n + 5) {}

    void initialize(int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i; //要记得先将每个节点的祖宗节点更新为本身
        }
    }

    int Find(int a) {
        if (a != fa[a]) { //如果a的父节点不是本身，就往前找到其祖宗节点
            fa[a] = Find(fa[a]); //往回返的时候把路上遍历过的所有节点更新为祖宗节点
        }
        return fa[a];
    }

    void Union(int x, int y) {
        int a = Find(x);
        int b = Find(y); //找到两个数的祖宗节点
        if (a != b) {
            fa[b] = a; //合并时只改其祖宗节点
        }
    }

    bool find_union(int x, int y) { //判断两个数在不在一个集合里
        int a = Find(x);
        int b = Find(y);
        if (a == b) {
            return true;
        } else {
            return false;
        }
    }
};

struct edge {
    int x, y, c;
} v[200005];

void best_coder() {
    int n, m;
    cin >> n >> m;
    UF uf(n);
    uf.initialize(n);
    for (int i = 1; i <= m; ++i) {
        cin >> v[i].x >> v[i].y;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].c;
    }
    for (int i = 1; i <= m; ++i) {
        int a = v[i].x;
        int b = v[i].y;
        if (v[a].c != v[b].c) {
            uf.Union(a, b);
        }
    }
    bool is;
    for (int i = 1; i <= m; ++i) {
        int a = v[i].x;
        int b = v[i].y;
        if (v[a].c == v[b].c && uf.find_union(a, b)) {
            is = true;
        }
    }
    if (is) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

小码匠AC代码

只修改了一行

    bool is;

修改成

    bool is = false;

原因：应该是和编译器有关，不同编译器变量的默认初始值不同，后来老码农用家里mac电脑一跑，结果就不对了。

今后注意点：一定要给变量赋初始值！一定要给变量赋初始值！！一定要给变量赋初始值！！！

AC代码

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

struct UF {
    vector<int> fa;

    UF(int n) :
            fa(n + 5) {}

    void initialize(int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i; //要记得先将每个节点的祖宗节点更新为本身
        }
    }

    int Find(int a) {
        if (a != fa[a]) { //如果a的父节点不是本身，就往前找到其祖宗节点
            fa[a] = Find(fa[a]); //往回返的时候把路上遍历过的所有节点更新为祖宗节点
        }
        return fa[a];
    }

    void Union(int x, int y) {
        int a = Find(x);
        int b = Find(y); //找到两个数的祖宗节点
        if (a != b) {
            fa[b] = a; //合并时只改其祖宗节点
        }
    }

    bool find_union(int x, int y) { //判断两个数在不在一个集合里
        int a = Find(x);
        int b = Find(y);
        if (a == b) {
            return true;
        } else {
            return false;
        }
    }
};

struct edge {
    int x, y, c;
} v[200005];

void best_coder() {
    int n, m;
    cin >> n >> m;
    UF uf(n);
    uf.initialize(n);
    for (int i = 1; i <= m; ++i) {
        cin >> v[i].x >> v[i].y;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].c;
    }
    for (int i = 1; i <= m; ++i) {
        int a = v[i].x;
        int b = v[i].y;
        if (v[a].c != v[b].c) {
            uf.Union(a, b);
        }
    }
    bool is = false;
    for (int i = 1; i <= m; ++i) {
        int a = v[i].x;
        int b = v[i].y;
        if (v[a].c == v[b].c && uf.find_union(a, b)) {
            is = true;
        }
    }
    if (is) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

代码学习

老码农通常都会要求我AC完题目后再看看题解或者大佬们的代码，可以扩展思路和学习其他人的编码方式。

代码学习1: peti1234

#include <bits/stdc++.h>
 
using namespace std;
const int c=200005;
int n, m, l[c], r[c], cl[c], ki[c], jo;
int holvan(int a) {
    return (ki[a] ? ki[a]=holvan(ki[a]) : a);
}
void unio(int a, int b) {
    a=holvan(a), b=holvan(b);
    if (a!=b) {
        ki[a]=b;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        cin >> l[i] >> r[i];
    }
    for (int i=1; i<=n; i++) {
        cin >> cl[i];
    }
    for (int i=1; i<=m; i++) {
        int a=l[i], b=r[i];
        if (cl[a]!=cl[b]) {
            unio(a, b);
        }
    }
    for (int i=1; i<=m; i++) {
        int a=l[i], b=r[i];
        if (cl[a]==cl[b] && holvan(a)==holvan(b)) {
            jo=1;
        }
    }
    cout << (jo ? "Yes" : "No") << "\n";
    return 0;
}

代码学习2: Um_nik

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
 
const int N = 300300;
int n, m;
vector<int> g[N];
int col[N];
int a[N];
 
void dfs(int v) {
	col[v] = m;
	for (int u : g[v]) if (col[u] == 0 && (a[v] ^ a[u]))
		dfs(u);
}
 
int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
 
	scanf("%d%d", &n, &m);
	while(m--) {
		int v, u;
		scanf("%d%d", &v, &u);
		v--;u--;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	m = 1;
	for (int v = 0; v < n; v++) if (col[v] == 0) {
		dfs(v);
		m++;
	}
	for (int v = 0; v < n; v++)
		for (int u : g[v]) if (col[v] == col[u] && (a[v] ^ a[u] ^ 1)) {
			eprintf("%d %d - %d %d - %d %d\n", v, u, col[v], col[u], a[v], a[u]);
			printf("Yes\n");
			return 0;
		}
	printf("No\n");
 
	return 0;
}