CF大陆斗C战士（三）

C. Good Subarrays

题目大意

如果一个子数组的数组元素之和等于数组元素个数，则称其为好子数组。给你一个数组，问其中的好子数组有多少个。

题目分析

一个子数组的数组元素之和等于数组元素个数为好子数组，那么如果将每一位减一，则元素和为零时为好子数组。

假设当前前缀和为sum，若使子数组和为0则需要减去和同样为sum的前，即sum之前出现了多少次，既可以得到几个好子数组。注意当前缀和本身为0时，本身就作为一种方案。

code

#include<bits/stdc++.h>
#define int long longusing namespace std;int n, m, k, t;void solve()
{map<int, int>q;string s;cin >> n >> s;int ans = 0, sum = 0;for(int i = 0; i < n; i ++){sum += s[i] - '0' - 1;if(!sum) ans ++;ans += q[sum];q[sum] ++;}cout << ans << "\n";
}signed main()
{cin >> t;while(t --) solve();return 0;
}

C. Boboniu and Bit Operations

题目大意

给你两个数组a和b，规定c[i]=a[i]&b[j]，找到c1 | c2…|cn的最小值

题目分析

几个数之间进行&操作，数值只会不变或者变小。几个数之间进行|操作，数值只会不变或者变大。

设c1 | c2…|ci结果为res，若要使最终结果则在多异或数的情况下要保证res不变，我们只需找到置否有相应的a[i]与b[j]配队满足即可。

对于res的范围最小值为0而最大值应为a中元素相或之和。从小到大枚举res即可

code

#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 210;int n, m, k, t;
int a[N], b[N];bool check(int x)
{int cnt = 0;for(int i = 1; i <= n; i ++)for(int j = 1;j <= m; j ++){if(((a[i] & b[j]) | x) == x){cnt ++;break;}}if(cnt == n) return true;else return false;
}void solve()
{int maxn = 0;cin >> n >> m;for(int i = 1; i <= n; i ++){cin >> a[i];maxn |= a[i];}for(int i = 1; i <= m; i ++) cin >> b[i];for(int i = 0; i <= maxn; i ++){if(check(i)){cout << i << "\n";break;}}
}signed main()
{solve();return 0;
}

C. Rings

题目大意

有一个01串，需要你选出两个区间 [l1, r1] 和 [l2, r2]满足以下条件：

• 1≤l1≤n ,1≤r1≤n, r1−l1+1≥n/2
• 1≤l2≤n, 1≤r2≤n, r2−l2+1≥n/2
• 至少满足 l1 != l2，r1!= r2两条件当中的一个
• 第一个区间所转化成的十进制值的值应当是第二个的k倍

题目分析

全为1的情况只需要找出长度相等且满足要求的两段即可，得到的数值是一样的

成倍数关系在二进制中比较容纳工艺想到和办到应该是左移，如11100是1110的二倍，当零在第一位时00011和0011数值应当是相等的

code

#include<bits/stdc++.h>using namespace std;int n, m, k, t;void solve()
{string s;cin >> n >> s;s = " " + s;for(int i = 1; i <= n / 2; i ++){if(s[i] == '0'){cout << i << " " << n << " " << i + 1 << " " << n << "\n";return;}}for(int i = n / 2 + 1; i <= n; i ++){if(s[i] == '0'){cout << 1 << " " << i << " " << 1 << " " << i - 1 << "\n";return;}}cout << 1 << " " << n - 1 << " " << 2 << " " << n << "\n";
}int main()
{cin >> t;while(t --) solve();return 0;
}