A.Tricky Template (模拟)
题意：
询问是否存在一个字符串模板 t t t使得字符串 a a a， b b b与之匹配， c c c不匹配，匹配条件如下：
- 如果模板中第 i i i个字母是小写字母，那么 s i s_i si必须与 t i t_i ti相同。
- 如果模板中的第 i i i个字母是大写字母，那么 s i s_i si必须与 t i t_i ti的小写字母不同。例如，如果模板中有字母 A A A，则在字符串的相应位置不能使用字母 a a a。
分析：
如果字符串 c c c中有一个字符和字符串 a a a，字符串 b b b都不同就存在符合条件的字符串模板 t t t。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int t;
cin >> t;
while (t--) {
int n;
string a, b, c;
cin >> n >> a >> b >> c;
bool flag = 0;
for (int i = 0; i < n; i++)
if (c[i] != a[i] && c[i] != b[i]) {
flag = 1;
break;
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
B.Forming Triangles (模拟)
题意：
有 n n n根木棍，第 i i i根木棍长度为 2 a i 2^{a_i} 2ai。询问从 n n n根木棍中选出 3 3 3根木棍组成一个三角形的方案数。
分析：
先使用计数排序（桶的思想）统计各个数字的出现次数，然后考虑合法的情况。
合法的情况有两种：
- 同种长度木棍选择两根，再选一根短的木棍。
- 选择长度相等的三根木棍。
简单组合数公式计算即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<LL> a(n + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x]++;
}
LL ans = 0;
LL lst = 0;
for (int i = 0; i <= n; i++) {
LL x = a[i];
if (x >= 2) {
ans += x * (x - 1) / 2 * lst;
}
if (x >= 3) {
ans += x * (x - 1) * (x - 2) / 6;
}
lst += x;
}
cout << ans << endl;
}
return 0;
}
C. Closest Cities (前缀和)
题意：
n n n个城市分布在一个数轴上，第 i i i个城市的坐标为 a i a_i ai，保证 a i a_i ai升序，并保证对于每一个 i i i，距离他最近的城市只有一个。有两种城市间移动的方式：
-
花费 1 1 1元转移到当前所在城市最近的城市。
-
花费 ∣ a x − a y ∣ \vert a_x-a_y \vert ∣ax−ay∣元，从 x x x移动到 y y y。
给出 m m m次询问，每次给出两个城市 x x x, y y y，询问从 x x x到 y y y最少需要花费多少元。
分析：
可以发现，最优的移动方式一定是尽量选择转移到离当前城市最近的城市。可以分别计算从前到后和从后到前两个方向的花费，分别维护从前到后和从后到前的前缀和即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 1e18;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<LL> a(n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = -inf;
a[n + 1] = inf;
vector<LL> sum1(n + 2), sum2(n + 2);
for (int i = 1; i <= n; i++) {
if (a[i + 1] - a[i] < a[i] - a[i - 1])
sum1[i + 1] = sum1[i] + 1;
else
sum1[i + 1] = sum1[i] + a[i + 1] - a[i];
}
for (int i = n; i >= 1; i--) {
if (a[i] - a[i - 1] < a[i + 1] - a[i])
sum2[i - 1] = sum2[i] + 1;
else
sum2[i - 1] = sum2[i] + a[i] - a[i - 1];
}
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
LL ans = 0;
if (y > x)
ans = sum1[y] - sum1[x];
else
ans = sum2[y] - sum2[x];
cout << ans << endl;
}
}
return 0;
}
D.Berserk Monsters(模拟)
题意：
Monocarp在打怪。
一排有 n n n个怪物，编号从 1 1 1到 n n n。其中第 i i i个怪物有两个参数：攻击值等于 a i a_i ai，防御值等于 d i d_i di。为了杀死这些怪物，Monocarp给它们施放了狂暴咒语，因此它们会互相攻击，而不是攻击Monocarp。
战斗由 n n n个回合组成。每回合都会发生以下情况：
- 首先，每个活着的怪物 i i i都会对左边最近的活着的怪物(如果存在)和右边最近的活着的怪物(如果存在)造成 a i a_i ai伤害;
- 然后，每只在本回合中受到超过 d j d_j dj伤害的活着的怪物 j j j都会死亡。也就是说，当且仅当第 j j j个怪物的防御值 d j d_j dj小于它在本轮受到的总伤害时，它才会死亡。
计算每一轮中死亡的怪物数量。
分析：
这道题的本质是模拟，我们可以想到对于每个结点，我们都需要找他的左右两个相邻的结点，因此我们采取链表的写法，用链表维护相邻的怪物，随后在每一次遍历的过程中找到死亡的结点，随后对左右节点的前驱和后继进行改变。每一轮遍历都会将死亡的结点进行消除，即改变了死亡结点的前驱和后继，因此我们每次对上一轮被消灭的怪物相邻的怪物进行处理即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const LL N = 5e5;
int n, a[N], d[N], killed[N];
int l[N], r[N];
void Solve() {
queue<int> q1, q2, q3;
int len = 0;
for (int i = 1; i <= n; i++)
q1.push(i);
for (int i = 1; i <= n; i++) {
int ans = 0;
while (!q1.empty()) {
int x = q1.front();
q1.pop();
if (killed[x] || x <= 0 || x > n)
continue;
if (d[x] < a[l[x]] + a[r[x]]) {
if (!killed[x]) ++ans, killed[x] = 1;
q2.push(x);
}
}
cout << ans << " ";
len++;
if (ans == 0)
break;
while (!q2.empty()) {
int x = q2.front();
q2.pop();
q3.push(x);
r[l[x]] = r[x];
l[r[x]] = l[x];
}
while (!q3.empty()) {
int x = q3.front();
q3.pop();
q1.push(l[x]), q1.push(r[x]);
}
}
for (int i = len + 1; i <= n; i++)
cout << "0 ";
cout << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
a[0] = a[n + 1] = 0;
d[0] = d[n + 1] = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
killed[i] = 0;
l[i] = i - 1, r[i] = i + 1;
}
for (int i = 1; i <= n; i++)
cin >> d[i];
Solve();
}
return 0;
}
E.Increasing Subsequences(构造)
题意：
数组 a a a的递增子序列是指在不改变其余元素顺序的情况下，通过移除某些元素而得到的序列，并且其余元素是严格递增的（即 a b 1 < a b 2 < ⋯ < a b k a_{b_1} \lt a_{b_2} \lt \dots \lt a_{b_k} ab1<ab2<⋯<abk和 b 1 < b 2 < ⋯ < b k b_1 \lt b_2 \lt \dots \lt b_k b1<b2<⋯<bk）。注意，空子序列也是递增的。
给你一个正整数 X X X。找出一个长度最多 200 200 200的整数数组，使得它恰好有 X X X个递增的子序列，若没有这样的数组，输出 − 1 -1 −1。如果有多个答案，输出其中任何一个。
如果两个子序列由相同的元素组成，但对应数组中的不同位置，则认为它们是不同的（例如，数组 [ 2 , 2 ] [2,2] [2,2]有两个不同的子序列等于 [ 2 ] [2] [2]）。
分析：
考虑从大往小地向序列中加数。为了最小化所需数量至少要有一个长度为 ⌊ log 2 X ⌋ ⌊\log2X⌋ ⌊log2X⌋的递增数列，考虑能否复用这个递增数列中的某些元素来凑出其他 2 2 2的幂出来。
假设当前序列的答案为 k k k，若在当前已有数组的右边加一个最大值，或者加一个比之前所有数都小的数在最左边，那么新生成的序列的答案就为 2 k 2k 2k，加一个比之前所有数都小的数在右边的话新生成的序列的答案就为 k + 1 k+1 k+1。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const LL N = 5e5;
LL t, X;
int main() {
cin >> t;
while (t--) {
cin >> X;
LL high;
for (LL i = 61; i >= 0; --i) {
if ((X >> i) & 1LL) {
high = i;
break;
}
}
deque<int> ans;
ans.push_back(0);
LL lst = 0;
for (LL i = high - 1; i >= 1; --i) {
if ((X >> i) & 1LL) {
ans.push_back(--lst);
ans.push_front(--lst);
} else
ans.push_front(--lst);
}
if (X & 1LL)
ans.push_back(--lst);;
cout << ans.size() << endl;
for (auto x: ans) {
cout << x << " ";
}
cout << endl;
}
return 0;
}
F.Replace on Segment(区间DP)
题意：
给你一个数组 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an，其中每个元素都是从 1 1 1到 x x x的整数。
你可以多次对它进行下面的操作：
- 选择三个整数 l l l、 r r r和 k k k，使得 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n、 1 ≤ k ≤ x 1 \le k \le x 1≤k≤x和一个元素 a i a_i ai，使得 l ≤ i ≤ r l \le i \le r l≤i≤r与 k k k不同。然后，对于每个 i ∈ [ l , r ] i \in [l, r] i∈[l,r]，用 k k k替换 a i a_i ai 。
换句话说，在数组中选择一个子段，并从 1 1 1到 x x x中选择一个未在该子段中出现的整数，然后用该整数替换子段中的每个元素。
为使数组中的所有元素相等。最少需要进行多少次操作？
分析：
设 f l , r , j f_{l,r,j} fl,r,j为使区间 [ l , r ] [l,r] [l,r]元素都为 j j j的最小操作数，设数组 g l , r , j g_{l,r,j} gl,r,j表示在区间 [ l , r ] [l,r] [l,r]中没出现过元素 j j j的方案数。
考虑 f f f数组转移。第一种是直接从 g g g转移到 f f f，即对没出现过 j j j的区间 [ l , r ] [l,r] [l,r]直接耗费 1 1 1全部变成 j j j。即： f l , r , j = g l , r , j + 1 f_{l,r,j}=g_{l,r,j}+1 fl,r,j=gl,r,j+1。第二种是区间合并，需要枚举中转点 m i d mid mid，此时 f l , r , j = f l , m i d , j + f m i d + 1 , r , j f_{l,r,j}=f_{l,mid,j}+f_{mid+1,r,j} fl,r,j=fl,mid,j+fmid+1,r,j。
考虑
g
g
g数组转移。第一种是从
g
g
g转移，
g
g
g数组需要变成没有出现过数
z
z
z的最小方案数，即
g
l
,
r
,
k
=
g
l
,
r
,
j
+
1
g_{l,r,k}=g_{l,r,j}+1
gl,r,k=gl,r,j+1。
第二种仍为区间合并，枚举中转点即可，即
g
l
,
r
,
j
=
g
l
,
m
i
d
,
j
+
g
m
i
d
+
1
,
r
,
j
g_{l,r,j}=g_{l,mid,j}+g_{mid+1,r,j}
gl,r,j=gl,mid,j+gmid+1,r,j。
那么，最后的答案即为 m i n ( f 1 , n , 1 , f 1 , n , 2 , . . . , f 1 , n , x ) min(f_{1, n, 1}, f_{1, n, 2}, ..., f_{1, n, x}) min(f1,n,1,f1,n,2,...,f1,n,x)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const LL N = 155;
int n, x, a[N], f[N][N][N], g[N][N][N], tmp[N][N][N];
void solve() {
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
for (int j = 1; j <= x; j++) {
if (j != a[i]) {
g[i][i][j] = 0;
f[i][i][j] = 1;
}
}
g[i][i][a[i]] = 1;
f[i][i][a[i]] = 0;
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int j = 1; j <= x; j++) {
for (int mid = l; mid < r; mid++) {
f[l][r][j] = min(f[l][r][j], f[l][mid][j] + f[mid + 1][r][j]);
tmp[l][r][j] = min(tmp[l][r][j], g[l][mid][j] + g[mid + 1][r][j]);
}
f[l][r][j] = min(f[l][r][j], tmp[l][r][j] + 1);
for (int k = 1; k <= x; k++) {
if (k == j) {
continue;
}
g[l][r][k] = min(g[l][r][k], tmp[l][r][j] + 1);
}
}
for (int j = 1; j <= x; j++) {
g[l][r][j] = min(g[l][r][j], tmp[l][r][j]);
}
}
}
int ans = n;
for (int i = 1; i <= x; i++) {
ans = min(ans, f[1][n][i]);
}
cout << ans << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
memset(f, 0x3f, sizeof(f));
memset(g, 0x3f, sizeof(g));
memset(tmp, 0x3f, sizeof(tmp));
solve();
}
return 0;
}
学习交流
以下为学习交流QQ群，群号： 546235402，每周题解完成后都会转发到群中，大家可以加群一起交流做题思路，分享做题技巧，欢迎大家的加入。
![[框架系列]-[通用lock框架]集成及具体配置使用](https://img-blog.csdnimg.cn/direct/6e2bb3fe43294480b8cefbcba10211a8.png)
