【cf】#681 A. Kids Seating (Div. 2, based on VK Cup 2019-2020 - Final)

A. Kids Seating

• 有1到4n个数，要求找出n个数，使得任意两个数之间不互质且没有整除关系。

解题思路

• 一道构造题。
• n的规模是100，就暴力做了。
• 可以发现第一个数至少得从4开始。然后遍历4*n个数，对于每一个数，查找他是否和前面的数互质，并且和前面的数是否有整除关系。对于整除关系，可以每次发现有整除关系时都筛一下，这样能提高效率。
• 遍历4*n个数之后，判断找到的数是否满足n个数，如果不够n，那么从5开始作为第一个数……以此类推。
• 关键字： 暴力构造

•   这里给出几个定义：
    * pos[]：初始化为1，0表示不符合要求
    * ans[]：记录符合要求的数字
    * cnt：表示当前有多少个符合要求的数字
    * j：第一个数字
    * check(a)：将a的倍数的pos[]都标记为0，因为有整除关系，所以不符合要求，标记为0。
    * check2(a, cnt)：判断a是否和前面符合要求的cnt个数有互质关系，若互质，返回1，否则返回0。
  

注意

• 若发现当前找不到n个数字，要j++从头开始找时，记得重新初始化pos[]和ans[]。

技巧

• __gcd(a,b)：返回a,b的最大公约数。
  判断a,b两个数是否互质：即判断 __gcd(a,b) == 1

我的代码

#include<bits/stdc++.h>
using namespace std;
int n, cnt;
int a[4005], pos[4005], ans[1005];
void check(int a){
    
	for(int i = a; i <= 4*n; i+=a){
    
		pos[i] = 0;
	}
}

int check2(int a, int cnt){
    
	for(int i = 0; i <= cnt; i++)
		if(__gcd(a, ans[i]) == 1)	
			return 1;
	return 0;
} 
int main(){
    
	int t;
	cin >> t;
	while(t--){
    
		cin >> n;
		cnt = 0;
		int j = 4;
		while(j < 4*n){
    	
			memset(ans, 0, sizeof(ans));
			memset(pos, 1, sizeof(pos));
			ans[cnt] = j;
			check(j);
			for(int i = j+1; i <= 4*n; i++){
    
				if(check2(i, cnt)){
    
					continue;
				}
				if(i % ans[cnt] == 0){
    
					check(i); continue;
				}
				if(pos[i] == 0)	continue;
				ans[++cnt] = i;
				check(i);
				if(cnt == n-1)	break;
			}
			if(cnt < n-1){
    
				j++;
				memset(ans, 0, sizeof(ans));
				cnt = 0;
				continue;
			}
			else break;
		}
		if(n == 1){
    
			cout << 1 << endl;
		}
		else{
    
			for(int i = 0; i <= cnt; i++)
				cout << ans[i] << " ";
			cout << endl;
		}
	}
	
	
} 

优化

• 关键字：思维、构造

• 代码