题目链接点这里
111 上大分了。
CF1922A Tricky Template
只要存在一个位置，使得 $c$ 和 $a, b$ 均不同就能构造出答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve()
{
int n;
cin >> n;
string a, b, c;
cin >> a >> b >> c;
for (int i = 0; i < n; ++i)
{
if (a[i] != c[i] && b[i] != c[i])
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
CF1922B Forming Triangles
注意到只有两个相同长度的木棍和另一个小于等于这个长度的木棍能够组成三角形。然后就可以用组合数公式计算答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve()
{
ll n, x, ans = 0, cnt = 0;
cin >> n;
map<int, int> book;
for (int i = 1; i <= n; ++i)
{
cin >> x;
book[x]++;
}
for (auto [x, y]: book)
{
ll num = y;
if (num >= 2)
ans += cnt * num * (num - 1) / 2;
if (num >= 3)
ans += num * (num - 1) * (num - 2) / 6;
cnt += num;
}
cout << ans << endl;
}
CF1922C Closest Cities
时隔一年我又犯了等号写成赋值的错误，令人感慨。（老玩家集体类目）
首先观察出能用最近点传送就一定用上，并且不会出现往回走的情况。然后看数据范围，要求快速计算两点间最短距离，那显然用前缀和做最合适了。先预处理出每个点的最近点，存在 $cls$ 里，然后从两个方向分别前缀和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void solve()
{
int n, m;
cin >> n;
vector<ll> arr(n + 1);
for (int i = 1; i <= n; ++i)
cin >> arr[i];
vector<ll> pre_lr(n + 1, 0), pre_rl(n + 1, 0);
vector<ll> cls(n + 1, 0);
cls[1] = 2;
cls[n] = n - 1;
for (int i = 2; i <= n - 1; ++i)
{
if (arr[i] - arr[i - 1] < arr[i + 1] - arr[i])
cls[i] = i - 1;
else
cls[i] = i + 1;
}
for (int i = 2; i <= n; ++i)
{
if (cls[i - 1] == i)
pre_lr[i] = pre_lr[i - 1] + 1;
else
pre_lr[i] = pre_lr[i - 1] + arr[i] - arr[i - 1];
}
for (int i = n - 1; i >= 1; --i)
{
if (cls[i + 1] == i)
pre_rl[i] = pre_rl[i + 1] + 1;
else
pre_rl[i] = pre_rl[i + 1] + abs(arr[i] - arr[i + 1]);
}
cin >> m;
while (m--)
{
int l, r;
cin >> l >> r;
if (l < r)
{
cout << pre_lr[r] - pre_lr[l] << endl;
}
else if (l > r)
{
cout << pre_rl[r] - pre_rl[l] << endl;
}
}
}
CF1922D Berserk Monsters
这道题需要一个能灵活删除元素的线性结构，那么就很容易想到用双向链表来存储怪兽。同时注意到，只有上一轮死亡怪物的左右两个位置才有可能在下一轮再发生变动。于是可以用 $acti$ 来存储可能发生变动的位置。一开始所有位置都存入 $acti$ 内，在每一轮去查询 $acti$ 内存的位置对应的怪物是否死亡，若死亡则把左右两个怪物加入下一轮的 $acti$ 中，像这样不断的模拟 $n$ 轮即得到答案。
再分析一下时间复杂度，存入 $acti$ 内的怪物数量是是一个常数乘上 $n$，$set$ 本身操作是 $\log{n}$ 级别，于是总的时间复杂度是 $O(n \log{n})$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void solve()
{
int n;
cin >> n;
vector<int> arr(n + 1), drr(n + 1);
for (int i = 1; i <= n; ++i)
cin >> arr[i];
for (int i = 1; i <= n; ++i)
cin >> drr[i];
vector<pii> adj(n + 1);
for (int i = 1; i <= n; ++i)
adj[i].fi = i - 1, adj[i].se = i + 1;
adj[1].fi = -1;
adj[n].se = -1;
set<int> acti;
for (int i = 1; i <= n; ++i)
acti.insert(i);
int round = n;
while (round--)
{
int dead = 0;
map<int, int> dmg;
for (auto id: acti)
{
int l = adj[id].fi;
int r = adj[id].se;
if (l != -1)
{
dmg[l] += arr[id];
if (acti.find(l) == acti.end())
dmg[id] += arr[l];
}
if (r != -1)
{
dmg[r] += arr[id];
if (acti.find(r) == acti.end())
dmg[id] += arr[r];
}
}
acti.clear();
for (auto [id, sumi]: dmg)
{
if (sumi > drr[id])
{
dead++;
int l = adj[id].fi;
int r = adj[id].se;
if (l != -1 && r != -1)
{
acti.insert(l);
acti.insert(r);
adj[l].se = r;
adj[r].fi = l;
}
else if (l == -1 && r != -1)
{
acti.insert(r);
adj[r].fi = -1;
}
else if (r == -1 && l != -1)
{
acti.insert(l);
adj[l].se = -1;
}
}
}
for (auto [id, sumi]: dmg)
{
if (sumi > drr[id])
acti.erase(id);
}
cout << dead << " ";
}
cout << endl;
}
CF1922E Increasing Subsequences
这题有两种思路，一种是套递增子序列模型，一种是找规律。
解1
求递增子序列（IS）数量是一个经典的动态规划问题，这题反过来，给定数量要求构造原序列。
首先抽象出下面两个操作（设 $x$ 是 IS 的数量，不考虑空子序列）：
- 在数组末尾添加一个最小的数，则 $x$ 变为 $x+1$。
- 在数组末尾添加一个比所有数都大的数，则 $x$ 变为 $2 \times x+1$。
然后逆向的考虑如何将 $x$ 变为 $0$：
- $x$ 为偶数时，在数组前面添加一个最小的数，则 $x$ 变为 $x-1$。
- $x$ 为奇数时，在数组前面添加 $cur$，则 $x$ 变为 $\frac{x-1}{2}$。
逆向操作形成的数组即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void solve()
{
ll x;
vector<int> ans;
cin >> x;
--x;
int cur = 100;
while (x != 0)
{
if (x % 2 == 0)
{
ans.pb(0);
--x;
}
else
{
ans.pb(cur--);
x /= 2;
}
}
reverse(all(ans));
cout << ans.size() << endl;
for (auto x : ans)
cout << x << " ";
cout << endl;
}
解2
由二项式定理得 $0, 1, 2, 3, …, x-1$ 的 IS 数量为 $2^x$。然后发现规律：先找出最大的 $x$，然后从大到小遍历每一个二进制位。如果第 $i$ 位是 $1$，则在序列最后添加一个 $i$，这样操作会让答案增加 $2^i$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
ll x;
cin >> x;
int maxi = __lg(x);
vector<int> ans;
for (int i = 0; i < maxi; ++i)
ans.pb(i);
for (int i = maxi - 1; i >= 0; --i)
{
if ((x >> i) & 1)
ans.pb(i);
}
cout << ans.size() << endl;
for (auto x: ans)
cout << x << " ";
cout << endl;
}
