因为题目保证存在合法的 \(X\) 和 \(Y\)，那么获胜者总是最后一个下棋者，因为如果不是最后一个，那么对局就不会结束。
1
2
3
4
5
| public static void solve() {
int n = io.nextInt();
String s = io.next();
io.println(s.charAt(n - 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
| public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
int k = 2;
int[] b = new int[n];
Arrays.fill(b, 1);
int[] cnt = new int[101];
for (int i = 0; i < n && k <= 3; i++) {
if (++cnt[a[i]] == 2) {
b[i] = k++;
}
}
if (k <= 3) {
io.println(-1);
return;
}
for (int i = 0; i < n; i++) {
io.print(b[i] + " ");
}
io.println();
}
|
如果当前数组是通过移动得到，那么它的最后一个元素必定是由定点元素转移过来，所以我们只需要判断最后一个元素是否在 \([1,n]\) 范围内，然后不断地回滚左移操作，即不断地找到移动之前的最后一个元素位置，并进行判断即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void solve() {
int n = io.nextInt(), k = io.nextInt();
int[] b = new int[n];
for (int i = 0; i < n; i++) {
b[i] = io.nextInt() - 1;
}
int i = n - 1;
while (b[i] != -1 && b[i] < n && --k > 0) {
int j = (i - (b[i] + 1) + n) % n;
b[i] = -1;
i = j;
}
io.println(k == 0 || b[i] == -1 ? "Yes" : "No");
}
|
我们总是可以构造一个数组 \(c\)，使得 \(\operatorname{LIS}(c)=\operatorname{LIS}(a)\)，方法为将数组 \(b\) 中的元素 \(b_{i}\)，插入到数组 \(a\) 中第一个满足 \(a_{j}\leq b_{i}\) 的元素 \(a_{j}\) 之前，操作方式类似归并排序。
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
| public static void solve() {
int n = io.nextInt(), m = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
var b = new Integer[m];
for (int i = 0; i < m; i++) {
b[i] = io.nextInt();
}
Arrays.sort(b, ((e1, e2) -> e2 - e1));
int i = 0, j = 0, k = 0;
int[] ans = new int[n + m];
while (i < n || j < m) {
if (i >= n) {
ans[k++] = b[j++];
} else if (j >= m) {
ans[k++] = a[i++];
} else if (a[i] <= b[j]) {
ans[k++] = b[j++];
} else {
ans[k++] = a[i++];
}
}
for (int x : ans) {
io.print(x + " ");
}
io.println();
}
|