模拟,注意最后答案要减一。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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 b = 1; for (int i = 0; i < n; i++) { if (b == a[i]) b += 2; else b += 1; } io.println(b - 1); }
|
比赛时写复杂了,就是枚举不选哪个数,使用位运算会很简单。
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();
long xor = 0L; long[] s = new long[n]; for (int i = 0; i < n; i++) { int k = io.nextInt(); for (int j = 0; j < k; j++) { s[i] |= 1L << io.nextInt(); } xor |= s[i]; }
int ans = 0; for (int i = 1; i <= 50; i++) { if ((xor >> i & 1) != 1) continue; long res = 0L; for (int j = 0; j < n; j++) { if ((s[j] >> i & 1) != 1) { res |= s[j]; } } ans = Math.max(ans, Long.bitCount(res)); } io.println(ans); }
|
思维题,没想出来。不管前两张牌如何操作,都必定可以拿到之后的所有正数牌,然后对前两张牌分类讨论即可。
1 2 3 4 5 6 7 8 9 10 11 12 13
| public static void solve() { int n = io.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = io.nextInt(); } long ans = 0L; for (int i = 2; i < n; i++) { ans += Math.max(0, a[i]); } ans += Math.max(0, a[0] + Math.max(0, n > 1 ? a[1] : 0)); io.println(ans); }
|
很典的换根 DP,因为第三题花费太长时间,导致差几分钟 AC。只要相邻的两个节点值不相同,它们就需要做一次操作。先以一个节点为根做 DFS,并记录所有节点的子树大小,和以该节点为根的成本。然后再做一次 DFS,换根计算代价的差值。(比赛时犯蠢,在换根的过程中打印答案,但是遍历不能保证从 \(1\) 到 \(n\) 的顺序,所以是错的)
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
| private static long[] ans; private static int[] value, sz; private static List<Integer>[] g;
public static void solve() { int n = io.nextInt(); value = new int[n]; for (int i = 0; i < n; i++) { value[i] = io.nextInt(); } g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int i = 0; i < n - 1; i++) { int u = io.nextInt() - 1, v = io.nextInt() - 1; g[u].add(v); g[v].add(u); } sz = new int[n]; ans = new long[n]; dfs1(0, -1); dfs2(0, -1); for (int i = 0; i < n; i++) { io.print(ans[i] + " "); } io.println(); }
private static void dfs1(int x, int fa) { sz[x] = 1; for (int y : g[x]) { if (y == fa) continue; dfs1(y, x); sz[x] += sz[y]; ans[0] += (long) sz[y] * (value[x] ^ value[y]); } }
private static void dfs2(int x, int fa) { for (int y : g[x]) { if (y == fa) continue; ans[y] = ans[x] + (long) (sz[0] - sz[y] - sz[y]) * (value[x] ^ value[y]); dfs2(y, x); } }
|