abc200-d

本题主要体验了unordered_map和位运算的快乐，stl还是太棒了

• 首先我们来看看什么是unordered_map👀

去看这个博客unordered_map

在本题中，由于N的最大值为200，而我们要找到对200取模后值相等的两个不同子序列。根据容斥原理，假如我们能找到201个互不相同子序列，那他们其中一定有两个子序列的和对200取模后的值相等，我们可以注意到（怎么注意到的啊喂！）当N=8的时候，就有256个这样的子序列了，那就可以断定一定存在这样的子序列，这时候我们就可以开始暴力了，非常的舒服，那么自然，当n>8时也一定是成立的，当n<8时也照常暴力即可。

时间复杂度达到了惊人的O(min(2^k,200)),k=min(n,8)也就是说最大时间复杂度也只有200，omg

上代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
unordered_map<int,vector<int>>md;
/*
    这里是unordered_map的一个定义，它分为键和值两个部分，键也就是key，哈希表区分元素的那个依据，这里是int类型，值是vector类型的一个向量，用来存这个序列的所有位置
    这里也能看出vector的好处，两个vector之间只需要用等号连接就能把一个里的数全放在另一个里面，爽啊
    stl真是太好用了，原始人，进化！
*/
int w[N];
void print(vector<int>d)
{
    cout<<d.size()<<' ';
    for(auto x:d)cout<<x<<' ';
    /*
        此处是vector的一个用法，d.size()能读取向量d里元素的数量，
        auto x:d代表了从d的第0位遍历到d.size()-1位，写起来很快啊
    */
    cout<<'\n';
}
int main()
{
    int n;
    cin>>n;
    int mins=min(n,8);
    for(int i=0;i<n;i++)cin>>w[i];
    for(int i=1;i<(1<<mins);i++){
        /*
            这里这个1<<mins代表将1左移mins位，等价于pow(2,mins)，但是在速度上要比pow快得多，这里mins最大值为8，不会爆int
        */
        int sum=0;
        vector<int>tmp;
        for(int j=0;j<mins;j++)
            if(i>>j&1)
                /*
                    这里的i>>j代表了将i右移j位，这里的i代表的数化作二进制数，就是前mins位的出勤情况，假如j=0，那么i就不右移，&1之后假如i的最低位是1返回值就是1，否则为0（因为1可看作高位全为0，即为0000001），如果是1，则这个位置上的数在这次计算中出勤了，加和要加上，并且把这个位置放在tmp里（因为j是从0开始，而序列下标是从1开始算的）
                */
                sum=(sum+w[j])%200,tmp.push_back(j+1);
        if(md[sum].size()){//如果这个键对应的向量里不是空的，说明之前已经有等于同一个值的数了，直接输出
            cout<<"YES\n";
            print(tmp);
            print(md[sum]);
            return 0;
        }else
            md[sum]=tmp;//太酷啦，一行就搞定了
    }
    cout<<"No\n";
    return 0;
}