A. Doremy's Paint 3
记数组中数的种类数为\(k\)，当\(k=1\)时，答案为\(yes\)；当\(k=2\)时，记两个种类的数的个数差为\(d\)，当\(d≤1\)时，答案为\(yes\)；其他情况答案为\(no\)。
时间复杂度：\(O(nlogn)\)
1 void solve()
2 {
3 int n; cin >> n;
4
5 map<int, int> mp;
6 vector<int> a(n + 1);
7 for (int i = 1; i <= n; i++)
8 {
9 cin >> a[i];
10 mp[a[i]]++;
11 }
12 if (mp.size() == 1 || (mp.size() == 2 && abs(mp.begin()->sc - (--mp.end())->sc) <= 1)) cout << "YES\n";
13 else cout << "NO\n";
14 }
B. Qingshan Loves Strings
顺序遍历\(s\)，若遇到相邻两字符相等时，则尝试在他们中间加入\(t\)，若\(t\)本身不是好的或加入\(t\)后\(s\)仍然是不好的（可以用\(t\)的首尾字符直接比较，不用真的加入），答案则为\(no\)；其他情况答案为\(yes\)。
时间复杂度：\(O(n+m)\)
1 void solve()
2 {
3 int n, m;
4 cin >> n >> m;
5
6 string s, t;
7 cin >> s >> t;
8
9 char f = t.front(), b = t.back();
10
11 bool OK = true, used = false;
12 for (int i = 0; i < n - 1; i++)
13 if (s[i] == s[i + 1])
14 {
15 if (s[i] == f || s[i + 1] == b) OK = false;
16 else used = true;
17 }
18
19 if (!OK) cout << "NO\n";
20 else if (!used) cout << "YES\n";
21 else
22 {
23 for (int i = 0; i < m - 1; i++)
24 if (t[i] == t[i + 1])
25 {
26 cout << "NO\n";
27 return;
28 }
29
30 cout << "YES\n";
31 }
32 }
C. Qingshan Loves Strings 2
当\(n\)为奇数时，答案为\(-1\)；当\(n\)为偶数时，记\(s\)当前的首字符为\(f\)，尾字符为\(b\)，当\(f=b\)时，若\(f=1\)，则在当前\(s\)的开头插入\(01\)，若\(f=0\)，则在当前s的结尾插入\(10\)，当\(f≠b\)时，不进行插入操作；
此时\(s\)的首尾字符一定不相等，则\(s\)去除首尾字符，接着对新的\(s\)进行相同的考虑即可。（进行插入操作时要记录该插入点前面的字符数量，特别注意\(s\)开头删除过的字符）
当插入次数大于\(300\)时，答案为\(-1\)，否则输出插入操作数和具体操作。
时间复杂度：\(O(n)\)
1 void solve()
2 {
3 int n;
4 cin >> n;
5
6 string s;
7 cin >> s;
8
9 deque<char> dq;
10 for (auto i : s) dq.pb(i);
11
12 int tim = 0, sf = 0;
13 vector<int> ans;
14 while (dq.size() >= 2 && tim <= 300)
15 {
16 auto f = dq.front(), b = dq.back();
17 sf++;
18 if (f != b)
19 {
20 dq.pop_back();
21 dq.pop_front();
22 }
23 else
24 {
25 tim++;
26 if (f == '0')
27 {
28 ans.push_back(dq.size() + sf);
29 dq.pop_front();
30 dq.push_back('0');
31 }
32 else
33 {
34 ans.push_back(0 + sf);
35 dq.pop_back();
36 dq.push_front('1');
37 }
38 }
39 }
40
41 if (tim > 300 || dq.size() == 1) cout << -1 << '\n';
42 else
43 {
44 cout << ans.size() << '\n';
45 for (auto i : ans) cout << i << " ";
46 cout << '\n';
47 }
48 }
D. Doremy's Connecting Plan
若所有点能加边连通，则最优方法是点\(2\)到点\(n\)按某种顺序与点\(1\)依次相连来实现，换言之，若两不为\(1\)且不同的点能先连边，则他们都能与\(1\)先后连边。
简要证明：\(1\)与\(i\)和\(j\)都不能连边即\(a_1+a_i<ic\)且\(a_1+a_j<jc\),两式相加即\(2a_1+a_i+a_j<c(i+j)\)，i与j能连边即\(a_i+a_j≥cij\)，显然\(ij>i+j\)，前后两式相矛盾，证毕。
则可以用贪心的方法使点\(2\)到点\(n\)按\(ic-a[i]\)的值升序排序，依次与点\(1\)相连即可。
时间复杂度：\(O(nlogn)\)
1 #define int long long
2
3 void solve()
4 {
5 int n, c;
6 cin >> n >> c;
7
8 vector<int> a(n + 1);
9 for (int i = 1; i <= n; i++) cin >> a[i];
10
11 vector<int> order(n + 1);
12 iota(order.begin() + 2, order.end(), 2);
13 sort(order.begin() + 2, order.end(), [&](int i, int j){return i * c - a[i] < j * c - a[j];});
14
15 int now = a[1];
16 for (int i = 2; i <= n; i++)
17 {
18 int j = order[i];
19 if (now + a[j] < j * c)
20 {
21 cout << "NO\n";
22 return;
23 }
24 now += a[j];
25 }
26 cout << "YES\n";
27 }
E1. Doremy's Drying Plan (Easy Version)
首先可以用差分数组和前缀和求出每一天被的覆盖次数\(d\)，则\(d=0\)的天数一定为答案的一部分，又因为可以撤消其中的两个区间，所以\(d=1\)和\(d=2\)的天数都有可能更新答案，则我们可以枚举两个区间\(A\)和\(B\)来实现。
分两种情况枚举，当\(A\)与\(B\)不相交时，则直接选择使\(d=1\)的天数减去最多的两个区间即可；当\(A\)与\(B\)相交时，我们只需要枚举每处使\(d=2\)的\(A\)和\(B\)即可，显然这样的\(A\)与\(B\)不超过\(n\)对。
时间复杂度：\(O(mlogn)\)
1 void solve()
2 {
3 int n, m, k;
4 cin >> n >> m >> k;
5
6 vector<int> d(n + 2);
7 vector<int> l(m + 1), r(m + 1);
8 for (int i = 1; i <= m; i++)
9 {
10 cin >> l[i] >> r[i];
11 d[l[i]]++, d[r[i] + 1]--;
12 }
13
14 vector s(3, vector<int>(n + 1));
15 for (int i = 1; i <= n; i++)
16 {
17 d[i] += d[i - 1];
18 for (int j = 1; j <= 2; j++)
19 s[j][i] = s[j][i - 1] + (d[i] == j);
20 }
21
22 int cnt = count(d.begin() + 1, d.end() - 1, 0), ans = cnt;
23
24 multiset<int> c1;
25 for (int i = 1; i <= m; i++)
26 c1.insert(s[1][r[i]] - s[1][l[i] - 1]);
27 auto it = --c1.end();
28 ans += (*it) + (*(--it));
29
30 set<int> c2;
31 for (int i = 1; i <= n; i++)
32 {
33 if (d[i] != 2) continue;
34 c2.insert(i);
35 }
36
37 vector a(n + 1, vector<int>(0));
38 for (int i = 1; i <= m; i++)
39 {
40 auto it = c2.lower_bound(l[i]);
41 while (it != c2.end() && (*it) <= r[i])
42 {
43 a[(*it)].push_back(i);
44 it++;
45 }
46 }
47
48 for (int i = 1; i <= n; i++)
49 {
50 if (d[i] != 2) continue;
51 int seg1 = a[i][0], seg2 = a[i][1];
52 int L1 = min(l[seg1], l[seg2]), L2 = max(l[seg1], l[seg2]);
53 int R1 = max(r[seg1], r[seg2]), R2 = min(r[seg1], r[seg2]);
54 int val = s[1][R1] - s[1][L1 - 1] + s[2][R2] - s[2][L2 - 1];
55 ans = max(ans, val + cnt);
56 }
57
58 cout << ans << '\n';
59 }