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

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

[Problem - B - Codeforces][]

题意：

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

思路：

设两个子序列是a和b

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

满足的条件是：

1.  a!=b

1.  f(a)=f(b)

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

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

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

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

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

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

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

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

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

![3572727aa695e2eaddf7fa255d0809ea.png][]

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;
    }

**总结：**

1.  **一些证明怎么去证明：**

**如果我们要去证明结论的正确性，就去考虑一般的情况，然后看这个一般的情况能不能转化到我们所考虑的特殊情况**

**一般性证明：直接设未知数，然后考虑直接证**

**反证法**

**归纳法**

**2.构造，先考虑需要满足的条件，然后去考虑特解情况**

[Problem - B - Codeforces]: https://codeforces.com/contest/1775/problem/B
[3572727aa695e2eaddf7fa255d0809ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e89cff0a325f461db04c5e5d0b592f51.png