只要存在三个连续的空格，就可以执行两次操作一，再多次执行操作二，来装满所有空格。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void solve() {
int n = io.nextInt();
String s = io.next();
String[] arr = s.split("#");
int ans = 0;
for (String t : arr) {
int m = t.length();
if (m >= 3) {
io.println(2);
return;
}
ans += m;
}
io.println(ans);
}
|
注意题目说的是剩下一种类型的数字，而不是一个数字。如果剩下数字 \(1\)，那么首先将 \(2\) 和 \(3\) 抵消，如果 \(2\) 多于 \(3\)，那么多出的数量如果是偶数，就可以将该数量的一半执行操作，再做一次抵消，最后就只剩下 \(1\)；反之亦然。
1
2
3
4
5
6
7
8
9
10
11
12
| public static void solve() {
int a = io.nextInt(), b = io.nextInt(), c = io.nextInt();
if (Math.abs(b - c) % 2 == 0) io.print(1);
else io.print(0);
io.print(" ");
if (Math.abs(a - c) % 2 == 0) io.print(1);
else io.print(0);
io.print(" ");
if (Math.abs(a - b) % 2 == 0) io.print(1);
else io.print(0);
io.println();
}
|
做一次后序遍历即可。题目说的是选择任意字母替换，而不是选择其他节点上的字母替换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public static void solve() {
int n = io.nextInt();
String s = io.next();
int[][] g = new int[n][];
for (int i = 0; i < n; i++) {
int l = io.nextInt() - 1, r = io.nextInt() - 1;
g[i] = new int[]{l, r};
}
io.println(dfs(0, g, s));
}
private static int dfs(int x, int[][] g, String s) {
if (g[x][0] == -1 && g[x][1] == -1) {
return 0;
}
int res = Integer.MAX_VALUE;
if (g[x][0] != -1) {
res = Math.min(res, dfs(g[x][0],g, s) + (s.charAt(x) != 'L' ? 1 : 0));
}
if (g[x][1] != -1) {
res = Math.min(res, dfs(g[x][1],g, s) + (s.charAt(x) != 'R' ? 1 : 0));
}
return res;
}
|
\(f(a,b,c)\) 表示 \(a,b,c\) 中最小的两个数的 \(\gcd\)，而我们要求出给定数组的所有不同下标构成的三元组的 \(f\) 之和。暴力的想法是枚举中间值，然后计算以该值为中心构成的三元组的 \(\gcd\) 之和，时间复杂度为 \(O(n^{2})\)。正确的做法：由于数据范围比较小，我们可以首先计算出 \([1,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
| private static final int N = 100000;
private static final List<Integer>[] aux;
static {
aux = new List[N + 1];
Arrays.setAll(aux, k -> new ArrayList<>());
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j += i) {
aux[j].add(i);
}
}
}
public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
Arrays.sort(a);
int[] c = new int[N + 1];
long[] f = new long[N + 1];
for (int i = 0; i < n; i++) {
for (int x : aux[a[i]]) {
f[x] += (long) c[x] * (n - i - 1);
c[x]++;
}
}
long ans = 0L;
for (int i = N; i >= 1; i--) {
for (int j = i + i; j <= N; j += i) {
f[i] -= f[j];
}
ans += f[i] * i;
}
io.println(ans);
}
|
似乎是和强连通分量相关的题目，有空可以补一下。