2015-2016 6th BSUIR Open Programming Contest Final

Problem A

Solved by Weaver_zhu. 00:32 (+)

数位dp基础题

Problem B

Unsolved.

Problem C

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

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

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

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

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

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

Problem D

Unsolved.

Problem E

Solved by Weaver_zhu. 02:02 (+4)

题意：$n$个人投票，可以组成选区，每个同级选区人数相同，占绝对多数才算赢得选区。问最优指定选区的情况下最少需要多少人确定会投给你才能赢。

题解：捉鬼现场，和队友双线程自闭。记忆化搜索，枚举因数得出每个分选取的方案往下递归。

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

Upsolved by Weaver_zhu.

第一眼看成了绝对值最大最小，然后思路再也没有回来。

题意：两个$n$位数，一个人选数字，一个人选择填到被减数或者减数上的一个位置。挑数字的人希望结果最大，挑位置的人希望结果小。让你找出两个人的最优策略。

题解：$n=1$的时候一定是$9-5$或者$4-0$。$n=2,3$暴力（手工）发现答案是$40,400$。猜答案。

为什么答案是$4000...$，$0-4$算小数，其余算大数。第二个人尽量要让减数大，被减数小。而最高位数一定是$9-5,4-0$，因为第一位数的影响总能盖过其余所有的。

考虑填其他位数的情况，让答案大于$40000..$。那么两个人得同时盯紧最高位相差一定是$4$。如果叫大数，那么第二个人应该往下填，否则会发现大数往上填了之后，怎么找都能大于$4000...$。就是之后不停叫4，第二个人保证最高位不失守填了最高位之后一直叫$0$，发现就大于$4000...$了。所以第二个人只能放$5$在下面。第一个人第一个数怎么选数字，如果第一个人叫了$5$以上的数字，那么第二个人填到减数最高位，gg。叫$0,9$也是同理，最高位失守，所以只能叫$5,4$。

考虑$5$，第二个人填了$5$在减数最高位，那么剩下就应该不停叫$9$填满。如果填在非最高位，再叫比$5$大的数最高位就gg了，叫小于$5$的数，这一位gg了。第一个人为了守住$4000..$，只能再叫$5$。第一个人怎么办呢，如果继续填下面，那么下面的空位总会比上面少，继续叫$5$，等最高位填好了之后，第一个人全叫$9$，失守，因此第二个人只能填上面。如果继续叫$5$而不填最高位，那么减数被减数空位削减速度一致，最后还是到$n=1$的情况。这样下来，答案还是$4000..$。

考虑$4$，相似的道理，只不过作为小数要先填到上面。

那么的第二个人的思路也出来了。

Problem J

Unsolved.