https://codeforces.com/contest/1973/problem/B
题目大意:
给定长度位n的数组a,找出符合以下条件的最小k:
任意连续的k个元素,他们按位或的结果相同
输入:
t 组数据,每组数据第一行 n (1 ≤ n ≤ 1e5)和 第二行数组a(0 ≤ai <2`20)
输出:
最小的 k
思路:
-
假设一个小于 n 的 k 满足条件,则 (k + 1) 也满足条件
证明:
假设当前 k = 3, 则 a[1] | a[2] | a[3] = a[2] | a[3] | a[4] = ...
=> (a[1] | a[2] | a[3]) | (a[2] | a[3] | a[4]) = (a[2] | a[3] | a[4]) | (a[3] | a[4] | a[5]) = ...
以此类推, (a[1] | ... | a[k]) | (a[2] | ... | a[k + 1]) = (a[2] | ... | a[k + 1]) | (a[3] | ... | a[k + 2]) = ...
注意到,已经 or 过的数再 or 多少遍都不会改变结果,故上式可以化简为:
a[1] | .. a[k + 1] = a[2] | ... | a[k + 2] = ...接下来,可以在 [1, n] 上二分确定最小的k
-
怎么判断每个k是否符合条件?
前 k 位按位或的结果设为 expectedNum ,后面每段连续的 k 个数字按位或的结果与 expectedNum 进行比较,看是否相同
check函数代码实现:
将每个 a[i] 转换成二进制,用s_a表示,每 k 个数字按位或的结果为s_res,则每一位s_res[i]取决于这 k 个 s_a[i] 中有没有'1',如果有,则s_res[1] = '1',否则 s_res[1] = '0'
=>一堆数字按位或,如果有一个 1 则结果为 1,否则为 0
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n;
/* 十进制转二进制 */
string DtoB(int x){
if(x == 0){
return "0";
}
string s = "";
while(x > 0){
s += x % 2 + '0';
x /= 2;
}
int len = s.length();
for(int i = 0; i < len - 1 - i; i++){
swap(s[i], s[len - 1 - i]);
}
return s;
}
/* check当前k是否可行 */
bool check(int k, vector<string> &a, vector<vector<int>> &b){
/* 计算前k个数字按位或的结果 */
char expectedNum[21]; //expected[j]表示结果的倒数第j位
for(int j = 1; j <= 20; j++){
if(b[k][j] > 0){
expectedNum[j] = '1';
}
else{
expectedNum[j] = '0';
}
}
for(int i = k + 1; i <= n; i++){
for(int j = 1; j <= 20; j++){
if(!(expectedNum[j] == '1' && b[i][j] - b[i - k][j] >= 1 || expectedNum[j] == '0' && b[i][j] - b[i - k][j] == 0)){
return false;
}
}
}
return true;
}
signed main(){
std::iostream::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
while(t--){
/* 初始输入 */
cin >> n;
vector<int> a(n + 1);
vector<string> A_inBinary(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
A_inBinary[i] = DtoB(a[i]);
}
vector<vector<int>> b(n + 1, vector<int>(21)); //b[i][j]表示前i行,倒数第j位上1的个数,前缀和的思想
for(int i = 1; i <= n; i++){
string s = A_inBinary[i];
int len = s.length();
for(int j = 1; j <= 20; j++){
b[i][j] = b[i - 1][j] + (s[len - j] == '1');
}
}
/* 二分 */
int l = 1, r = n, mid = (l + r) / 2, ans = mid;
while(l <= r){
mid = (l + r) / 2;
if(check(mid, A_inBinary, b)){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
cout << ans << "\n";
}
return 0;
}
注意点:
类似需要转换成二进制的题目,出现转换后长度不统一时,若有需要,可以将数组的长度开到最大(如a_max = 2`32,就将数组长度设为32),前面多余没用到的设为0(例如本段代码中的 expected 和 b 就将长度均设为21)