题解：P9384 [THUPC 2023 决赛] 着色

Deepsick · 2026-03-05 14:24:34 · 题解

Part 1

先考虑怎么给尽量多的边标 0，使得没有三元或五元环的每条边都是 0。

一种构造是：把两个端点编号之差为奇数的边都设为 0。可以发现这些边构成的环的长度一定是偶数，所以满足条件。

Part 2

现在考虑剩下哪些边没处理。发现这些边可以构成两个完全图，其中一个的节点编号都是奇数，另一个都是偶数。

既然还是完全图，我们就可以继续使用刚才的方法，把两个端点编号之差等于两倍奇数的边都标上 1。同理，继续把端点编号之差为四倍奇数的边标上 2，八倍奇数的边标上 3……

从而我们就得到了如下构造：把每条长度为 x 的边标上 a_x，其中

因为 a_x \le \lfloor \log_2x \rfloor，且 x<n \le 1000，所以 a_x \le 9，满足题目条件。 ::::success[AC 代码]

#include <iostream>
using namespace std;
int a[1001];
int main() {
    int n,i,j;
    cin>>n;
    for(i=1;i<=n;i++) a[i]=i%2?0:a[i/2]+1;
    for(i=1;i<n;i++) {
        for(j=1;j<=n-i;j++) cout<<a[j];
        cout<<'\n';
    }
    return 0;
}

:::: AC 记录。