2015-2016 6th BSUIR Open Programming Contest. Final

Problem A

Solved by zerol. 00:22 (+)

题意：问有多少个小于等于给定的数满足每一位上的数大于等于一个数字。

题解：数位 DP 签到。

Problem B

Unsolved.

Problem C

Solved by zerol. 01:17 (+)

题意：数列的前两项是 1, 2，后面每一项都是与前一项不互素且在之前的数列中未出现过的最小数字。

题解：对于每一个可能在数列中出现的质因数维护可用的最小倍数。预处理数列中的可能出现的每个数字的所有质因子（只需要记录它的一个质因子即可，决不要一个个塞进 vector），求出前一个数的每个质因子对应的最小倍数的最小值。

Problem D

Unsolved.

Problem E

Solved by ultmaster. 00:44 (+)

题意：现在规定一种选举的规则，如果 $n$ 个人能等分成 $k$ 组，那么这 $k$ 组可以递归的等分，并各自选举出一个代表，这些代表再投票，决定当前选取的结果。现在要黑幕划分，使得用尽可能少的实际支持数赢得选举。

题解：枚举因数暴搜一下就好了。要记忆化。

Problem F

Unsolved.

Problem G

Solved by kblack. 02:00 (+)

题意：$N \times N$ 个学生，概率考试，随机反转行列，询问某个数量的学生及格是否有可能。

题解：想错了一万个地方。$n(a+b) - 2ab = k$，化简 $(n-2a)(n-2b) = n^2-2k$，数据范围傻逼得很，n 小的 $n^2$ 瞎搞，n 大 得 $nt$ 瞎搞。

Problem H

Solved by ultmaster. 00:04 (+)

哈！我也能抢到签到！

Problem I

Solved by ???. 04:09 (+15)

题意：有两个待填的 $n$ 位数，共有 $2n$ 个空位。第一个人叫数字，第二个人填。第一个人想要第一个减第二个数的差尽可能大，第二个人想要尽可能小。求在最优策略下的交互。

题解：

• $n=1$ 的情况第一个人给的数，一定是一个 5 一个 9，或者一个 4 一个 0。
• 如果是第一个人，先叫一个 5，然后第二个人如果填在第二个数最高位，就给他一个 9 让他填在第一个数的最高位。否则叫一个 5 让他填在第一个数的相应位置，然后转化成 $n-1$ 的子问题。
• 如果是第二个人，那么只要给出一种序列即可。当然第一个人的第一个数是有主动权的，起码会有 5 开头 9 结尾，和 4 开头 0 结尾两种情况。如果是 5 开头的，就填在第二个数的末位，然后会再给一个 5，填在第一个数的末位，就转化成 $n-1$ 的子问题；给 4 同理，不过先填在第一个数的末位。

ultmaster: 我写了个能输出决策树的暴力，据说发现了一万个遗漏的情况。

zerol: 这一道题，我背了好几个大锅。

kblack: 大家一起见鬼，呲牙.jpg

Problem J

Unsolved.