【构造】Codeforces Round #843 (Div. 2) B Gardener and the Array-蒲公英云

【构造】Codeforces Round #843 (Div. 2) B Gardener and the Array

女爷i 2024-03-30 17:28 171阅读 0赞

Problem - B - Codeforces

题意：

给定一个序列，让你判断是否存在两个子序列使得这两个子序列或起来相等

思路：

设两个子序列是a和b

两个子序列凭空出现，那肯定考虑构造

满足的条件是：

a!=b
f(a)=f(b)

如果只考虑第二个条件，那么特解是a=b

但是考虑到a不能等于b，因此考虑把一些数删掉，使得删掉数后f(a)依然等于f(b)

删掉的这些数满足什么条件呢？满足这个数是可有可无的数

可有可无的数就是删掉之后f(a)依然等于f(b)，即二进制位为1的位的1的个数在删之前>=2

因此a就是所有数或起来，b就是a集合去掉可有可无的数

所以结论就是，如果一个数列，它没有可有可无的数，那就不行，否则就可以

以上讨论的是取a为所有数或起来的情况，那么怎么考虑一般情况

事实上是可以证明，所有的一般情况都可以转化为上面讨论的那种情况

这里贴一下pzr大佬的证明：

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=2e5+10;
map<int,int> cnt;
vector<int> v[mxn];
int n,k,x;
void solve(){
    cnt.clear();
    cin>>n;
    for(int i=1;i<=n;i++) v[i].clear();
    for(int i=1;i<=n;i++){
        cin>>k;
        for(int j=1;j<=k;j++){
            cin>>x;
            v[i].push_back(x);
            cnt[x]++;
        }
    }
    for(int i=1;i<=n;i++){
        int ok=1;
        for(auto it:v[i]){
            if(cnt[it]<2) ok=0;
        }
        if(ok){
            cout<<"Yes"<<'\n';
            return;
        }
    }
    cout<<"No"<<'\n';
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;cin>>__;
    while(__--)solve();return 0;
}