从 \(1\) 到 \(9\) 的序列中删除一些数(至少保留两位),使得结果为质数。可以发现 \(13\) 和 \(31\) 都是质数,所以判断 \(1\) 和 \(3\) 的先后顺序,然后输出即可。
1 2 3 4 5 6 7 8 9 10 11 12 13
| public static void solve() { char[] s = io.next().toCharArray(); int n = s.length; for (int i = 0; i < n; i++) { if (s[i] == '1') { io.println(13); return; } else if(s[i] == '3') { io.println(31); return; } } }
|
比赛时我是从左往右遍历记录不相等的数量,如果有不相等的,那么就需要一个 \(0\),否则遇到 \(1\) 就输出 YES。和正解的思路是一样的,就是麻烦一点。正解是有相同的 \(01\) 出现时就输出 YES。
1 2 3 4 5 6 7 8 9 10 11 12
| public static void solve() { char[] a = io.next().toCharArray(); char[] b = io.next().toCharArray(); int n = a.length; for (int i = 0; i < n - 1; i++) { if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') { io.println("YES"); return; } } io.println("NO"); }
|
比较简单的写法就是用一个标记数组做记录,递增会向左传递,递减会向右传递,然后判断是否冲突即可。更进一步观察,可以发现只需要记录最大的递增位置,和最小的递减位置。
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
| public static void solve() { char[] s = io.next().toCharArray(); int n = s.length; boolean ok = true; int pos = -1, neg = n, cur = -1; for (char c : s) { if (c == '+') { cur++; } else if (c == '-') { if (cur-- == neg) { neg = n; } pos = Math.min(pos, cur); } else if (c == '0') { if (cur == pos || cur <= 0) { ok = false; break; } neg = Math.min(neg, cur); } else { if (neg <= cur) { ok = false; break; } pos = cur; } } io.println(ok ? "YES" : "NO"); }
|
没想到啊。枚举负数前缀的长度:在负数前缀中,如果 \(a[i]<=a[i+1]\),就需要操作一次;在正数后缀中,如果 \(a[i]>=a[i+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(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = io.nextInt(); } int cnt = 0; for (int i = 0; i < n - 1; i++) { if (a[i] >= a[i + 1]) { cnt++; } } int ans = cnt; for (int i = 1; i < n; i++) { if (a[i - 1] >= a[i]) cnt--; ans = Math.min(ans, cnt + 1); if (a[i - 1] <= a[i]) cnt++; } io.println(ans); }
|