如果伤心的学生有 \(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); }