二分答案思想下的二进制问题
序列合并
题目描述
给定一个长度为 n n n 的非负整数序列 { a n } \{a_n\} {an}，你可以进行 k k k 次操作，每次操作你选择两个相邻的数，把它们合并成它们的按位或。
形式化地，一次操作中，你选择一个下标 i i i（ 1 ≤ i < n 1 \le i < n 1≤i<n），然后把原序列变成 { a 1 , a 2 , ⋯ , a i or a i + 1 , a i + 2 , ⋯ , a n } \{a_1,a_2,\cdots,a_i \operatorname{or} a_{i+1},a_{i+2},\cdots,a_n\} {a1,a2,⋯,aiorai+1,ai+2,⋯,an}。
求 k k k 次操作后所有数按位与的最大值。
输入格式
第一行包含两个正整数 n , k n,k n,k。
第二行包含 n n n 个非负整数，其中第 i i i 个非负整数为 a i a_i ai。
输出格式
输出一行，包含一个正整数，代表答案。
【数据范围】
- 对于 25 % 25\% 25% 的数据， n ≤ 20 n \le 20 n≤20。
- 对于另外 25 % 25\% 25% 的数据， k = n − 2 k=n-2 k=n−2。
对于所有数据，保证 1 ≤ k < n ≤ 2 × 1 0 5 1 \le k<n \le 2 \times 10^5 1≤k<n≤2×105， 0 ≤ a i < 2 30 0 \le a_i < 2^{30} 0≤ai<230。
思路
对于这种给定一个序列，，定义其价值为序列最终其相与/或的值时，我们往往可以考虑去枚举最终的答案是否合法。
具体操作为，我们枚举答案二进制表示下的每一位，因为是尽可能的让答案更大，所以我们去枚举当前位为1时是否合法即可。
综上思路就和二分答案有些类似，所以这一类题的关键就在于如何 check 每次枚举的答案。
对于这一题，我们可以发现，对一个序列进行k次合并，等价于将其划分成 n − k n-k n−k 个子段，现在题目变为了对于每个子段 x i x_i xi ，其最终相与的值是否能为 x x x ,那么对于每个子段的 x i x_i xi 而言，x 二进制表示上为 1 的位置， x i x_i xi 对应的位置也得为 1,所以我们的思路为，使用一个变量 s s s 去记录当前子段内部相或的值，若 s & x = x s\&x = x s&x=x ,那么则清空 s s s，子段数加一，最后判断子段数是否大于 n − k n-k n−k 即可。
#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> ar;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{int n,k;cin>>n>>k;vector<int> a(n);for(auto &ai: a) cin>>ai;ll ans=0;auto check=[&](int x){int s=0;int cnt=0;for(int i=0;i<n;i++){s|=a[i];if((s&x)==x){s=0;cnt++;}}return cnt>=n-k;};for(int i=31;i>=0;i--){ll res=ans+(1<<i);if(check(res)){ans=res;}}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;// cin >> t;while (t--){solve();}system("pause");return 0;
}
牛客小白月赛94 E，F
思路：
这题和上面一题类似，也是求一些数相与的最大值，我们可以去枚举答案的每一位，去check当前这一位放 1 后是否合法即可。
这题的 check 比上一题还简单，即若当前的价值为当前枚举答案 x x x 的子集，我们变把他放入，最后看体积是否合法即可。
#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{int n,k;cin>>n>>k;vector<int> v(n+5),w(n+5);for(int i=1;i<=n;i++) cin>>v[i]>>w[i];ll ans=0;auto check=[&](int x){ll sum=(1ll<<32)-1;for(int i=1;i<=n;i++){if((w[i]&x)==x){sum&=v[i];}}return sum<=k;};for(int i=31;i>=0;i--){ll res=ans+(1<<i);if(check(res)){ans=res;}}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;// cin >> t;while (t--){solve();}system("pause");return 0;
}