A. Doremy's Paint 3
对于式子 \(b_1 + b_2 = b_2 + b_3 = \dots = b_{n-1}+b_n=k\)，从中挑出 \(b_i + b_{i+1} = b_{i+1} + b_{i+2}\)，得到 \(b_i = b_{i+2}\)，这就意味着所有奇数位置上的数需要相等，所有偶数位置上的数也需要相等。
对于 \(n\) 个数而言，有 \(\lceil \frac{n}{2} \rceil\) 个奇数位置和 \(\lfloor \frac{n}{2} \rfloor\) 个偶数位置。因此，当且仅当可以找到 \(\lfloor \frac{n}{2} \rfloor\) 个相等的数并且余下部分内部也是相等的数时答案为 Yes。
情况可以分为以下三类：
- 所有的数都一样，比如 \([3,3,3,3,3,3]\)，此时答案为 Yes
- 有两种不同的数，比如 \([1,2,1,2,1]\)。如果其中一种数出现了恰好 \(\lfloor \frac{n}{2} \rfloor\) 次则答案为 Yes。例如 \([1,2,1,2,1]\) 和 \([2,3,2,3]\) 答案为 Yes 而 \([1,1,1,2]\) 和 \([3,3,3,3,4,4]\) 答案为 No。
时间复杂度为 \(O(n)\)。
参考代码
#include <cstdio>
const int N = 100005;
int a[N], cnt[N];
int main()
{
int t; scanf("%d", &t);
while (t--) {
int n; scanf("%d", &n);
int diff_num = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]); cnt[a[i]]++;
if (cnt[a[i]] == 1) diff_num++;
}
if (diff_num == 1) printf("Yes\n");
else if (diff_num > 2) printf("No\n");
else if (cnt[a[1]] == n / 2 || cnt[a[1]] == (n + 1) / 2) printf("Yes\n");
else printf("No\n");
for (int i = 1; i <= n; i++) cnt[a[i]]--;
}
return 0;
}
B. Qingshan Loves Strings
有三种情况答案为 Yes：
- s 本身是好的
- t 是好的，t 的头尾都是 '1'，而 s 中没有 "11"
- t 是好的，t 的头尾都是 '0'，而 s 中没有 "00"
参考代码
#include <cstdio>
const int N = 55;
char s1[N], s2[N];
bool good(char s[], int len) {
for (int i = 1; i < len; i++)
if (s[i] == s[i - 1]) return false;
return true;
}
bool check(char s[], int len, char ch) {
for (int i = 1; i < len; i++)
if (s[i] == ch && s[i - 1] == ch) return false;
return true;
}
int main()
{
int t; scanf("%d", &t);
while (t--) {
int n, m; scanf("%d%d%s%s", &n, &m, s1, s2);
bool res = good(s1, n);
if (res) printf("Yes\n");
else {
res = good(s2, m);
if (!res || s2[0] != s2[m - 1]) printf("No\n");
else if (check(s1, n, s2[0])) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
C. Qingshan Loves Strings 2
首先，如果 \(0\) 的数量和 \(1\) 的数量不一致则必然无解。
否则，可以按如下方法构造：
如果 \(s_1 \ne s_n\)，接下来不需要再考虑头尾字符，可以将剩余部分 \(s_{2...n-1}\) 看成新的 \(s\)，如果消除完毕，则结束构造。
如果 \(s_1 = s_n\)，假如两者都是 \(1\)，可以在前面插入 \(01\)，假如都是 \(0\)，可以在后面插入 \(01\)，例如：
"110010""1001""011001""1100""10"""
这样一来实际上将插入 \(01\) 这个操作转化成了把最后一位的 \(1\) 移到最前面或者是把第一位的 \(0\) 移到最后面。所以最坏情况下，每个字符都要移动，需要 \(n\) 次操作。
实际上最坏只需要 \(n/2\) 次操作，因为对于消除操作中的 \(0\) 和 \(1\)，最多只有其中一个需要移动。
时间复杂度为 \(O(n)\)。
参考代码
#include <cstdio>
#include <deque>
using namespace std;
const int N = 105;
char s[N];
int op[N];
int main()
{
int t; scanf("%d", &t);
while (t--) {
int n; scanf("%d%s", &n, s);
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++)
if (s[i] == '0') cnt0++;
else cnt1++;
if (cnt0 != cnt1) printf("-1\n");
else {
deque<char> dq;
for (int i = 0; i < n; i++) dq.push_back(s[i]);
int p = 0, del = 0;
while (!dq.empty()) {
if (dq.front() != dq.back()) {
dq.pop_front(); dq.pop_back(); del++;
} else {
p++;
if (dq.front() == '0') {
op[p] = n - del; dq.push_back('0'); dq.push_back('1');
} else {
op[p] = del; dq.push_front('1'); dq.push_front('0');
}
n += 2;
}
}
if (p == 0) printf("0\n\n");
else {
printf("%d\n", p);
for (int i = 1; i <= p; i++) printf("%d%c", op[i], i == p ? '\n' : ' ');
}
}
}
return 0;
}
D. Doremy's Connecting Plan
不妨假设 \(c=1\)，实际上当 \(c \ne 1\) 时，只需要令 \(a_i'= \frac{a_i}{c}\) 即和 \(c=1\) 的情况等价。
设 \(s_i = \sum a_j\)，其中 \(j\) 是 \(i\) 当前所连接的结点。
如果 \(i\) 和 \(j\) 之间可以连边（\(i \ne 1, j \ne 1\)），相当于要求 \(s_i + s_j \ge i \cdot j \ge i + j\)。
而这实际上可以推出 \(s_i \ge i\) 和 \(s_j \ge j\) 这两个条件中至少有一个成立（否则 \(s_i + s_j < i + j\)），不妨设 \(s_i \ge i\)。由此推出 \(s_i + s_1 \ge 1 \cdot i\)，也就是说可以在 \(i\) 和 \(1\) 之间连一条边。
而且，添加一条新的边不会导致原来能加的边变得不能加，所以我们可以永远考虑 \(1\) 和 \(i\) 之间能不能连边，这样一来只需要考虑顺序即可。
对于式子 \(s_i + s_1 \ge 1 \cdot i\)，可以发现 \(s_i - i\) 越大，结点 \(i\) 就越有可能和 \(1\) 相连，所以我们可以按 \(a_i - i\) 降序排序，按照这个顺序依次处理每个结点是否可以和 \(1\) 相连。
时间复杂度为 \(O(n \log n)\)。
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200005;
int order[N], c;
LL a[N];
bool cmp(int i, int j) {
return a[i] - a[j] > 1ll * c * (i - j);
}
int main()
{
int t; scanf("%d", &t);
while (t--) {
int n; scanf("%d%d", &n, &c);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]); order[i] = i;
}
sort(order + 2, order + n + 1, cmp);
LL sum = a[1];
bool ok = true;
for (int i = 2; i <= n; i++) {
int idx = order[i];
if (sum + a[idx] >= 1ll * idx * c) {
sum += a[idx];
} else {
ok = false; break;
}
}
printf("%s\n", ok ? "Yes" : "No");
}
return 0;
}
E1. Doremy's Drying Plan (Easy Version)
首先考虑暴力做法。
对于每一个位置 \(i=1,2,3,...,n\) 我们可以通过差分与前缀和预处理每个位置被线段覆盖的次数。首先，对于每个覆盖次数为 \(0\) 的位置，可以放到最后再考虑，因为这部分点的数量与移除的两条线段无关，设这部分点的数量为 \(A\)，再设移除两条线段后产生的新的不被覆盖的点的数量是 \(B\)，则本题的答案为 \(A + \max B\)。
要计算 \(B\)，考虑每一对线段 \(I_1, I_2\)：
- 如果两者不交叉，\(B\) 等于 \(I_1\) 和 \(I_2\) 中刚好覆盖一次的点的数量之和；
- 如果两者交叉，假设两者交叉的线段为 \(J\)，则 \(B\) 等于\(I_1\) 和 \(I_2\) 中刚好覆盖一次的点的数量之和再加上 \(J\) 中恰好覆盖两次的点的数量。
如果直接枚举每一对线段，则时间复杂度为 \(O(n + m^2)\)，考虑优化这个算法：
- 对于两线段不交叉的情况，实际上直接从所有线段中挑出覆盖一次的点的数量最多的两条即可；
- 对于两线段交叉的情况，实际上真正有用的最多只有 \(n\) 对线段：对于每一个位置 \(i\)，如果它恰好被覆盖两次，此时就考虑覆盖这个点的两条线段即可。
对于某一个点，如何维护覆盖它的线段？这里我们可以把每个线段 \([l,r]\) 看成是在 \(l\) 位置开始计算时引入，在 \(r\) 位置完成计算后移除，可以利用一个 multiset 来维护当前涉及到的线段，这样一来时间复杂度优化到 \(O(n+m \log m)\)。
参考代码
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 200005;
vector<int> left[N], right[N];
int diff[N], cnt[N], sum1[N], sum2[N];
multiset<pair<int, int>> s;
int main()
{
int t; scanf("%d", &t);
while (t--) {
int n, m, k; scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
left[i].clear(); right[i].clear();
diff[i] = 0;
}
for (int i = 1; i <= m; i++) {
int l, r; scanf("%d%d", &l, &r);
left[l].push_back(r); right[r].push_back(l);
diff[l]++; diff[r + 1]--;
}
for (int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + diff[i];
for (int i = 1; i <= n; i++) {
sum1[i] = sum1[i - 1]; sum2[i] = sum2[i - 1];
if (cnt[i] == 1) sum1[i]++;
else if (cnt[i] == 2) sum2[i]++;
}
// only 1
int max1 = 0, max2 = 0;
for (int i = 1; i <= n; i++)
for (int x : left[i]) {
// [i, x]
int cur = sum1[x] - sum1[i - 1];
if (cur > max1) {
max2 = max1; max1 = cur;
} else if (cur > max2) max2 = cur;
}
int ans = max1 + max2;
// 1+2
s.clear();
for (int i = 1; i <= n; i++) {
for (int x : left[i]) s.insert({i, x});
if (cnt[i] == 2) {
auto it = s.begin();
int l1 = it->first, r1 = it->second;
it++;
int l2 = it->first, r2 = it->second;
int a = l1, b = r1, c = l2, d = r2;
// sort
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (a > d) swap(a, d);
if (b > c) swap(b, c);
if (b > d) swap(b, d);
if (c > d) swap(c, d);
ans = max(ans, sum1[d] - sum1[a - 1] + sum2[c] - sum2[b - 1]);
}
for (int x : right[i]) s.erase(s.find({x, i}));
}
for (int i = 1; i <= n; i++) if (cnt[i] == 0) ans++;
printf("%d\n", ans);
}
return 0;
}