2017.11.10

NOIP2017滚粗记


  明天就是提高组,马上考试了,十分紧张,这天中午去的,车上一直在睡觉。

扯淡

考完联赛后一直在搞文化。。。
联赛过去了不知道多少天了才来写这东西。。。。


  晚上看了看模板,双联通,强联通之类的,怕考到,树剖和点分也记了记。

Day0

早自习知道了要期中考试。
感觉心态炸裂了。
上午在乱敲板子。。。。
打了一堆莫名其妙的数据结构。
其实完全没什么卵用啊。
下午老师说要调整心态。
调整心态啊。。。。。
那就颓呗。orz yyb大佬 直接用解放军虐翻美帝
感觉CJ的象棋素质不够高啊,就连我这种渣渣都没人下得过。
晚上在家里颓?
10点就睡觉了,不过躺在床上想了很多乱七八糟的事情。

  晚上定了一个kfc,吃得恶心。

Day1

出发的比较早,早餐在长理的食堂吃的,味道还不错。
然后8:15进了考场,感觉今年确实很严格啊。
尼玛开考前不准动电脑?
闲的蛋疼的我赶紧默了一遍配置。
这个NOILinux怎么设置了密码?
哼,我毕竟曾经在NOILinux上安装过网易云。
当然不会忘记NOILinux的密码。
看着周围同学一脸懵逼,机智的我输了个123456就进去了。

进去一看,这什么垃圾系统。
工作区都没有?外观里面开不了?
不支持新建模板功能?
然后我在文档里面发现了一些诡异的东西。
CCF今年太良心了吧!!
模板已经给你打好一大半了。
还有对拍也给你打好了。
emacs配置里面给你自动加上了编译命令。
不过配置+模板还是消耗了大约10至15分钟。

15分钟看完题目。
T1明显是一道规律题目。
T2直接模拟。
T3的话。。。。。为啥k这么小呢?是不是可以搞一些奇怪的算法。

然后开始想T1。
一开始在观察样例。
令\(a< b\),
对于任意\(x=ak+r\)。
我们要使其可以选,
r肯定是用b来搞掉的。
那么又\(gcd(a,b)==1\)。
所以每一个r都需要对应个数的b来搞掉。
所以b用的最多的就是(a-1)次。
所以答案为\((a-1)*b-a\).
即\(ab-a-b\)。

tnnd想了我好久啊。
不放心还打了个拍。
这时候大约是9:15的样子。
去上个厕所稳下。
然后看T2.
tnnd还是细节很多的。
不过反正不用担心复杂度的问题。
一顿乱搞总之就过了大样例。

这时候10:00了。
还有两个小时,感觉今天很稳啊。(内心真实写照,感觉奶死了自己)
然后T3不会做了。
尴尬。
部分分貌似不是很好拿。
感觉有点捉急。

bfs肯定可以TLE。在最短路很长的时候跑的会很快。
DP肯定可以MLE。但是可以处理最短路很短的时候的情况。
嗯。。。。。。
那就直接把这两东西搞在一起不就可以了吗。
然后就开始打BFS+最短路剪枝。
没打多久就打出来了。
我去你大爷的。
大样例一次要跑1分钟(O3)。
还是个错的。
答案就比大样例少了20几。
崩溃了,调到11点中没有调出来。
决定再打DP。
然后20分钟打完,大样例过了。
这就很舒服…….
打个对拍,好像在最后20分钟调出来了。
然后就一直在测极限数据。
我的程序是如果最短路大于某个值,就BFS,否则就DP。
然后我就一直在调这个参数,最后发现DP跑的慢的要死,一怒之下设成了100。
最后还是检查了一下。
貌似没有问题。


出来膜拜ZSY大佬怒切T3.
下午在颓刺客信条。
晚上突然想起T3忘记初始化路径。
完了,心态爆炸,GG上天啦。
期望得分:
\(100+100+0=200\).

2017.11.11

Day2

今天走的很早,还是在这边吃的饭。
进考场了。
仍然是10~15分钟敲配置+模板。
然后再看题目。
T1明显套路煞笔题。
T2一看就感觉是状压,又感觉不是。
比较n<=12的都应该可以用搜索做了吧。
T3我一看就知道是差分,但是我并不会做。
果不其然,联赛这尿性就是每年一道差分题

水完T1差不多9:15的样子。
接着刚T2。
果然状压好像不行啊。
必须记录每个点到根的距离啊。
那就搜呗……
加了个最优性剪枝发现跑的贼快。
但是极限数据过不了。
麻烦啊。。。。。
然后发现对答案有影响的只有两个东西。
所选的边的边权。
所选的点到根的距离。
那我是不是可以A*?
把搜索顺序按照一个估价函数的值排序。
然后小的答案就会排在前头。
然后我的最优性剪枝就会发挥作用。

不得不说我想的太多了,
由于每次要开一个数组来存搜索顺序。
不管我怎么改估价函数,
跑的比原来的还慢。

我一气之下只搜按照估价函数排序后前一半的决策。
tnnd,跑的还是很慢啊。。。。
不过答案是对的诶。
搜1/4?慢
搜1/8?慢
搜1/16?WA了…….
后来只搜前3个决策。
勉强能过而且不TLE。
打了个对拍,然后就放那里拍。(60s才能拍一组强不强?)
应该还剩下1h30min的时间吧。

然后就去写T3了。
50分就随便乱搞一下。
不过调了我好久啊,最后只剩下50分钟了。
然后我发现30分需要打平衡树。
50分钟我打的出来么…….
这时候一看发现T2拍WA了。
发现拍了50多组数据就WA了。
好可怕,然后仔细一测发现还是个T的。
再稍微缩小了一下决策范围。
应该还是挺稳的。
(出题人应该不会卡我这种鬼畜的搜索算法吧。。。。。。)
然后突然发现T3剩下30分可以写值域线段树。
哈哈哈,单点修改线段树就十分舒服。
大约10分钟后我写完了。
测了一组小样例我就没管了。
最后糅合部分分的时候真tm烦。
差点没搞好。


出了考场感觉Day2的状态不错。
然后下午一测。。。。。
T3忘开Long Long。
GG了。
期望得分:\((100)+(100-??)+40=240-??\)

  提高组的第一天,起来十分紧张,昨夜没睡好,半夜lln莫名把我叫醒,kfc吃坏了,

总结

这次考试的话,感觉考的不错,但还是留下了很多遗憾。
Day1T3就忘记初始化。虽然加上之后只有30分,又WA又T又RE
Day2T3忘记开longlong,导致辛辛苦苦打了80分,最后只能得到40分。

两天都是T3出毛病,感觉跟我的紧张心态脱不了干系。
同时也跟平时考试时的放松有关系。
直到联赛前的一次模拟考试,我仍然犯了不少低级错误。
想必联赛的时候肯定更容易犯错吧。
会做题是实力,可是能拿分才是真正的实力。

  土豆泥的问题,起来没有食欲,吃了一点点早餐=空腹,考前又看了看模板。

最后的扯淡

为期一个月的NOIP集训就这么结束了。
然后我就去考期中了,
然后就被爆踩了。
准备被各科老师怼死。

  8:10多分进入考场,紧张到没有了,反而现在写blog的时候紧张,不知道为什么。

  解压密码后,看了看题目。

  第一题我去,什么题目,扩展欧几里得的应用???

  ax+by=c
这种方式,但是貌似很难做啊,怎么办,当时十分绝望,这个我好像,不是特别会,

  不会要挂吧,然后仔细读题,发现有大数据,那看一看吧,看了以后发现,这不是相乘在减一下两数之和吗?

  然后写了一个dp,发现,对了,轻松了不少,发现规律时想,有些人应该不会一眼看出,有些坑了,

  但是说不定扩欧可以。

  第二题题意十分长,不过可以看出是裸的模拟,考验细节,然后仔细打,应该没什么问题。

  第三题,这不是魔法猪学院吗,唉,GG,我当时就是朝着这个思路去想的,写了一个A*,以为轻松60+

  结果day1只有100+100+30=230分。

2017.11.12

  昨晚诸老师说今天题目会很难,看了第一题后发现,还是比较简单的,虽然刚看到题目的时候,觉得

  十分难,以为考几何,结果就是bfs吧,判联通性。

  第二题有些难,没什么特别思路,应该是爆搜或者状压,毕竟数据范围小,

  先写第三题,写了50+20=70吧,应该没问题的,本来20分想写线段树的,但是毕竟第二题还没打,的留出时间,

  还有STL没学好,以为vector是平衡树的,早知道用deque还是list了,但忘了哪个是链表的,

  哎,然后回去写第二题,看了看,那就最暴力的写状压吧,O(2^n*n^4),八千万左右,但是这是极限

  不会到达极限,估计两千万左右,毕竟这是我可以想到的最好方法。

  但是还是爆炸了,只有100+100+35=235

总结:这次时间还是充裕的,应该多去思考,day1T3 day2T3
这次十分不好,应该多去思考有保证的,当然暴力分是应该先写好的。

这次高一,跪了。

admin

相关文章

发表评论

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