[原创]The 10th Zhejiang Provincial Collegiate Programming Contest
[原创]The 10th Zhejiang Provincial Collegiate Programming Contest
2017-02-06 22:31:40 Tabris_ 阅读数：256
博客爬取于 2020-06-14 22:41:51
以下为正文
版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54897814
题目连接：http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=347
套题是真 TM 酸爽。$19347887*29$
A Applications
英语题 特别复杂的模拟 注意细节 细节 细节 细节 细节 。。。。
B Break Standard Weight
签到题 直接暴力就好了
C Calculate Prime S
理解题意，首先 x 很明显要求个逆元，因为 m 不是素数，所以只好用扩展欧几里德求了，
对于 S[n] 是很明显的 fibonacci 数列(S[n]=fib[n+2] )，枚举两个就出来了，别忘了还有空集..
然后就不会了，
最后才知道 fibonacci 的一个性质
1.gcd(fib(n),fib(m))=fib(gcd(n,m))
证明：可以通过反证法先证 fibonacci 数列的任意相邻两项一定互素，然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m))，递归可求gcd(fib(n),fib(m))=gcd(fib(k),fib(l))，最后k=l，不然继续递归。K是通过展转相减法求出，易证k=gcd(n,m)，所以gcd(fib(n),fib(m))=fib(gcd(n,m))。
所以只有当 gcd(n,m)=1 或 2 时(fib[1]==fib[2]==1) fib[n]与 fib[m]互质
所以若 S[n] 要是一个 PrimeS
则 n+2 必须是一个质数或者 4 ，自己画画就知道为什么 4 是特殊的了
所以构造一个特殊的素数表
P[i] 3 4 5 7 11 13...................
所以第 K 个 PrimeS 就是 fib[P[k]]
还有一个结论：
计算(a/b)\%c 其中 b 能整除 a
如果 b 与 c 互素，则(a/b)\%c=a*b^{phi(c)-1}%c
如果 b 与 c 不互素，则(a/b)\%c=(a\%bc)/b
对于 b 与 c 互素和不互素都有(a/b)\%c=(a\%bc)/b成立
就是枚举出能够整除 x 的 PrimeS 用快速幂求取 PrimeS
最后计算 就好了 注意下可能会爆 int 就好了
D Density of Power Network
明白题意让求的是去掉平行线后，线与节点数的比值就好了
签到题 暴力做
E Egg Painting
不会 还找不到题解...
F Friends
这个题比较 6
确定题意后，直接暴力加边就好了，直到不能在加边为止
G Give Me Your Hand
看题解是个 dp 然而 dp 废。。。。
来日在补
H Hard to Play
签到题 明白题意直接做就好了，
I In 7-bit
阅读题 明白题意 直接处理就好了
J Java Beans
签到题 找环上和最大的长度为 k 的连续区间， 前缀和处理然后枚举即可。
K Kindergarten Election
题面比较有意思，一群幼儿园同学要投票选个老大，（不能选自己），每个人都有一个心仪的老大目标，然后 1 号小朋友要当老大，可以拿糖贿赂其他小朋友来确保自己当老大。问 1 号小朋友最少需要多少个糖果能确保自己当上老大。
枚举加贪心，
枚举 1 号小朋友当上老大时的票数，然后贪心选择贿赂谁，维护下结果的就行了。
题目不难，就是不好想到枚举，想直接进行贪心，然后就会各种 GG
最后发现这套题是之前省选训练过的题..
总结：
英语读题水平太菜，
模拟水平太差，
代码能力有待加强
思维不够开阔，胆子不够大，至少暴力的想法是有的 但是却不敢写。
写代码的速度可以放慢些，写快了细节上出错率大。
