Codeforces Global Round 26
A
如果 \(a_1 = a_n\)，无解。
如果 \(a_2 = a_n\)，\(a_1, a_2\) 涂成红色，否则只把 \(a_1\) 涂成红色。
void solve() {
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
if(a[1] == a[n]) {
cout << "NO\n";
return;
}
cout << "YES\n";
if(a[2] != a[n]) {
cout << "R";
for(int i = 2; i <= n; ++ i) {
cout << "B";
}
cout << '\n';
return;
}
cout << "RR";
for(int i = 3; i <= n; ++ i) {
cout << "B";
}
cout << '\n';
}
B
如果首位不等于 \(1\)，无解。
否则可以推出两个数 \(a + b = x\) 每一位的和，且这个和一定属于 \([10, 18]\)，否则无解。
例如：\(1393938\)。
- \(a_0 + b_0 = 18\)。
- \(a_1 + b_1 = 13 - 1\)（一定有进位）。
- \(a_2 + b_2 = 19 - 1\)。
以此类推。
void solve() {
ll x; cin >> x;
auto s = to_string(x);
int n = s.length();
if(s[0] != '1') {
cout << "NO\n";
return;
}
for(int i = 0; i <= n - 2; ++ i) {
int x = 10 + s[i + 1] - '0';
if(i != n - 2) -- x;
if(x < 10 || x > 18) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
C1
void solve() {
ll n, mi = 0, mx = 0;
cin >> n;
for(int i = 1; i <= n; ++ i) {
int x; cin >> x;
ll pi = mi, px = mx;
mx = max({px + x, abs(px + x), pi + x, abs(pi + x)});
mi = min({px + x, abs(px + x), pi + x, abs(pi + x)});
}
cout << mx << '\n';
}
C2
void solve() {
ll n, mi = 0, mx = 0, ai = 1, ax = 1;
cin >> n;
for(int i = 1; i <= n; ++ i) {
int x; cin >> x;
ll pi = mi, px = mx;
ll pai = ai, pax = ax;
mx = max({px + x, abs(px + x), pi + x, abs(pi + x)});
mi = min({px + x, abs(px + x), pi + x, abs(pi + x)});
ai = 0;
ax = 0;
ax = (ax + pax * ( (mx == px + x) + (mx == (abs(px + x)) ) ) ) % P;
ai = (ai + pax * ( (mi == px + x) + (mi == (abs(px + x)) ) ) ) % P;
if(px != pi) {
ax = (ax + pai * ( (mx == pi + x) + (mx == (abs(pi + x)) ) ) ) % P;
ai = (ai + pai * ( (mi == pi + x) + (mi == (abs(pi + x)) ) ) ) % P;
}
}
cout << ax << '\n';
}
D
设 \(s\) 长度为 \(n\)。特判全为 a 的情况，共 \(n - 1\) 种方案。
设 \(s\) 中非 a 字符的数量为 \(m\)。
如果 \(t\) 中有 \(k\) 个非 a 字符，把 \(t\) 掐头去尾忽略前后的 a 后，原串里一定恰好存在 \(\dfrac{m}{k}\) 个 \(t'\)，且 \(k\mid m\)。
枚举 \(k\)。记录第 \(i\) 个非 a 字符的位置为 \(p_i\)（从 \(0\) 开始），如果 \(s_{p_i} \ne s_{p_i - k}\) 或不在分割处的 \(p_i - p_{i - 1}\ne p_{i - k} - p_{i - k - 1}\)，\(t'\) 不合法。
把 \(t'\) 还原为 \(t\)，枚举左边有的 a 个数 \(l \in [0, p_0]\)。
设 \(x\) 为分割处的最小间隔 \(\min(p_i - p_{i - 1}),\ k \mid i\)，则右边的 a 个数 \(r \in [0, \min(x - l, n - p_{m - 1} - 1)]\)。
void solve() {
string s;
cin >> s;
int n = s.length();
if(count(s.begin(), s.end(), 'a') == n) {
cout << n - 1 << '\n';
return;
}
vector<int> a;
for(int i = 0; i < n; ++ i) {
if(s[i] != 'a') {
a.eb(i);
}
}
int m = a.size();
ll ans = 0;
for(int i = 1; i <= m; ++ i) {
if(m % i) {
continue;
}
int ok = 1;
for(int j = i; j < m; ++ j) {
int o = j % i;
if(s[a[j]] != s[a[o]] || (o && a[o] - a[o - 1] != a[j] - a[j - 1])) {
ok = 0;
break;
}
}
if(ok) {
int mi = n;
for(int j = i; j < m; j += i) {
mi = min(mi, a[j] - a[j - 1] - 1);
}
int r = n - a.back() - 1;
for(int l = 0; l <= a[0]; ++ l) {
ans += max(0, min(r + 1, mi - l + 1));
}
}
}
cout << ans << '\n';
}