codeforce round951 div2

A guess the maximum

问题：

翻译一下就是求所有相邻元素中max - 1的最小值

代码：

#include <iostream>
#include <algorithm>using namespace std;const int N = 5e4;int a[N];
int n;void solve() {cin >> n;int ans = 0x3f3f3f3f;for(int i = 1; i <= n; i ++ ) cin >> a[i];for(int i = 1; i <= n - 1; i ++ ) {int k = max(a[i], a[i + 1]) - 1;ans = min(ans, k);}cout << ans << endl;
}int main() {int t;cin >> t;while(t -- ) {solve();}return 0;
}

B Xor sequences

题目：

思路：guess题，就是求两个数的lowbit

代码：

#include <iostream>
#include <algorithm>using namespace std;const int N = 5e4;int a[N];
int n;void solve() {int x, y;cin >> x >> y;int ans = 1;for(int i = 0; i <= 30; i ++ ) {int xx = x >> i & 1;int yy = y >> i & 1;if(xx == yy) ans *= 2;else break;}cout << ans << endl;
}int main() {int t;cin >> t;while(t -- ) {solve();}return 0;
}

C earning on bets

题目：

思路：

以下为不严谨证明

假设有n = 3 

k1 k2 k3

x1 x2 x3

满足x1 * k1 > x1 + x2 + x3

        x2 * k2 > x1 + x2 + x3

        x3 * k3 > x1 + x2 + x3

变形后有sigma 1/k < 1

由于分数的精度不好计算，因此考虑乘上所有k的lcm

即 lcm * sigma 1/k < lcm

这个是判断条件，如果成立给每个1/k乘上lcm即可

代码：

#include <iostream>using namespace std;const int N = 2e5 + 10;int k[N];int _gcd(int a, int b) {return b? _gcd(b, a % b): a;
}int lcm(int a, int b) {return a * b / _gcd(a, b);
}void solve() {int n;cin >> n;for(int i = 1; i <= n; i ++ ) cin >> k[i];int L = 1;for(int i = 1; i <= n; i ++ ) {L = lcm(L, k[i]);} int sum = 0;for(int i = 1; i <= n; i ++ ) {sum += L / k[i];}if(sum >= L) cout << -1;else for(int i = 1; i <= n; i ++ ) {cout << L / k[i] << " ";}
}int main() {int t;cin >> t;while( t-- ) {solve();}
}

D fixing a binary string

题目：

思路：对原操作进行化简，实际上就是把前p个字符翻转，并且接到原字符串的后面，则此时我们的答案串实际上是已知的如果第p个字符是1，那么答案串就是以1结尾的k pop串，反之则是以0

结尾的k pop串，既然答案已知我们遍考虑枚举p，之后在o1内用哈希字符串比较。注意到还要对原串翻转，因此还要倒着求一遍哈希

这题没有卡哈希

代码：

#include <iostream>
#include <algorithm>using namespace std;const int N = 2e5 + 10;
const int P = 131;typedef unsigned long long ULL;int n, k;
char s[N], str[N];
ULL ansh[N], h[N], p[N], reh[N];
/*
re (n - p + 1 , n) == ans (n - p + 1, n);
h p + 1, n == ans 1, n - p
*/
bool check(int x) {if(reh[n] - reh[n - x] * p[x] == ansh[n] - ansh[n - x] * p[x]) {if(h[n] - h[x] * p[n - x] == ansh[n - x] - ansh[0] * p[n - x]) {return true;}       }return false;
}void solve() {cin >> n >> k;for(int i = 1; i <= n; i ++ ) cin >> s[i];p[0] =  1;int c = s[1] - '0';for(int i = n, cnt = 1, judge = 1; i; i --, judge ++ ) {if(cnt & 1) str[i] = c + '0';else str[i] = !c + '0';if(judge % k == 0) cnt ++;}for(int i = 1; i <= n; i ++ ) p[i] = p[i - 1] * P;for(int i = 1; i <= n; i ++ ) h[i] = h[i - 1] * P + s[i];for(int i = 1; i <= n; i ++ ) ansh[i] = ansh[i - 1] * P + str[i];reverse(s + 1, s + n + 1);for(int i = 1; i <= n; i ++ ) reh[i] = reh[i - 1] * P + s[i];for(int i = 1; i <= n; i ++ ) {if(check(i)) {cout << i << endl;return;}}cout << -1 << endl;
}int main() {int t;cin >> t;while(t -- ) {solve();}return 0;
}