国庆中秋喜相逢邀请赛题解

Posted by yjjr's blog on February 6, 2018

传送门:http://106.14.168.81/contest/8

1.          预估气温

(weather.pas/c/cpp)

O(n)模拟每两天中温差即可,最后特判下不符合一次函数的情况,水题

2.          完美的波形图

(waveform.pas/c/cpp)

60分做法——普通DP,O(n^2)

第一重循环枚举波峰的位置,第二重循环计算要修改值,找到最小的即可

100分做法——优化,O(n)

通过算法60分的做法,我们发现可以优化掉内层的循环,先用f[i]记录从头到第i个音阶的修改值,g[i]表示从尾到第i个音阶的修改值,最后再O(n)枚举波峰位置,O(1)计算修改值比大小,套路性极强的DP。

3.          布置会场

(hall.pas/c/cpp)

60分暴力的做法应该很好想到

100分的正解——在每两个座位之间建边,距离记为边的权值,做kruskal最小生成树,将n^2条边从小到大排序,找(n-k-1)条小的边加入并查集(两个端点原本未在同一个部落中)输出第(n-k)条边即可。这题应该是整套题中思维复杂度最高的,正解比较难想到,但部分分很好拿,而且时间给了2s,没有卡时卡常数。

出题idea的来源:noip2010关押罪犯

4.          噪音问题

(noise.pas/c/cpp)

50分——dfs深搜

100分——bfs广搜+队列,模板题。考验选手的代码能力,注意对‘A’—>‘Z’大写字母的处理。

T4的数据完全随机构造,不存在极限数据。

关于极限数据的解释:当噪声源(大写字母)数量超过100*100个,由于常数过大,需要3s以上时间,所以本题数据中不含极限数据。

总结:

      T1 水题

      T2 DP+优化

      T3 最小生成树

      T4 bfs

第一次出题呐,感觉T4出的太垃圾,还是自己太弱233...暴力的分都很好拿,如果都写满的话,差不多>=250,第二题第四题都是套路题,第三题难度应该是较大的,总体难度略高于noip2016普及组


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr