NOIp游记

· · 个人记录

寄死了

考前

好像7点0几分就到了，等了好久

试机

先敲了个tarjan缩点（，然后又敲了个字典树，忘了空间怎么开，感觉很慌，开自动保存，开一系列编译命令，打了个缺省源。旁边的人经常看我代码，莫名感觉很慌。

考时

一开始发的密码是solo什么什么的，结果错了，一直到8：40多才有密码，rp--，解压后发现pdf还有个密码，试了试那个密码不对，果断试了solo，果然对了，比别人多出至少15s,rp++

9：10左右看完题目，感觉全都不可做，暴力也很难打，开始思考T1。 先考虑可以光优化C，可以先枚举上下两个边及中间的那条线，如果这条线没有障碍的话，可以分别找出上下两条线往右遇到的第一个障碍，乘起来，再加起来，复杂度就变成 O(n^4) 了，向右第一个障碍和这条线是否有障碍可以预处理，复杂度就变为 O(n^3)，在考虑只枚举两条线，上面那条和左边那条，之后对于每个下面的，我们可以预处理，预处理出从上面那条线的+2位置开始，走到下面第一个障碍，所有能够向右扩展的和，处理一个后缀和就可以，复杂度变为 O(n^2)

接下来考虑F,可以分别处理右边 第一个的障碍的距离*下面第一个障碍距离，再求个后缀和，就做完了。

想完时时间为9：30左右，9：50就写完了，开始写对拍（还好我写了，不写就完了），10：10左右，写完对拍后，暴力发现马上就错了，把错的那组数据复制下来，试一下，发现又跟std一样了，立马察觉到没有清空，清空后继续拍。拍了一会，又发现错了，复制下来std用试了试又和暴力一样了，发现std也没清空。（太艹了，还好写对拍了

此时已经10：20多了，开T2，最大的错误，每个部分分都不会，很慌，™的打了个n^m的暴力，贼难打，还难调，打到12：40多，还没对，非常慌，决定不打了，去看下面的题。

先看的T4,一眼望去只会8分暴力，感觉20分要单调栈，还难调，就没打（丝毫没意识到可以预处理。

打完已经12：50了，检查了一下，准备走

突然被告知延长10分钟，开始想T3，发现链上随机选两个点 i,j分别作为起止点，起止点中间军营可以随便放，除这条路径上的其他边也随便选，方案数就为2^{i-j-1}*2^{m-(i-j)}=2^{m-1}，于是可以直接做，再加上只选一个点的方案数，感觉没有可以写挂的点，也没测试。啊啊啊啊啊啊啊啊啊啊啊

贴一下我的sb错误： 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

预计：100+0+10+8=118

洛谷：100+0+0+8=108

小屠零:100+0+0+8=108

落得暴力老哥的分数了，小屠零上显示没到一等奖，但凡我T3检查一下，哎~~~~~~

出分了

和自测分数一样，听说T1n^2m过了一车，可能没法一等了（108的™到了210多。