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