题解：AT_abc200_d [ABC200D] Happy Birthday! 2

算法：抽屉原理，状态压缩

解题思路：

抽屉原理先加证明：显而易见，在 201 个序列中必定有两个对 200 取模的余数相同。

因为

2^8=256>200

，所以我们只需要状态压缩枚举前 8 个数列的情况总数，找到即输出。

当

n \ge 9

时，上述情况同

n \le 8

，一定有解。

用 vector 存储状态压缩的情况，满足直接输出即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[2001];
vector<int>f[2001];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]%=200;
	}
	if(n>8) n=8;
	for(int i=0;i<(1<<n);i++){
		vector<int>v;
		int s=0;
		for(int j=0;j<n;j++){
			if((i>>j)&1){
				s=(s+a[j])%200;
				v.push_back(j+1);
			}
		}
		if(f[s].size()){
			puts("Yes");
			cout<<f[s].size()<<" ";
			for(auto x:f[s]) cout<<x<<" ";
			puts("");
			cout<<v.size()<<" ";
			for(auto x:v) cout<<x<<" ";
			exit(0);
		}
		f[s]=v;
	}
	puts("No");
	
	return 0;
}

题解：AT_abc200_d [ABC200D] Happy Birthday! 2

文章操作

算法：抽屉原理，状态压缩

解题思路：

代码

相关推荐

评论

题解：AT_abc200_d [ABC200D] Happy Birthday! 2