CF1554C 和牛客练习赛101C（问题转化，按位贪心）

写了两道和位运算不等式有关的贪心题，发现思路非常一样就放一起了。

牛客练习赛C

题意

给一个严格递增的序列 /(a/)。

求一个最小的 /(x/) 使得对所有的序列元素做一遍按位与后仍然严格递增。

思路

考虑贪心，为了使答案尽可能小，从高位往低位贪心，贪心过程中先取 /(i/) 位为0，然后贪心check之后的二进制位 /(j/) 是否存在一个解使得约束成立。

check的过程中就判断，如果保留第 /(j/) 位的 /(1/) 是否不会使得答案变差，也就是能否使得序列 非严格递增 。用“非严格”而非 “严格” 是因为前者不会使答案变差并仍然可以区分一定的有序性（如把一段序列有序的过程可以想象为把[ X,X,X,X ]变成[[X],[X],[X],[X]]的分段过程，非严格递增虽然不能达到目的，但可以达成[[X,X],[X,X]] 的区分，它仍然让结果更优了），那就贪心的把它保留下来。

最后判断贪心结果是否满足题意，如果可以，说明 /(i/) 位可以为 /(0/)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<iomanip>
#include<bitset>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '/n'
#define int long long
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int n; cin >> n;
    vector<int> a(n + 1);
    rep(i,1,n) cin >> a[i];
    int ans = 0;
    per(i,30,0) {
        int cur = ans;
        per(j,i - 1,0) {
            cur |= 1 << j;
            bool flg = 0;
            rep(k,1,n - 1) if((a[k] & cur) > (a[k + 1] & cur)) {
                flg = 1;
                break;
            }
            if(flg) cur ^= 1 << j;
        }
        bool ok = 1;
        rep(j,1,n - 1) if((a[j] & cur) >= (a[j + 1] & cur)) {
            ok = 0;
            break;
        }
        if(!ok) ans |= 1 << i;
    }
    cout << ans;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    //int T;cin>>T;
    //while(T--)
        solve();

    return 0;
}

CF1554C

题意

给定 /(n/) ，/(m/) 求 /(MEX(n /oplus 0,n /oplus 1,n /oplus 2,…,n /oplus m)/)

思路

一开始没什么思路，打了个表发现当 /(n < m/) 时规律很难找。瞄了眼题解发现有一个非常有意思的转化。

设 /(x/in [0,m]/) ，/(n /oplus x = k/) 。 那么 /(k/) 就是出现过的数字。给式子移项 $n /oplus k = x $ 考虑 /(MEX/) 的定义，我们要求的其实就是最小的满足 /(n /oplus k’ = y > m/) 的 /(k’/) ，这里的 /(k’/) 就是没出现的数字。

这样就是转化为找 /(n /oplus k /ge m+1/) 的最小解。这里就可以从高到低按位贪心贪心，思路和上面牛客的题基本是一样的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<iomanip>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '/n'
#define int long long
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int n,m; cin >> n >> m;
    // n ^ k >= m + 1
    int ans = 0;
    per(i,30,0) {
        int cur = ans;
        per(j,i - 1,0) {
            if(n >> j & 1){}
            else cur |= (1 << j);
        }
        if((n ^ cur) < m + 1) ans |= (1 << i);
    }
    cout << ans << "/n";
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}