补题链接：Here
1535A. Fair Playoff
四名选手参加了季后赛。比赛按以下方案进行：第一名选手与第二名选手比赛，第三名选手与第四名选手比赛，然后两人中的获胜者进入决赛。
众所周知，在两个选手之间的比赛中，技术更高的一个将获胜。第 (i) 位玩家的技能等于 (s_i) ，所有技能等级两两不同（i。 e。数组中没有两个相同的值。
如果两位技术最高的选手在决赛中相遇，这场比赛就被称为公平。
确定给定的比赛是否公平。
先进行比较，确定出线玩家的技能值大小，然后排序进行最终比较，如果技能值和相等则输出 YES，否则输出 NO
void solve() {
int a[4];
cin >> a[0] >> a[1] >> a[2] >> a[3];
int b = max(a[0], a[1]), c = max(a[2], a[3]);
sort(a, a + 4);
// cout << b << " " << c << " " << a[0] << " " << a[1] << "
";
if (a[2] + a[3] == b + c)cout << "YES
";
else cout << "NO
";
}
1535B. Array Reodering
好下标数对 ：(1le i < j le n) 并且 (gcd(a_i,2a_j) > 1)
请问在给定的大小为 (n) 的数组可重排序后的最大好下标数对的数量
如果 (a_i) 的值为偶数，那么 (gcd(a_i,2a_j)) 的值至少为 (2) 并且不必去考虑 (a_j) 的值，所以我们只需要把原数组的偶数放前面，奇数放后面即可
void solve() {
int n; cin >> n;
vector<int>a, b;
for (int i = 0, x; i < n; ++i) {
cin >> x;
if (x & 1)a.push_back(x);
else b.push_back(x);
}
vector<int>v;
for (int x : b)v.push_back(x);
for (int x : a)v.push_back(x);
int cnt = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (__gcd(v[i], 2 * v[j] ) > 1)cnt++;
cout << cnt << "
";
}
更新一发 H神 的写法：Lamda表达式，233ms -> 200ms
void solve() {
int n; cin >> n;
vector<int>a(n);
for (int &x : a)cin >> x;
sort(a.begin(), a.end(), [](const int &x, const int &y) {
return x % 2 < y % 2;
});
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
ans += __gcd(a[i], 2 * a[j]) > 1;
cout << ans << "
";
}
1535C. Unstable String
给你一个字符串s，定义如果一个字符串任意两个位置符号都不同，且只有0，1组成的字符串是不稳定的。
定义由0，1，？，组成的字符串，且？可以任意的转换成0和1，使字符串可以变成不稳定的字符串叫做美丽字符串。
给一个字符串求有多少子字符串可以形成美丽的字符串。
假如有一个区间 ([l,r]) ，如果这个区间内的字符串是美丽的，那以r结尾的美丽子字符串的贡献就是 r-l+1
我们每次让右指针向右遍历，如果当前区间是美丽字符串，那以 (r) 结尾的子符串产生的贡献就是 r-l+1，如果遍历的过程中当前的字符串不是美丽字符串，那我们就让左指针向右。
但是我们怎么判断当前的区间是不是美丽的呢？
我们判断一个字符串是不是美丽的，其实只需要判断当前区间是不是只有奇数位置上有一种字符，偶数位置上是另一种字符，? 号的时候可以忽略，因为有 ? 可以变成奇数和偶数，不会影响判断。
记得答案要开 long long。
因为如果是全是 ? 的串，最终的结果是 (n*(n+1)/ 2) 是会超出 int 的
void solve() {
string s;
cin >> s;
int type = 0, cnt = 0;
ll ans = 0;
for (int i = 0, j = 0; i < s.size(); ++i) {
while (j < s.size()) {
if (s[j] == '?')j++;
else if (cnt == 0 or type == (s[j] - '0') ^ (j % 2)) {
cnt++;
type = (s[j] - '0') ^ (j % 2);
j++;
} else break;
}
ans += j - i;
if (s[i] != '?')cnt--;
}
cout << ans << "
";
}
1535D. Playoff Tournament
【题意待补】
代码来自 H神，学习ing....
void solve() {
int k; string s;
cin >> k >> s, s = " " + s;
vector<int>par(1 << k), L(1 << k), R(1 << k), f(1 << k);
for (int i = 1, x = 1, y = (1 << (k - 1)) + 1; i < k; ++i) {
for (int j = 0; j < (1 << (k - i)); ++j) {
par[j + x] = j / 2 + y;
(j & 1 ? R : L)[j / 2 + y] = j + x;
}
x = y;
y += (1 << (k - 1 - i));
}
auto up = [&](int i) {
f[i] = 0;
if (i <= (1 << (k - 1)))f[i] = 1 + (s[i] == '?');
else {
if (s[i] != '1')f[i] += f[L[i]];
if (s[i] != '0')f[i] += f[R[i]];
}
};
for (int i = 1; i < (1 << k); ++i)up(i);
int _; for (cin >> _; _--;) {
int p; string c;
cin >> p >> c;
for (s[p] = c[0] ; p; p = par[p])up(p);
cout << f.back() << "
";
}
}