A. Not Too Hard
模拟。
Code
B. 11/11
模拟。
Code
C. Consecutive
Description
给你一个字符串 \(S\),有 \(Q\) 次询问,每次输入 \(l, r\),求:\([S_l,S_r]\) 区间中有多少个相邻的字符是相等的。
Solution
循环一遍字符串,看看 \(s_i\) 是否等于 \(s_{i+1}\),如果等于,记录前缀和数组 \(pre\),\(pre_i = pre_{i-1} + 1\),否则 \(pre_i = pre_{i-1}\)。
每次询问的时候只需要输出 \(pre_{r - 1} - pre_{l - 1}\) 即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, t, l, r, len, c[N];
char s[N];
inline void solve() {
scanf("%d%d", &l, &r);
printf("%d\n", c[r - 1] - c[l - 1]);
}
signed main() {
scanf("%d%d%s", &n, &t, s + 1);
for (int i = 1; i <= n; i++) c[i] = c[i - 1] + (s[i] == s[i + 1]);
while (t--) solve();
return 0;
}
D. Take ABC
Description
给定一个字符串 \(S\),每次会将字符串 \(S\) 中的一个子串 \(\texttt{ABC}\) 删除,进行若干次操作之后,输出字符串 \(S\)。
Solution
我们维护两个数组 \(nxt,lst\),分别表示每个字符的后面和前面字符的下标,类似于链表的思想。
维护变量 \(z\) 表示当前的下标,当 z != n + 1
的时候进行循环。
每次维护变量 \(t2,t3\) 分别赋值为 nxt[z]
和 nxt[nxt[z]]
,表示下标 \(z\) 的下一个字符的下标和下一个字符的下一个字符的下标。
如果这三个下标分别对应的字符正好为 \(\texttt{ABC}\),则将 lst[nxt[t3]]
的值更改为 lst[z]
,nxt[lst[z]]
的值更改为 nxt[t3]
,表示删除了当前子串。并且将 \(z\) 指向 lst[z]
。
每次循环时 z = nxt[z]
即可。
时间复杂度近似于 \(O(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int nxt[N], lst[N], v[N], n;
char s[N];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
nxt[0] = 1;
lst[n + 1] = n;
for (int i = 1; i <= n; i++)
nxt[i] = i + 1, lst[i] = i - 1, v[i] = s[i] - 'A' + 1; // 将 nxt 数组和 lst 数组赋初始值,并且 v 数组记录将字符转换为数字的结果,方便判断
int z = 1, t2, t3;
while (z != n + 1) {
t2 = nxt[z];
t3 = nxt[t2];
if (t2 == n + 1 || t3 == n + 1) break; // 子串不存在,越界了
if (v[z] == 1 && v[t2] == 2 && v[t3] == 3) { // 找到子串 "ABC"
lst[nxt[t3]] = lst[z];
nxt[lst[z]] = nxt[t3];
// 如果下标存在,就指向前一个字符
if (z) z = lst[z];
if (z) z = lst[z];
if (z) z = lst[z];
}
z = nxt[z];
}
// 打印结果
z = nxt[0];
while (z != n + 1)
printf("%c", 'A' - 1 + v[z]), z = nxt[z];
return 0;
}
E. Modulo MST
Description
给你一个无向图,求:生成树中最小的路径,最小路径的定义为路径上的每条边权值之和 \(\bmod \ K\) 的结果。
Solution
这道题不能用最小生成树的思想来做,因为加了一个取模的条件,所以不能贪心地取最小的路径。
所以看到数据范围 \(1 \le N \le 8,1 \le M \le \dfrac{N(N-1)}{2}\),很明显可以爆搜。
如果遍历每条边,\(M\) 最大为 \(28\),最多有 \(C_{28}^{8}\) 种可能性,大概为 \(10 ^ 6\) 左右,总的时间复杂度为 \(O(C_{28}^{8} \times \log n)\),不会超时。
但是要注意剪枝,可以使用按秩合并的并查集来做,注意不要路径压缩,这样的话就无法在搜索时回溯。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20;
int n, m, k, fa[N], si[N];
int x[N << 1], y[N << 1], len[N << 1];
int find(int x) {
return x == fa[x] ? x : find(fa[x]);
}
int dfs(int i, int cnt, int sum) {
if (i == m + 1) {
if (cnt == n - 1) return sum;
return 1e18;
}
int rx = find(x[i]), ry = find(y[i]);
if (rx == ry) return dfs(i + 1, cnt, sum);
if (si[rx] > si[ry]) swap(rx, ry);
fa[rx] = ry;
si[rx] += si[ry];
int ans = dfs(i + 1, cnt + 1, (sum + len[i]) % k);
fa[rx] = rx;
si[rx] -= si[ry];
ans = min(ans, dfs(i + 1, cnt, sum));
return ans;
}
signed main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) fa[i] = i, si[i] = 1;
for (int i = 1; i <= m; i++) cin >> x[i] >> y[i] >> len[i];
cout << dfs(1, 0, 0);
return 0;
}
- 328 Beginner AtCoder Contest ABCbeginner atcoder contest 328 328 beginner atcoder contest beginner atcoder contest abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332