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 Weaver_zhu. 02:02 (+4)

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 02:18 (+3)

题意：$n\times n$的矩阵，初始全为$0$，每次可以翻转一行或者一列，询问能不能有恰好$k$个$1$。

题解：显然一行翻转两次是没有意义的，我们只需要知道有多少行和列被反转就能知道有多少$1$。

于是我们枚举翻转行的次数，直接算出列能够在整数次的翻动下完成恰好$k$个$1$。

因为保证了$1\le n,t\le 10^7$，$1\le n*n*t\le 10^11$ ，我们需要分类做，显然分成$O(n*n*n)$和$O(n*t)$的两类。

一类预处理，一类在线。

Problem H

Solved by Weaver_zhu. 00:05 (+)

Problem I

Unsolved. (-11)

Problem J

Unsolved.