• Home
  • About
    • Ruinan photo

      Ruinan

      Something interesting.

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Recent Project
  • Problem List

2016青岛网络赛

20 Sep 2016

2016 青岛网络赛


    写的很蠢,比赛很简单但是写的不好,感觉队伍还是比赛练少了…没有发挥出原有的水平。


1001

    题目要求不比x小的\[2^a3^b5^c7^d\]这样的数的个数。

    直接打表二分即可。


1002

    这个题读入比较坑,他说读入有1M但是并没有n的范围…其实n会很大,要用字符串存,而且有前导零…

    比赛的时候RE了一次就发现问题了,后来改成了字符串就过了。

    做法是在n比较小的时候直接打表,跟\(\frac{π^2}{6}\)接近了之后就直接输出\(\frac{\pi^2 }{6}\)就行了。


1003

    AC自动机模板题,不过好像空间卡的很死,比赛的时候并没有出这题。


1005

    签到题,判断n的奇偶即可。


1006

    首先判断图的连通性,不联通的图一定是impossible否则用欧拉图的性质进行判断,因为每条边都会被走到,我们记录每个点的边数然后加一除二就能得出每个点被走过的次数了。又因为偶数次其实没有必要,所以我们统计奇数次的值就可以了。

    这个题跑了Rank 1…


1007

    这个题比赛的时候花了不少时间,因为每次应该取代价最小的k个,最开始的想法是用优先队列,但是时间不够,后来发现只要用两个队列模拟就好了。(从一个队列出来的元素求和后插入另外一个队列)

    注意这个题应该首先取到总数-1 能被 k-1 除尽的情况,否则不能直接取前k个。


1011

    这个题就是先跑出最短路,然后在最短路上跑一遍最小割就行了。

    写起来挺方便,不过代码量略大。


其他

    其他的题都没过,以后有时间会补上(也许永远不会补… : P)

    这次比赛还是反应出了队伍不少的问题,缺乏比赛经验,某些方面过于薄弱等等,在以后的集训中还是要多多注意。




ACM2016网络赛 Like Tweet