ABC200 D - Happy Birthday! 2 题解

D - Happy Birthday! 2

题意

  给定一个序列,找出是否存在两个不同的子序列,子序列的总和对\(200\)同余。

解题

  一个直接的想法就是将所有可能的情况都遍历一边,如果我们使用最暴力的方法,枚举每个元素所在组的情况,时间复杂度将会非常高,因此我们需要另外的解法。考虑到子序列求和后需要对\(200\)求余,也就是说我们得到的余数结果的范围在\([0,200)\)之间。题目要求出一对子序列,也就是说总和求余后是一样的。
  这里我们可以根据抽屉原理,知道如果我们计算过\(201\)个子序列后,就必定存在两个子序列的总和是同余的。抽屉原理也叫鸽洞原理,简单举个例子就是假设有\(200\)个鸽子洞,但是我们有\(201\)个鸽子需要回到洞里,那么就必定存在一个洞中有两只鸽子。
  在本题中,对总和求余的所有可能就是例子中的\(200\)个鸽子洞,当我们有超过\(200\)个子序列的时候,我们就可以得到超过\(200\)种可能的求余结果,因此就必定存在两个子序列的求余结果是相同的。同时,对于\(N\)个元素,我们可以得到的可能子序列个数为\(2^N-1\)个,当\(N\ge 8\)时,就一定会有结果,而当\(N\le 8\)时,需要判断是否存在结果。
  综上,我们只需要\(\min(n,8)\)个元素,再利用二进制枚举子序列,最后找到相同余数的子序列就得到结果,如果不存在就输出\(No\);

参考代码

点此展开
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

void print(vector<int> arr){
    cout<<arr.size();
    for(auto c:arr){
        cout<<" "<<c;
    }
    cout<<endl;
}

int main()
{
    int n;
    cin>>n;
    vector<int> a(n);

    for(int i=0; i<n; i++) cin>>a[i];

    int cnt=min(8,n);
    vector<int> rem[201];
    for(int i=1;i<1<<cnt;i++){
        int seg=0;//记录总和得到的余数
        vector<int> tmp;//记录子序列
        for(int j=0;j<cnt;j++){
            if(i&(1<<j)){
                tmp.push_back(j+1);
                seg+=a[j];
                seg%=200;
            }
        }

        if(rem[seg].size()!=0){//此前已经有过同样余数的子序列
            cout<<"Yes"<<endl;
            print(rem[seg]);
            print(tmp);
            return 0;
        }
        else
        {
            rem[seg]=tmp;
        }
    }
    cout<<"No"<<endl;

    return 0;
}
上一篇:使用Maven来创建WEB项目


下一篇:CF590E Birthday