2015-2016 6th BSUIR Open Programming Contest Final

Problem A

Solved by Weaver_zhu. 00:32 (+)

数位dp基础题

Unsolved.

Solved by Xiejiadong && Kilo_5723. 01:02 (+1)

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

题解：显然，数列中的每一项都是一个质数的倍数，我们用所有的质数来维护一个队列，表示当前质数所到的最小倍数。

对于第$n$项，我们只需要对于$n-1$的质因数，然后在所有的队列里面找一个没有出现过的最小的数作为当前项。

显然一个数的质因数不会超过$8$个，时间能保证。

预处理的时候，不要用 vector ，常数太大，注意内存，有点卡。

Unsolved.

Solved by Weaver_zhu. 02:02 (+4)

题意：$n$个人投票，可以组成选区，每个同级选区人数相同，占绝对多数才算赢得选区。问最优指定选区的情况下最少需要多少人确定会投给你才能赢。题解：捉鬼现场，和队友双线程自闭。记忆化搜索，枚举因数得出每个分选取的方案往下递归。

Unsolved.

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)$的两类。

一类预处理，一类在线。

Solved by Weaver_zhu. 00:05 (+)

趁队友还没打开题面先抢个签到

Unsolved. (-11)

Unsolved.