

硬币


由于硬币是连续的,所以贪心成立。
直接从最大面额的开始支付,直到商品剩余金额小于最大面额,然后用当前不大于商品剩余金额的最大面额开始支付,直到付清。
由于硬币的面额是从 1 开始的,所以一定存在终点。
这与使用现行人民币付款一样,贪心成立。即,10 元、20 元、100 元付款,要求面额最小,一定是先从 100 元的开始支付。
只有在一种情况下,贪心不成立,需要动态规划,那就是硬币的面额是形如 10 元、6 元、1 元,购买 14 元的商品,如果先从 10 元的支付,就剩下 4 元,必须用 4 个 1 元,总共花了 5 个硬币,而如果是 6 + 6 + 1 + 1,就只需要 4 个硬币,因此贪心不成立,只能动态规划。
本题由于硬币从 1 开始,且连续,因此直接贪心。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); if (m < n) { System.out.println(1); } else { int ans = 0; int x = n; while (m != 0) { int num = m / x; ans += num; m = m - num * x; while (x > m) x--; } System.out.println(ans); } in.close(); } }
奇妙的数列


草稿纸上把数列一写,计算差分 f[x]
表示从第 1 个数到第 x 个数的累加,找到规律。
于是,给定区间求区间和,只需要计算差分 $f[R] – f[L]$ 即可。
由于是有规律的,所以直接用公式求,在 $O(1)$ 的时间复杂度得到答案。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for (int i = 0; i < n; i++) { int l = in.nextInt() - 1; int r = in.nextInt(); int L = (l % 2 == 0 ? 1 : -1) * ((l + 1) / 2); int R = (r % 2 == 0 ? 1 : -1) * ((r + 1) / 2); System.out.println(R - L); } in.close(); } }
石头剪刀布

想要得到 $s$ 分,就必须赢 $s$ 次,在 $n$ 张卡牌中找到 $s$ 张卡片,有 $C_n^s$ 种可能。
对于找到的这 $s$ 张牌,小Q有且只有一种出牌的方式能得分。
对于剩下的 $n – s$ 张牌,小Q不能赢,那就可以有两种出牌的方式,平局或者输掉,即 $2^{n-s}$ 种可能。
因此,最后的答案就是 $C_n^s \times 2^{n-s}$ 种排列。
答案对 $1E9+7$ 取余数。
事实上题目给出的第 2 行的每张卡牌的信息是多余的,没有用。
由于计算大组合数,所以要考虑计算的效率,以及不能溢出,这里用了 Lucas 定理,其中函数 C(n, m, p)
和 lucas(n, m, p)
表示 $C_n^m$ 对 $p$ 取余后的余数,powMod(n, k, p)
表示 $n^k$ 对于 $p$ 取余后的余数。
有一个小坑,不注意只能通过 80% 的数据——题目没有保证 $s$ 小于 $n$,如果不处理就会死循环。
由于 $n$ 张牌不可能得到大于 $n$ 分,所以一旦出现 $s > n$,就输出 0。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int s = in.nextInt(); final int p = (int) (1e9 + 7); if (s > n) System.out.println(0); else System.out.println(lucas(n, s, p) * powMod(2, n - s, p) % p); in.close(); } static long powMod(long n, long k, long p) { long ans = 1; while (k != 0) { if (k % 2 == 1) ans = (ans * n) % p; n = (n * n) % p; k >>= 1; } return ans; } static long C(long n, long m, long p) { if (m == 0) return 1; if (m > n - m) m = n - m; long up = 1, down = 1; for (int i = 1; i <= m; i++) { up = (up * (n - i + 1)) % p; down = (down * i) % p; } return up * powMod(down, p - 2, p) % p; } static long lucas(long n, long m, long p) { if (m == 0) return 1; return C(n % p, m % p, p) * lucas(n / p, m / p, p); } }
气球游戏


这道题和“洛谷”上面的 1638 逛画展 这题很像。
滑动窗口, 或者说,双指针。
首先确定初始的窗口大小不可能小于 $m$,然后右指针向右移动,直到窗口中包含了所有的颜色气球至少各一个。
之后左指针尝试移动,左指针移动的条件是,当移除最左气球的时候,窗口中仍然保有该颜色气球至少一个,也就是,左指针指向的气球颜色大于 1,左指针移动。
左指针移动的动作是 while
而不是 if
,即,如果左指针移动以后指向的那个气球的颜色仍大于 1(不管是刚才那个颜色还是新的颜色)就还是继续移动,如果还是大于 1 就继续移动。
直到左指针移不动了,右指针移动。
窗口滑动的终点是右指针到达尽头。
在整个过程中记录窗口长短的最小值。
需要维护的信息是一个长度为 m 的数组,记录窗口中每个颜色气球有多少个。
在任何条件下,包括初始窗口的确定,如果长度撑满整个数组(右指针到底)了都没能遍历所有颜色气球(即长度为 m 的那个数组中有任何一个元素为 0),输出 -1。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[] q = new int[n]; int[] count = new int[m + 1]; for (int i = 0; i < n; i++) { q[i] = in.nextInt(); } int l = 0; int r = m - 1; for (int i = l; i <= r; i++) { count[q[i]]++; } int min = 0; while (!all(count, m)) { r++; if (r == n) { min = -1; break; } count[q[r]]++; } if (min != -1) { min = r - l + 1; } while (min != -1) { while (count[q[l]] > 1) { count[q[l]]--; l++; } min = Math.min(min, r - l + 1); r++; if (r == n) break; count[q[r]]++; } System.out.println(min); in.close(); } private static boolean all(int[] count, int m) { for (int i = 1; i <= m; i++) { if (count[i] == 0) { return false; } } return true; } }
彩色楼房

这题不会。
感觉是动态规划。
不过后来时间也来不及了,而且毫无思路,就直接放弃了。
用之前那个组合数的模板,猜了一个 $C_n^L$ 骗分骗了 5% 的测试数据,也好。
后来问了 zerol,他说也不会,感觉是 DP,但是没有思路,不会。并且 zerol 指出,为什么猜 $C(n, L)$ 呢,要猜也猜 $ n! $ 之类的。
不过可以肯定的是,这一题的第 2 行,是真的有用的了。
