构造题，首先考虑爆搜，但结果跑不出来。
既然题目中描述相同元素不能构成三元环或五元环，其实可以把条件用的更局限，考虑相同元素只能构成偶环，即同一权值的边构成二分图，可以发现本题刚好
种颜色，刚好 。
接下来考虑怎么构造二分图，本题大部分思路都是令 ，并将
作为染色的依据，但没有提到怎么去想出这样的思路。
首先，令一个集合 ，其中的元素互不相同,且都不为零。
令另一个集合 ，其中 且 满足 ，特别地 。
说人话就是集合 是由集合 中两个相邻的元素异或得到的。
对于以上两个集合有一个性质：即当 为偶数时，对于形式类似于
的情况刚好能不重不漏的覆盖整个
集合，具体请读者自证。
那以上结论有什么用呢？可以发现在一个二分图里面，点数刚好是偶数，而每个点的序都不同，刚好满足上述条件，故可以按照思路中的
作为染色的依据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include<cstdio>
using namespace std;
const int N=1e3+100;
int n;
int t[N];
int lowbit(int x){
return x&(-x);
}
int main(){
scanf("%d",&n);
for(int i=0;i<=10;i++){
t[1<<i]=i;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
printf("%d",t[lowbit(i^j)]);
}
printf("\n");
}
return 0;
}
|
