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

From EOJ Wiki
Revision as of 12:54, 29 March 2019 by Xiejiadong (talk | contribs) (→‎Problem I)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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$,然后利用哥德巴赫猜想,找到剩下的两个质数即可。