题解：AT_abc200_d [ABC200D] Happy Birthday! 2

xianxi · 2024-12-26 13:27:44 · 题解

经历

学校拿来当考试题，第一眼看到这题，觉得是数学结论题，想了一会公式，结果脑子烧了，决定打个暴搜。

事实上，我似乎打出了正解：数学结论加暴搜，只是没有结合。

简单题意

给你 N 个数，要求选出两个序列，使两个序列和模 200 同余，输出任意满足解即可。

思路

暴搜用一次搜索同时处理两个序列容易超时，且不易编码，所以，用一个搜索只搜一个序列，每一次记录序列模值，遇见重复的模值即可输出。

怎么证明此暴搜不超时呢？

我们可以这样理解：搜到一种解，我们会将它模 200 的值记录到一个数组内。假设最坏情况下，前 200 次搜索得到的序列值都不同，那么，第 201 次搜索一定会有一个之前搜过的与当前序列不同的序列模 200 值相同，即抽屉原理或鸽巢原理。也就是搜索只用搜至少 201 次即可得出答案。

我用状态压缩处理搜索，学过状态压缩的，可知 2 的 8 次方等于 256 大于 201，足以搜索出有解情况，当然，如果 N 小于 8 就要用 N 去状压。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int maxn=2005;
int n,m,a[maxn];
vector<int>v[maxn];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    n=min(n,(long long) 8);
    for(int i=1;i<=(1<<n);++i)
    {
        int p[maxn],len=0;
        int j=i,cnt=1,ans=0;
        while(j)
        {
            if(j&1)
            {
                ans+=a[cnt];
                p[++len]=cnt;
            }
            cnt++;
            j>>=1;
        }
        if(v[ans%200].size()!=0)
        {
            cout<<"Yes"<<"\n";
            cout<<len<<" ";
            for(int i=1;i<=len;++i)cout<<p[i]<<" ";
            cout<<"\n";
            cout<<v[ans%200].size()<<" ";
            for(int i=0;i<v[ans%200].size();++i)cout<<v[ans%200][i]<<" ";
            return 0;
        }
        else
        {
            for(int i=1;i<=len;++i)
            {
                v[ans%200].push_back(p[i]);
            }
        }
    }
    cout<<"No";
    return 0;
}

最后，感谢您的留步与观看。