Edu CF Round 137 A & B & C

A. Password
小 M 有一个四位数的密码,每位都是数字 0 - 9,他忘记了密码,但是他记得密码用了两种数字,每种用了 2 个,且记得没用哪些数字(n 个,会从输入给出),求可能的密码的数量。
比如,没用 1,2,4,5,6,8,9,0,那么剩下 3,7,有 3377,3737 ... 等可能。
思路:
简单数学题,看密码可能是怎么样的有两步,第一步是从剩下的 10 - n 个数字中选出两个数字,然后排列这两种共四个数字,可以用公式直接算出来: ,组合数直接递推预处理出来,右边的式子直接手算出来是 6.
B. Permutation Value
给定一个长度为 n 的排列 (1 - n 的排列),现在定义一个排列的值为:它的所有也是排列的连续子序列的个数。一个长为 s 的序列需要包含 1 - s 各一次。比如排列 [2, 1, 3],有连续子序列 [2],[1],[3], [2, 1], [2, 3], [2, 1, 3],其中有: [1], [2,1], [2, 1, 3] 是排列,因此值为 3. 现在给定一个整数,输出一个使得排列的值最小的长度为 n 的排列。
思路:
注意到,如果把 1 放在第一个位置,2 放在最后一个位置,那么显然只有 [1] 这个子序列和 [1, ....., 2] 这个子序列是排列,因为其他任何长度小于 n 的子序列都不会同时包含 1,2。而在任何排列中,[1], 和 长度为 n 的子序列都会是排列,因此 2 是排列的值的下界。因此上述的方案会给出一个最小的值的排列,也就是 [1, ...,...,.., ... ,..., 2]
C. Save the Magazines
小 M 要给大家送报纸,一条街上有 n 个箱子,小 M 在第 i 个箱子塞进 份报纸。现在突然下雨了,有的箱子没盖子,有的箱子有盖子,有盖子的箱子可以保护箱子里的报纸,没盖子的箱子里的报纸会湿透。现在假设小 M 可以在一瞬间进行任意的盖子移动,但是在 i 位置的盖子只能移到 i - 1 位置,且每个盖子只能被移动一次,问小 M 最多能救过来多少报纸?
思路:
从左到右来考虑,如果第一个箱子是被盖着的,那么直接把其中的报纸份数加入答案,并往后考虑。如果一个箱子是没被盖着的,且它下一个箱子也没盖子,那么直接跳过这个箱子。如果当前箱子没盖子,下一个箱子有盖子,考虑这样的一种情况: 01...1,当最前面的箱子把后一个的盖子夺走,有可能下一个箱子也可以再抢它下一个箱子的盖子,容易看出按这种办法可以让 01....1 中任意一个位置为 0,也就是放弃这个箱子。显然要放弃这里面报纸最少的箱子,做法是统计这一段的和与最小值,用和减去最小值就是这一段的最大挽救的报纸份数。通过这种方法线性的扫一遍就求出答案了。