2016中国大学生程序设计竞赛 - 网络选拔赛 总结

很高兴这场拿到了杭州赛区的名额,大概 10 月份会去杭州旅游吧。这场题目有两题原题,数据也是很水,所以有些题目没有尝试很可惜。这场比赛并没有很多题数,完全是靠手速和没有罚时才能打到名额,所以手速还是很重要啊。

 

1001 A water problem

真的是一题水题,大数取模,边读入边取模就行。

 

1002 Zhu and 772002

题目大意是给你 n 个数,求选取任意个积为完全平方数有多少种方案。可以从完全平方数的质因子幂次都是偶数下手。我们可以把 2000 以内的质数都预处理出来(大概有 303 个)并将所有的数分解质因数。为了方便起见,我们记 A_{ij} 为第 i 个素数在第 j 个数中有多少次幂。并记 X_j 为第 j 个数是否去到,那么一个方案合理的话就会有对于所有 i 都有 \sum A_{ij}\ *\ X_j\ \equiv\ 0\ (Mod\ 2) 接下来的事情就可以用高斯消元做了。用高斯消元算出自由元的数目 x,对于每一个自由元有两种取法,所以答案就是 2^x-1.

 

1004 Danganronpa

这题数据太水了,我提交了四个错误的版本都过了= =,所以正解我也不知道。

 

1011 Lweb and String

其实就是看这串数列里有多少个不同的字母,按出现顺序替换就是最大解。反正法可证。

发表评论

电子邮件地址不会被公开。 必填项已用*标注