题解：CF2179F Blackslex and Another RGB Walking

· · 题解

思路讲解

1. 关键引理：二分图把“同层边”彻底排掉

以点 1 为根，定义 dis_u 为 u 到点 1 的最短距离。

对任意一条边 (u,v)，在任意无权图里都有

|dis_u-dis_v|\le 1

理由很简单：从 u 走一步到 v，再走最短路回根，有 dis_u\le dis_v+1，同理 dis_v\le dis_u+1。

但是一般图里可能出现 dis_u=dis_v 的同层边，这会让“只靠颜色判断方向”变得不可能。

二分图的作用就在这里：二分图等价于“所有环长度为偶数”，也等价于“从固定根出发的最短路距离奇偶性给出一个合法二分划分”。因此对任意边 (u,v)，必有 dis_u 与 dis_v 奇偶性相反，也就是 dis_u\ne dis_v。

结合上一段的 |dis_u-dis_v|\le 1，我们得到最关键的结论：

|dis_u-dis_v|=1

这句话才是整题的地基：每条边一定连接相邻层，不会出现同层干扰。

2. 染色策略：到 1 最短距离模三

先手做一次宽度优先搜索求出所有 dis，并令颜色编号 c_u\equiv dis_u\pmod 3，再按编号映射到字符：

c_u=0\Rightarrow r,\quad c_u=1\Rightarrow g,\quad c_u=2\Rightarrow b

由上面的引理，u 的任意邻居 v 都满足 dis_v=dis_u\pm 1，所以邻居颜色编号只可能是

c_v\equiv c_u+1\pmod 3\quad 或者\quad c_v\equiv c_u-1\pmod 3

也就是说，站在 u 时，邻居颜色只会出现在“前一个颜色”和“后一个颜色”这两类里，不可能出现“同色邻居”，也不可能跳过一个颜色。

3. 后手的策略：先反推自己处在哪一层模三，再选让距离下降的那一色

如果后手在某一步看到邻居里同时出现两种颜色，那么缺失的那一种颜色就是自己当前点的颜色。因为邻居只可能是前驱色和后继色，两种都出现时，第三种必然对应 c_u。

于是有三种确定情况：

剩下是“邻居只有一种颜色”的情况。就随便选一个点即可，因为这些邻居的距离是一样的，你的距离也只可能从这些邻居上转移过来。

AC代码

AC

https://codeforces.com/contest/2179/submission/355080390

::::info[代码]

/**
 * Problem: F. Blackslex and Another RGB Walking
 * Contest: Codeforces Round 1071 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2179/problem/F
 * Created: 2025-12-25 15:05:02
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
void SolveFir() {
    ll N,M;
    cin>>N>>M;
    vector<vector<ll>> g(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    queue<pair<ll,ll>> q;
    q.push({1,0});
    vector<char> vis(N+2);
    vector<ll> vec_dis(N+2);
    vis[1]=true;
    while (!q.empty()) {
        auto [u,dis]=q.front();
        q.pop();
        for (auto v:g[u]) {
            if (vis[v]) continue;
            vis[v]=true;
            vec_dis[v]=dis+1;
            q.push({v,dis+1});
        }
    }
    for (int i=1;i<=N;++i) {
        ll op=vec_dis[i]%3;
        if (op==0) {
            cout<<"r";
        }else if (op==1) {
            cout<<"g";
        }else {
            cout<<"b";
        }
    }
    cout<<"\n";
}
void SolveSec() {
    ll Q;
    cin>>Q;
    for (int _=1;_<=Q;++_) {
        ll n;
        cin>>n;
        string s;
        cin>>s;
        int r_have=0,g_have=0,b_have=0;
        ll r_pos=0,g_pos=0,b_pos=0;
        for (int i=0;i<s.size();++i) {
            if (s[i]=='r') {
                r_have=1;
                r_pos=i+1;
            }else if (s[i]=='g'){
                g_have=1;
                g_pos=i+1;
            }else {
                b_have=1;
                b_pos=i+1;
            }
        }
        if (r_have+g_have+b_have==1) {
            cout<<1<<"\n";
            continue;
        }
        if (r_have+b_have==2) {
            cout<<r_pos<<"\n";
            continue;
        }
        if (r_have+g_have==2) {
            cout<<g_pos<<"\n";
            continue;
        }
        if (g_have+b_have==2) {
            cout<<b_pos<<"\n";
            continue;
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string s;
    cin>>s;
    cin >> lT;
    if (s=="first") {
        while(lT--)
            SolveFir();
    }else {
        while(lT--)
            SolveSec();
    }

    return 0;
}

/*

AC

https://codeforces.com/contest/2179/submission/355080390

first
1
4 4
1 2
1 3
4 2
4 3

*/

::::