2016.8.4第一次选拔考试

2016年信息学竞赛选拔试题一

今天是第一次选拔考试……还好,没考得很差……至少还在第六名……一班还有希望……

今天215……嗯A了一道题,一道题莫名T50分,两道骗分出奇迹!

果然骗分大法好,明天我要骗更多得分!!!

1、Paladin

今天的第一题,一道组合数学题,要写高精度……

高精度真是跟我八字不合!!!2个小时的高精度……然后还有50分超时啦……

是我被高精度搞晕了,一开始我想分解质因数,然后不知道怎么得出结论会爆空间……于是我就把分解质因数删掉了……于是……T飞了。

我真是傻,然后考完了以后稍稍修改就A了……

正解我就不说了……

就是先求出最小步数,然后判断满足要求的点(最多3个),然后计算组合数。

计算组合数的时候可以分解质因数,这样就可以节省很多时间,然后再一路乘起来,加些小常数优化即可。

2、DeathKnight

简单的容斥,半小时AC

3、Luna

神奇的构造题,正解真难想,但是骗分很好写

然而我骗的分还是太少了……

这题的骗分方法基本上是随机化贪心或者卡时搜索之类的……

然后正解是分治构造还要打表,很复杂,事实上还是骗分性价比更高。

4、Nessaj

一道二分图匹配题

我居然没想到!!!蠢死了

然而骗分竟然奇迹般的拿到了55……

骗分出奇迹!我只打了10分钟诶!

正解是奇偶点染色,然后跑最大匹配,然后将不再匹配中的点全选,将与被选的点相连的所有点不选,然后将不选的点的匹配点全部选上……

就可以了

 

总的来说,明天还要加油!

不如来评论一发?