自动搬运

查看原文

来自洛谷，原作者为

	RAY091016 &Silver_Losi|已不支持互关，请不要私信我或@我求互关|基本退犇了，有事TC，个人唯一标识Raylost#2949，小号Ray1016支持互关且在犇

搬运于2025-08-24 22:28:22，当前版本为作者最后更新于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;
}