P7282 Hop 题解

ARIS0_0 · 2025-07-24 09:20:21 · 题解

1. 题目解释

给定 n 个点，在这 n 个点内两两连边并给边染色，要求不能有连续的四条边颜色相同，求一个合法方案。

2. 思路

首先我们知道两个点中间若有连边，则必有倍数关系，不妨设 x_i\mid x_j，则有 x_j=k\times x_i 且 k 为大于大于 2 的整数。

考虑一条链，其中点 i 与点 i+1 相连且点权 w_{i+1} 为 w_i 的两倍。

由于点权最大为 1\times10^{18}，故这条链最长有 \log_21\times10^{18}\approx60 个点。

我们将这 60 个点每 4 个点分为一小组，每 4 个小组分为一个大组，最后共有 4 个大组。

我们再将同一小组内点的边全部染为红色，将同一大组但不同小组内点的边全部染为蓝色，不在一个大组内点的边全部染为绿色。

不难发现这种方式使得不存在连续四条边颜色相同。

我们强制令每一个 a_i 的标号为其二进制下最高位的位数。

然后就做完了。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1010],v[1010];
int get(int x){
    int ret=1,tot=1;
    while(1){
        if(tot*2>x){
            return ret;
        }
        tot*=2;
        ret++;
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v[i]=get(a[i]);
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i]%a[j]==0){
                if(v[i]/4==v[j]/4){
                    cout<<1<<" ";
                }
                else if(v[i]/16==v[j]/16){
                    cout<<2<<" ";
                }
                else{
                    cout<<3<<" ";
                }
            }
            else{
                cout<<1<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}