<原># The 10th Zhejiang Provincial Collegiate Programming Contest

The 10th Zhejiang Provincial Collegiate Programming Contest

2017年02月06日 22:31:40 Tabris_ 阅读数:206


博客爬取于2019-04-18 17:18:01
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54897814

题目连接: http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=347

套题是真TM酸爽。 193 ∗ 47 ∗ 887 ∗ 29

A Applications

英语题 特别复杂的模拟 注意细节 细节 细节 细节 细节 。。。。

B Break Standard Weight

签到题 直接暴力就好了

C Calculate Prime S

理解题意,首先x很明显要求个逆元,因为m不是素数,所以只好用扩展欧几里德求了,
对于S[n] 是很明显的fibonacci数列(S[n]=fib[n+2] ),枚举两个就出来了,别忘了还有空集..

然后就不会了,
最后才知道fibonacci的一个性质

1. g c d ( f i b ( n ) , f i b ( m ) ) = f i b (
g c d ( n , m ) )

证明:可以通过反证法先证fibonacci数列的任意相邻两项一定互素,然后可证 n > m 时 g c d ( f i b ( n
) , f i b ( m ) ) = g c d ( f i b ( n − m ) , f i b
( m ) ) ,递归可求 g c d ( f i b ( n ) , f i b ( m ) ) = g
c d ( f i b ( k ) , f i b ( l ) ) ,最后 k = l ,不然继续递归。 K
是通过展转相减法求出,易证 k = g c d ( n , m ) ,所以 g c d ( f i b ( n )
, f i b ( m ) ) = f i b ( g c d ( 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 p h i ( c ) − 1
如果b与c不互素,则 ( a / b ) % c = ( a % b c ) / b
对于b与c互素和不互素都有 ( a / b ) % c = ( a % b c ) / 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

—————————————————————————————-

最后发现这套题是之前省选训练过的题..

总结:
英语读题水平太菜,
模拟水平太差,
代码能力有待加强

思维不够开阔,胆子不够大,至少暴力的想法是有的 但是却不敢写.
写代码的速度可以放慢些,写快了细节上出错率大.


 上一篇
<原>#  ZOJ 3604 Tunnel Network [Prüfer编码与Cayley公式] 【树】 <原># ZOJ 3604 Tunnel Network [Prüfer编码与Cayley公式] 【树】
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2017-02-07
下一篇 
<原>#  codeforces 763B. Timofey and rectangles [思维]【智商】 <原># codeforces 763B. Timofey and rectangles [思维]【智商】
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2017-02-06
  目录