NOIP2017

NOIP2017 ~~爆零记~~ 参赛总结。

（先 flag 立在这里）。。。

问题是，真的爆炸了。。。

Day1

竟然开场先来一道数学题，算到一半突然开始看样例解释，就给蒙出来了。。。

爆炸的根源。本身是一道不算复杂的模拟，但是我考虑错了平行的 for 循环，爆 30。。

但是讲道理，样例 2 应该能把我给 hack 的 ( 我 Day2 的时候莫名其妙地找到了没有删掉的 Day1 样例文件 )，难道是我 bash 写错了 ?? 要真是这样的话，那就真完了。。。

最大的问题是：这个问题是我在 Day2 进场前发现的，差点心态爆炸。。。

又一道爆成 10 分的题，原因不明。

UPD: ~~首先 -1 就判错了，又没有删。。而且有数组没有清零。。。~~ 好吧，其实是 n 和 cnt(dijkstra 序中的最大标号 ) 写错了。。。（话说，我在想标算的时候已经想到了这个问题，怎么忘记改了呢？？）

这道题挺正常的，我估算出来可能平方的时候要开 unsigned long long（似乎很多人没考虑到）, 但是 luogu 的数据没卡这种情况。

40 分贪心挺好骗的， 70 分暴力我也想到了，但是胡乱算了一圈复杂度好像是 $O(n \cdot n ^ n)$ , 似乎过不去，放弃。( 实际上是极不满的 $O(n ^ n)$ , 也许是 $O(n ^ {n - 2})$ ?, 反正打了就有 70 分了 )

UPD: 实测十分钟写的 dfs 暴力就能过大部分随机数据，加最优性剪枝就稳 70 了。。。

30 + 30（可能被卡常），也没什么可说的。

NOIP 就这样结束了，下场似乎有点惨 ( 也许这些问题都避免就能够拿 100 + 100 + 70 + 100 + 70 + 60 = 500 的，却实际只有 100 + 30 + 10 + 100 + 40 + 60 = 340(luogu 数据 ))，但是这已经无力改变了，只能明年再来了。

总结如下：

1. 跑样例的 bash 一定要检查循环数是否等于样例数 ( 这件事一定要放到和检查文件名同一高度上！！！ ) （其实有一次也是脚本出错导致爆炸的。。。）

2. 一定要多拍样例，不但要测编代码时想到的 hack，调试的时候一定要想想“还有其它 hack 吗？”

3. 其实 D2T3 60 分打完还有 30 分钟左右时间，应该是足够打 T2 的 70 分的（至少不加剪枝的应该写的出来），却因为复杂度而望而却步。所以不能被复杂度束缚，而应该看实际运行时间！！！

UPD: 4. 注意变量名，注意所有对算法的修改要落实到每一个实现中！

正如我在初三总结出来的月考经验：只要每一门学科都发挥正常（没有弱智丢分），总成绩就会比较理想。
只要每一道题目都不出偏差，就能取得满意的成绩！
但是，这却很难。（按照考试评级方法，我每次总会有个 C）也许在接下来的一年，需要克服的就是这些问题 \

UPD: (11.25)

官方数据好水，竟然 D1T2 骗到 90 分，D1T3 骗到 50 分。(100 + 90 + 50 + 100 + 40 + 60 = 440, 多骗到 100 分 233…)

原来我测了 D1T2 的大样例啊。。。

顺便写一发题解：

D1T3: dijkstra 求最短路 + 拓扑判 0 环 + dp（按照 dijkstra 序 + 拓扑序）

D2T2: 状压 DP，将深度作为阶段转移。（在保证不漏正解的情况下减少状态，虽然可能会增加不优的方案。换句话说，增加错解没有关系，只需要保证正解存在即可）

D2T3: 将最后一行单独处理，线段树（平衡树）优化链表（单点修改 + 求第 k 大）。动态开点 , 如果用树状数组的话，就是先离线求出对于每一行（以及最后一行）每一个询问所对应的位置（这个可以离线后用一个树状数组处理），然后再处理每一个位置上的具体答案。

– The END –

要上文化课了！

jhdjames37

2017.11