如果伤心的学生有 \(x\) 个，则答案为 \(\lceil \frac{x}{2}\rceil\)。步骤如下：如果至少有两个伤心的学生，则交换他们的椅子；如果只有一个伤心的学生，则让他和任意其他学生交换椅子。
1
2
3
4
5
6
7
8
9
| public static void solve() {
int n = io.nextInt(), cnt = 0;
for (int i = 1; i <= n; i++) {
if (i == io.nextInt()) {
cnt++;
}
}
io.println((cnt + 1) / 2);
}
|
这道题感觉很妙啊，比赛时看到 \(n\) 的范围很大，所以猜了一个结论也没有细想，结果是对的。假设我们已经找到区间 \([l,r]\) 对每个满足 \(l\leq i\leq r\) 的 \(i\)，\(n\bmod i=0\)。然后我们可以将区间 \([l,r]\) 转化为区间 \([1,r-l+1]\)，因为对每个满足 \(1\leq x\leq r-l+1\) 的 \(x\)，在区间 \([l,r]\) 中总是可以找到一个数 \(y\)，使得 \(y\bmod x=0\)，因而也满足 \(n\bmod x=0\)。
为什么总是可以找到呢？因为一个连续的数列，对 \(x\) 取余得到的余数的周期为 \(x\)，所以一个长度为 \(x\) 的区间内，总是可以找到一个数 \(y\)，使得 \(y\bmod x=0\)。
时间复杂度 \(O(\log{(\max n)})\)，具体不知道怎么算的。
1
2
3
4
5
6
7
8
9
| public static void solve() {
long n = io.nextLong();
for (int i = 1; ; i++) {
if (n % i != 0) {
io.println(i - 1);
return;
}
}
}
|
比赛时想到找最大或最小的数和倍增，但是没弄明白。首先，如果所有数都非负或非正，那么只要做前缀或后缀和就可以得到非递减的数组，最多操作 \(19\) 次。此时我们还剩下 \(31-19=12\) 次操作机会，我们考虑如何在 \(12\) 次操作内把数组中的数都变为非负或非正：
- 当最大的正数加最小的负数大于等于零时：如果负数的数量小于等于 \(12\)，那么我们可以在 \(12\) 次操作内把所有负数变为正数；反之，我们可以选择一个负数让它倍增 \(5\) 次，它就会变为最小的负数，并且最大的正数加最小的负数一定小于零，然后我们就可以在 \(7\) 次操作内把所有正数变为负数（因为此时正数的数量小于 \(7\)）。
- 当最大的正数加最小的负数小于等于零时：同理。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| public static void solve() {
int n = io.nextInt();
int[] arr = new int[n];
int minPos = 0, maxPos = 0, neg = 0, pos = 0;
for (int i = 0; i < n; i++) {
arr[i] = io.nextInt();
if (arr[i] < 0) neg++;
if (arr[i] > 0) pos++;
if (arr[i] < arr[minPos]) minPos = i;
if (arr[i] > arr[maxPos]) maxPos = i;
}
List<int[]> ans = new ArrayList<>();
if (arr[minPos] + arr[maxPos] >= 0) {
if (neg <= 12) {
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
ans.add(new int[]{i, maxPos});
}
}
for (int i = 0; i < n - 1; i++) {
ans.add(new int[]{(i + 1), i});
}
} else {
for (int i = 0; i < 5; i++) {
ans.add(new int[]{minPos, minPos});
}
for (int i = 0; i < n; i++) {
if (arr[i] > 0) {
ans.add(new int[]{i, minPos});
}
}
for (int i = n - 2; i >= 0; i--) {
ans.add(new int[]{i, (i + 1)});
}
}
} else {
if (pos <= 12) {
for (int i = 0; i < n; i++) {
if (arr[i] > 0) {
ans.add(new int[]{i, minPos});
}
}
for (int i = n - 2; i >= 0; i--) {
ans.add(new int[]{i, (i + 1)});
}
} else {
for (int i = 0; i < 5; i++) {
ans.add(new int[]{maxPos, maxPos});
}
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
ans.add(new int[]{i, maxPos});
}
}
for (int i = 0; i < n - 1; i++) {
ans.add(new int[]{(i + 1), i});
}
}
}
io.println(ans.size());
ans.forEach(k -> io.println((k[0] + 1) + " " + (k[1] + 1)));
}
|
每种方案都有一个可以到达的最远位置 \(x\)，对于该位置我们能够得到的点数是确定的，即为 \(\sum_{i=0}^{x}a_{i} - x\) 点。所以我们只需要枚举每一个最远位置就能够解决问题，如果使用 DFS 时间复杂度是指数级别的，通过使用状压 DP 可以降低时间复杂度。假设当前枚举到位置 \(i\)，当前的可达位置是 \(dp_{i}\)，那么下一个可达位置就是 \(dp_{i+1}=dp_{i}|(dp_{i}<<a_{i})\)，然后如果当前位置可达，我们计算完答案之后需要将当前位置置为 \(0\)，因为对于下一个位置来说，当前位置已经解锁。如果使用 C++ 实现可以直接使用 \(bitset\)，而使用 Java 实现则需要手动写位图，因为 Java 内置的位图没有移位操作。
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
| public static void solve() {
int n = io.nextInt();
int[] arr = new int[2 * n + 1];
for (int i = 0; i < n; i++) {
arr[i] = io.nextInt();
}
int m = n * 2 / 64 + 1;
long[] dp = new long[m];
long[] dq = new long[m];
dp[0] = 1L;
long sum = 0L, ans = 0L;
for (int i = 0; i < 2 * n; i++) {
sum += arr[i];
int p = arr[i] / 64, q = arr[i] % 64;
for (int j = 0; j < m; j++) {
dq[j] = dp[j];
if (j >= p) {
dq[j] |= dp[j - p] << q;
if (j > p && q > 0) dq[j] |= dp[j - p - 1] >>> (64 - q);
}
}
long[] tmp = dp;
dp = dq;
dq = tmp;
p = i / 64;
q = i % 64;
if (((dp[p] >> q) & 1) == 1) {
dp[p] ^= 1L << q;
ans = Math.max(ans, sum - i);
}
}
io.println(ans);
}
|