2018 China Collegiate Programming Contest Final (CCPC-Final 2018)

Problem A

Solved by Xiejiadong. 00:12 (+1)

温暖的排序签到。

+1 是因为煞笔了。

Problem B

Solved by Kilo_5723. 04:20 (+)

题意：两个势力，一堆骑士，每个骑士加入不同的势力能获得不同的力量。有几对骑士不能加入同一个势力，每个骑士必须加入一个势力，问力量最高的骑士和力量最低的骑士的力量差是多少。

题解：显然，如果不是二分图就无解。然后对于每个联通块加入势力的方式都只有两种，分别求出两种情况下的最高力量和最低力量，最后对整体按最低力量排序，滑动窗口确定最低力量后求得最低的最高力量。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Xiejiadong && Weaver_zhu. 00:33 (+1)

题意：求一个 $n\times m$ 的矩阵里面能选出多少对矩形，满足前一个被后一个包含的关系。

题解：观察一维线段被包含的情况，显然答案为 $\left ( _{n+1}^{4} \right )$，那么二维的情况就是乘起来。

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 03:01 (+1)

题意：在一个平面上有数个整点，每次可以消除一个十字上的点，问最多一次消除多少点，以及这种情况下可能消除点的不同集合的数量。

题解：在消除大于两个点的情况下，消除点的集合数量等于十字中心的数量。在只能消除两个点的情况下，答案为 $C_n^2$。

维护每一行，每一列上的点数，计算最多能消除多少点并统计情况。对于行列交点上有点的情况进行特判。

如果删去这些情况后情况数为 $0$ 则答案 $-1$，再次以类似的方法统计情况数。

Problem J

Unsolved.

Problem K

Solved by Weaver_zhu. 03:53 (+10)

题意：随机在$[10^5, 10^9]$之中选一个$x$，然后选出小于$x$的最大质数$p$，不小于$x$的最小质数$q$，令$n=p \cdot q \;\; flag^{2^{30}+3} \equiv c (mod \; x)$现给定$x,c$求$flag$。

题解：素数还是挺多的，显然我们可以在$\sqrt{x}$附近找出$p,q$，然后$phi(x)$就出来了，然后求$2^{30}+3$关于$phi$的逆元$inv$，求出$c^{inv} \mod x$就是答案。嗯，看起来就这么简单。

心态崩了：求逆元的时候模数大于$10^9$要快速乘，然后快速乘被卡了。场上反复更换找素数的方法以为算法假了。但是组成$x$的两个质因数最大也在$10^9$附近，于是先在$p,q$模数下求出逆元再合回去。测试下来原6s数据现在跑1s。

Problem L

Solved by Xiejiadong. 03:10 (+2)

题意：给出一个数，将其分成六个质数相加的情况。

题解：首先一个数的周围，很容易找到一个质数。我们要找到一个质数，使得比这个数小至少 $20$ 。

然后，如果减去这个质数以后是奇数，则剩下的三位为$2,2,3$；如果是偶数，剩下的三位为$2,2,2$。

这样可以保证最后剩下的是一个偶数，并且$>2$，然后利用哥德巴赫猜想，找到剩下的两个质数即可。