简单模拟，比赛时打错了一个字母。
1
2
3
4
5
| public static void solve() {
String s = io.next();
Set<String> set = Set.of("ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD");
io.println(set.contains(s) ? "Yes" : "No");
}
|
因为左上角和右下角是中心对称的，所以判断右下角时可以使用形如 i + 8 - x 的下标来简化代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void solve() {
int n = io.nextInt(), m = io.nextInt();
String[] arr = new String[n];
for (int i = 0; i < n; i++) arr[i] = io.next();
for (int i = 0; i + 8 < n; i++) {
for (int j = 0; j + 8 < m; j++) {
boolean ok = true;
for (int x = 0; x < 4; x++) {
for (int y = 0; y < 4; y++) {
if (arr[i + x].charAt(j + y) != (x != 3 && y != 3 ? '#' : '.')) {
ok = false;
}
if (arr[i + 8 - x].charAt(j + 8 - y) != (x != 3 && y != 3 ? '#' : '.')) {
ok = false;
}
}
}
if (ok) io.println((i + 1) + " " + (j + 1));
}
}
}
|
其实第一眼看到感觉是可以二分做的，不过比赛时使用的是两个优先队列模拟解决的，边界想了半天，结果最优解很妙啊。我们要求最小的 \(x\)，使得可能卖 \(x\) 元的卖家数量 \(f(x)\) 大于等于可能花 \(x\) 元买的买家数量 \(g(x)\)。其实我们要求的就是使 \(f(x)-g(x) >= 0\) 时的最小 \(x\)，而 \(f(x) - g(x)\) 是随 \(x\) 非严格递增的，当 \(x = 0\) 时，\(f(x)-g(x)=-M\)，并且答案的取值在 \(A_{1},\dots,A_{N},B_{1}+1,\dots,B_{M}+1\) 中，所以可以直接排序（或者快速选择），然后输出第 \(M\) 个数即为答案。
1
2
3
4
5
6
7
8
9
10
| public static void solve() {
int n = io.nextInt(), m = io.nextInt();
int[] arr = new int[n + m];
for (int i = 0; i < n; i++) arr[i] = io.nextInt();
for (int i = 0; i < m; i++) arr[i + n] = io.nextInt() + 1;
Arrays.sort(arr);
io.println(arr[m - 1]);
}
|
动态规划，不太会做。首先定义状态 \(dp[i][j]\)，表示区间 \([1,i]\) 中左括号比右括号多 \(j\) 个的方案数（也可以定义为其他形式）。然后写状态转移方程，可以画图看下转移方向，每层会分别向左下和右下转移 \(n\) 次，然后就可以写出不用特判边界的转移方程。还可以使用滚动数组优化空间，此处略过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| private static final int MOD = 998244353;
public static void solve() {
String s = io.next();
int n = s.length();
int[][] dp = new int[n + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
char c = s.charAt(i - 1);
for (int j = 0; j < n; j++) {
if (c != ')') dp[i][j + 1] = dp[i - 1][j];
if (c != '(') dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
}
}
io.println(dp[n][0]);
}
|