题解：P7428 [THUPC 2017] 母亲节的礼物

Deepsick · 2026-08-08 06:47:23 · 题解

::::info[闲话] 怎么有一车人会做法不会证正确性的，反正我至今不知道这个做法能够如何被人类想到。 ::::

策略

先把所有点都染成颜色 a，然后反复执行以下操作直到不能执行为止：

• 选择一个点 u，使得其颜色与它周围的至少两个点颜色相同（称这样的点为特殊点）。由于 u 的度数不超过 7，所以一定存在一个颜色在它周围的点中出现不超过一次。我们将 u 改为这一颜色。

即可得到结果。

正确性

显然当操作无法执行下去时答案一定符合条件。而每次操作都会减少两端点颜色相同的边数，且该值不可能无限减小，所以必然存在某个时刻使得操作无法执行。

这也说明了总操作次数不会超过 m。

实现

每次操作枚举所有点显然是超时的。

考虑维护每个点周围每个颜色出现的次数，同时建立一个队列，每发现一个特殊点就将其入队，出队时判断它是否仍然为特殊点，若是则进行操作，否则忽略它。

这样总复杂度与入队次数成正比，而后者不会超过初始特殊点数量加操作次数，即不超过 n+m。

所以该算法的时间复杂度为 O(T(n+m))，空间复杂度为 O(n+m)。带七倍常数，因为每次操作都要更新特殊点周围每个点的信息。 ::::success[AC 代码]

#include <iostream>
#include <vector>
using namespace std;
vector<int> a[25001];
int b[25001],cnt[25001][4],q[1000001];
int main() {
    int T,n,m,i,j,l,r;
    cin>>T;
    while(T--) {
        cin>>n>>m;
        for(i=1;i<=n;i++) {
            a[i].clear();b[i]=0;
            for(j=0;j<4;j++) cnt[i][j]=0;
        }
        while(m--) {
            cin>>i>>j;
            a[i].push_back(j);a[j].push_back(i);
            cnt[i][0]++;cnt[j][0]++;
        }
        l=r=0;
        for(i=1;i<=n;i++) if(cnt[i][0]>1) q[r++]=i;
        while(l<r) {
            i=q[l++];
            if(cnt[i][b[i]]<=1) continue;
            for(j=0;j<a[i].size();j++) cnt[a[i][j]][b[i]]--;
            for(j=0;j<4;j++) if(cnt[i][j]<=1) break;
            b[i]=j;
            for(j=0;j<a[i].size();j++) if(++cnt[a[i][j]][b[i]]==2&&b[i]==b[a[i][j]]) q[r++]=a[i][j];
        }
        for(i=1;i<=n;i++) cout<<(char)(b[i]+'a');
        cout<<'\n';
    }
    return 0;
}

:::: AC 记录。为什么跑这么慢我也不知道。