每个工具对答案的贡献为 \(\min(a-1,x_{i})\),并且答案可能会爆 \(long\),状态好差,WA 两次。
1 2 3 4 5 6 7 8
| public static void solve() { int a = io.nextInt(), b = io.nextInt(), n = io.nextInt(); long ans = b; for (int i = 0; i < n; i++) { ans += Math.min(a - 1, io.nextInt()); } io.println(ans); }
|
数学题。当 \(k\bmod 2=1\) 时,先手会得到 \(\min(0,maxb-mina)\);反之,后手此时必然有最小价值的苹果 \(\min(mina,minb)\),而先手此时会有最大价值的苹果 \(\max(maxa,maxb)\),做一次交换即可。
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
| public static void solve() { int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
long suma = 0L; int mina = Integer.MAX_VALUE, maxa = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int x = io.nextInt(); suma += x; mina = Math.min(mina, x); maxa = Math.max(maxa, x); }
int minb = Integer.MAX_VALUE, maxb = Integer.MIN_VALUE; for (int i = 0; i < m; i++) { int x = io.nextInt(); minb = Math.min(minb, x); maxb = Math.max(maxb, x); }
if (k % 2 == 1) { io.println(suma + Math.max(0, maxb - mina)); } else { io.println(suma + Math.max(0, maxb - mina) - Math.max(maxa, maxb) + Math.min(mina, minb)); } }
|
完了,官方解法看不懂,下面是我的解法,就是一直乘二求余,贪心的拆分。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| public static void solve() { int n = io.nextInt(), m = io.nextInt();
int x = n % m, y = m / gcd(n, m); if ((y & (y - 1)) != 0) { io.println(-1); return; }
long ans = 0L; while (x != 0) { ans += x; x *= 2; x %= m; } io.println(ans); }
private static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
|
下面是官解,大概懂了。\(\frac{a}{b}\) 表示最终每个人得到的苹果价值的小数部分(可以表示为 \(\sum_{i\in S}\frac{1}{2^{i}}\)),因为 \(b\) 必须是二的幂,所以 \(a\) 中 \(1\) 的个数就表示这个人所需的最小苹果片数(就是集合 \(S\) 中元素的个数),乘以 \(m\) 就表示最后总共的苹果片数,然后减去最开始的 \(n\) 片就是需要进行操作的次数(因为每次操作会增加 \(1\) 片)。(这个题解很详细,提供了另一种视角)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| public static void solve() { int n = io.nextInt(), m = io.nextInt();
n %= m; int x = gcd(n, m), a = n / x, b = m / x; if ((b & (b - 1)) != 0) { io.println(-1); } else { io.println((long) Integer.bitCount(a) * m - n); } }
private static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
|
其实是很简单的动态规划,但就是动不起来啊。定义 \(dp[i]\) 为将 \(MEX\) 变为 \(i\) 需要的最小代价,然后从大到小转移即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| private static final int N = 5001;
public static void solve() { int n = io.nextInt(); int[] cnt = new int[N]; for (int i = 0; i < n; i++) { int x = io.nextInt(); if (x < n) cnt[x]++; }
int mex = 0; while (cnt[mex] > 0) mex++; long[] dp = new long[mex + 1]; Arrays.fill(dp, Long.MAX_VALUE); dp[mex] = 0; for (int i = mex - 1; i >= 0; i--) { for (int j = i + 1; j <= mex; j++) { dp[i] = Math.min(dp[i], dp[j] + (long) (cnt[i] - 1) * j + i); } } io.println(dp[0]); }
|