挺简单的一道题，偶数长度的数组操作两次就可以，如果是奇数长度，则额外操作两次。写的时候，把 \(n\) 错写成 \(n-1\)，找 BUG 花了一倍的时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
}
if (n % 2 == 0) {
io.println(2);
io.println(1 + " " + n);
io.println(1 + " " + n);
return;
}
io.println(4);
io.println(1 + " " + (n - 1));
io.println(1 + " " + (n - 1));
io.println((n - 1) + " " + n);
io.println((n - 1) + " " + n);
}
|
\(a\) 和 \(b\) 的最短距离有两种情况，一个是 \(a\) 和 \(b\) 的曼哈顿距离，另一个是 \(a\) 和 \(b\) 经过 \(k\) 的曼哈顿距离，该情况只要求 \(k\) 个点中距离 \(a\) 和距离 \(b\) 最近的距离就行。比赛时遇到个坑点，两个 Long.MAX_VALUE 相加会溢出，所以初始时除以二。
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(), a = io.nextInt(), b = io.nextInt();
long[] x = new long[n], y = new long[n];
for (int i = 0; i < n; i++) {
x[i] = io.nextInt();
y[i] = io.nextInt();
}
long ak = Long.MAX_VALUE / 2, bk = Long.MAX_VALUE / 2;
for (int i = 0; i < k; i++) {
ak = Math.min(ak, Math.abs(x[i] - x[a - 1]) + Math.abs(y[i] - y[a - 1]));
bk = Math.min(bk, Math.abs(x[i] - x[b - 1]) + Math.abs(y[i] - y[b - 1]));
}
long ab = Math.abs(x[b - 1] - x[a - 1]) + Math.abs(y[b - 1] - y[a - 1]);
io.println(Math.min(ab, ak + bk));
}
|
比赛时代码很乱，赛后总是可以优化成比较简单的形式。分类讨论，\(n\) 和 \(m\) 的大小关系，可以直接得出最大美丽值，需要注意特判 \(m=1\) 的情况。然后就是构造，当 \(n\leq m-1\) 时，让一个从 \(0\) 开始的数组循环左移来构造行，这样可以保证得到最大美丽值；当 \(n>m-1\) 时，前 \(m-1\) 行与之前一样构造，之后多余的行只需要和最后一行相同即可（保证不会影响美丽值）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static void solve() {
int n = io.nextInt(), m = io.nextInt();
if (m == 1) {
io.println(0);
} else if (n <= m - 1) {
io.println(n + 1);
} else {
io.println(m);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i < Math.min(n, m - 1)) {
io.print((j + i) % m + " ");
} else {
io.print(j + " ");
}
}
io.println();
}
}
|
找 BUG 花了半个小时，将判断 hi 是否是二的幂写成 hi % 2 != 0，修改为 Long.bitCount(hi) != 1 后通过，也可以写成 (hi & hi - 1) != 0。因为每个人都需要发送和接收糖果，计算每个人和平均糖果数的差值 \(x\)，如果 \(x\) 的二进制位不是由连续的 \(1\) 组成，那么就无解，否则总是有唯一的 \(lo\) 和 \(hi\)（都是二的幂），使得 \(hi-lo=|x|\)。这样可以计算出每个人发送和接收多少糖果，如果最后相互抵消，则存在满足题目要求的交换方案。
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
| public static void solve() {
int n = io.nextInt();
long sum = 0L;
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
sum += a[i];
}
if (sum % n != 0) {
io.println("NO");
return;
}
long avg = sum / n;
int[] cnt = new int[32];
for (int i = 0; i < n; i++) {
if (a[i] == avg) continue;
long x = Math.abs(a[i] - avg);
long lo = x & -x, hi = x + lo;
if (Long.bitCount(hi) != 1) {
io.println("NO");
return;
}
int p = Long.numberOfTrailingZeros(lo);
int q = Long.numberOfTrailingZeros(hi);
if (a[i] > avg) {
cnt[p]--;
cnt[q]++;
} else {
cnt[q]--;
cnt[p]++;
}
}
for (int i = 0; i < 32; i++) {
if (cnt[i] != 0) {
io.println("NO");
return;
}
}
io.println("YES");
}
|
考虑什么人可以不发送或者不接收糖果，必定是持有糖果数与平均糖果数的差值为二的幂的人，它们比原来多出一种选择，就是只执行一次发送或接收。具体操作见代码，有点说不清。最后大概是从高位到低位遍历，如果当前位不满足条件，就将低一位的差值与平均糖果数为二的幂的数分解。
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
| public static void solve() {
int n = io.nextInt();
long sum = 0L;
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
sum += a[i];
}
if (sum % n != 0) {
io.println("NO");
return;
}
long avg = sum / n;
int[] cnt = new int[32];
int[] in = new int[32], out = new int[32];
for (int i = 0; i < n; i++) {
if (a[i] == avg) continue;
long x = Math.abs(a[i] - avg);
if ((x & x - 1) == 0) {
int r = Long.numberOfTrailingZeros(x);
if (a[i] < avg) in[r]++;
else out[r]++;
continue;
}
long lo = x & -x, hi = x + lo;
if ((hi & hi - 1) != 0) {
io.println("NO");
return;
}
int p = Long.numberOfTrailingZeros(lo);
int q = Long.numberOfTrailingZeros(hi);
if (a[i] > avg) {
cnt[p]--;
cnt[q]++;
} else {
cnt[q]--;
cnt[p]++;
}
}
for (int i = 31; i >= 0; i--) {
cnt[i] += out[i] - in[i];
if (i == 0) break;
in[i - 1] -= cnt[i];
out[i - 1] += cnt[i];
if (in[i - 1] < 0 || out[i - 1] < 0) {
io.println("NO");
return;
}
}
io.println(cnt[0] == 0 ? "YES" : "NO");
}
|