https://codeforces.com/contest/1762
A. Divide and Conquer
分析：
数组所有元素和为偶数则为good。那么肯定要考虑奇偶性问题。
1.如果和直接==偶数，那cout << 0;
2.但是一个数除2向下取整是不明确除几次的（因为一个数可以表示成），因此对所有数分别除2，尝试每次都更新次数最小值即可。
ac代码：
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
void s(){
int n;
cin >> n;
vector<int> a(n + 1);
long long sum = 0;
for(int i = 1; i <= n; i ++) cin >>a[i], sum += a[i];
int ans = INF;
if(sum % 2 == 0){
cout << 0 << endl;
return;
}else{
for(int i = 1; i <= n; i ++){
int cnt = 0;
if(a[i] % 2 == 0){
while(a[i] % 2 == 0){
a[i] /= 2;
cnt ++;
}
}else {
while(a[i] % 2 == 1){
a[i] /= 2;
cnt ++;
}
}
ans = min(ans, cnt);
}
}
cout << ans << endl;
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t;
cin >> t;
while(t--) s();
return 0;
}
B.Make Array Good
大意：数组中任意两元素可以整除。
分析：要将所有的数变到某个数的倍数上。如果数学思维敏锐的话，可以每个数发觉变到离它最近的最好，因为这是最小的倍数梯度，任何一个数都可以落在2的x次方到x+1次方之间，仅仅增加一次可以变成2的倍数。
ac代码：
#include <bits/stdc++.h>
#define endl '\n'
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
int beishu[505], tt;
void s(){
int n;
cin >> n;
vector<int> a(n);
for(auto &i:a) cin >> i;
int times = 0;
vector<pair<int, long long>> ans;
for(int i = 0; i < n; i ++){
long long big = 0;
for(int j = 0; j < tt; j ++) {
if(beishu[j] >= a[i]) {
big = beishu[j];
break;
}
}
while(a[i] < big) {
if(a[i] + a[i] <= big) ans.push_back({i + 1, a[i]}) , a[i] += a[i];
else ans.push_back({i + 1, big - a[i]}), a[i] = big;
times ++;
}
}
cout << times << endl;
for(auto i : ans) {
cout << i.first << " " << i.second << endl;
}
}
void get(){
long long num = 1;
beishu[0] = 1;tt = 1;
while(num <= 1e18) beishu[tt ++] = (num *= 2);
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
get();
int t;
cin >> t;
while(t--) s();
return 0;
}
C. Binary Strings are Fun
大意：
定义good规则：对于每个奇数(2m-1)下标，该下标对应的字符在当前下标前出现的次数必须>=m. 例如：1001011 and 1101001
都是1001的good子串，因为下标1对应字符‘1’在此之前出现次数是1；下标3对应字符‘0’在此之前出现的次数是2；下标5对应字符‘0’在此之前出现次数是3；下标7对应字符‘1’在此之前出现次数是4。
对于每个前缀二进制子串，将它拉开，两两之间留个空位可以穿插0或1.询问所有的子串可能的情况数量总和。
每一个子串的答案是：len是后缀相等字符个数。
简单来说
这个样例手动模拟的时候发现后面四个1就是2倍变化。
前面10101交替的时候，为了保证子串good数组一定至少有1个数，那肯定会导致在结尾0变1或1变0的时候会把前面穿插的元素变成与最后一个元素对应的数，会限制成1次。
ac代码：
#include <bits/stdc++.h>
#define endl '\n'
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, INF = 0x3f3f3f3f, mod = 998244353;
//函数内初始化数组={}
long long qmi(long long a, long long b, long long mod){
long long ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b /= 2;
}
return ans;
}
void solve(){
int n;
cin >> n;
string a;
cin >> a;
vector<long long> suffix(n + 1);
int len = 0;
for(int i = n - 1, j = n - 1; i >= 0; i --){
if(i == j) {
while(a[j] == a[i]) j --;
}
len = i - j;
suffix[i] = qmi(2, len - 1, mod);
}
long long ans = 0;
for(int i = 0; i < n; i ++){
ans = (ans + suffix[i]) % mod;
}
cout << ans << endl;
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t;
cin >> t ;
while(t--) solve();
return 0;
}