Skip to main content

__debug's Home Keep it simple, stupid

记 NOIP2016

算是复仇成功了吧.

Stories

Day1

开考看题, 觉得今年的题画风不对啊… B 题怎么不能一眼秒了呢, C 题根本看不懂啊算了.

于是打算先想想 B, 大概 9:00 了还没完全想清, 有点虚了, 于是开始打 A. 打完之后想了一会儿就去打 B 了, 打着打着发现我的做法要线段树合并… 我去说好的联赛第二题难度呢.

但是我还是继续打了下去. 打完拍上之后, 心里想妈的 B 题都刚这么久, C 题怕是要完蛋啊. 然而一看完题… 妈的智障.

于是愉快地解决掉了 C, 这时大概是 10:30 左右. 回去造 B 的极限数据, T 飞了.

然后卡了一下常, 用 RMQ 求 LCA 之后好像就卡进去了. 空间要用 200 多 M…

比赛结束出来之后发现 B 题还可以用点分治… 然后听说毛爷爷的做法是 \(O(n \alpha(n))\) 的, 听说还有线性做法… 啊, 我好智障啊.

UPD: 我怎么就没有利用区间可减性呢… 权当是练习一下线段树合并和卡常技巧好了.

希望别挂啊 QAQ.

这次联赛也不按套路出题了, 个人感觉 C 题要比 B 题简单许多. 所以明天一开始一定要好好看题.

大家加油.

Day2

今天没睡好, 到考场上都是懵逼的.

汲取昨天的教训, 先把三题都看了. A 题没什么好说的, B 题怎么一眼队列秒了啊, C 题怎么像是大爆搜啊. 没错当时我脑子里根本就没想状压…

于是开始码. A, B 都很快搞完了. 期间发生了一件很有意思的事.

我 B 题拍着拍着, 突然告诉我硬盘空间不足了…

Fuck you! 什么垃圾电脑啊, 我要投诉! 结果发现 .out 有 1.3G… 原来是我随的数据 \(T = 0\) 了, 蜜汁尴尬.

C 题打完之后发现好像 T 飞了, 发现原来是状压啊, 艹, 我怎么这么蠢啊.

然后懒得重新写了, 于是就在 DFS 里面套了个很迷的记忆化. 后来发现不好造数据, 于是 py 交易了一发, 每次随抛物线, 然后随机取点, 这样就有了答案的上界. 然而我的 py 姿势不太熟练, 调数据生成器调了好久…

又后来发现精度炸了, 于是直接硬上分数类. 而且不知道怎么回事, 我用 scanf("%lf", &x) 读一个小数, 然后 x * 100 转成 int 硬是有 \(0.01\) 的精度误差, 我也懒得研究了, 于是直接读两个 int 进来.

UPD: 经过一些研究, 发现这的确是浮点数的一个大坑…

考虑下面的代码:

#include <cstdio>
int main()
{
    double x;
    sscanf("9.78", "%lf", &x);
    int y = x * 100;
    printf("%.16f %d", x, y);
    return 0;
}

输出将会是 9.7799999999999994 977.

这是由于浮点数的内部实现是用二进制小数, 所以诸如 \(0.1\) 这样的数字无法精确地表示. 平时在 double 之间用并没有出事, 因为误差非常小. 但是一旦从 double 转为 int 的时候就会出问题了, 因为要向零取整. 所以很多时候 double 需要 + 0.5 或是 round, 并不只是因为运算过程中出现了浮点误差, 而是 从一开始就不是精确值.

同时还有一个坑… FFT 的时候很多人都会写 int(x + 0.5), 然而 x 为负数的时候并不能这么写… 在需要强转 int 的时候用 round 比较保险, 不用考虑正负的问题.

C 题感觉比较虚, 希望没有写挂吧.

终于考完了, 要回去补文化了.

After Story

听说刚考完就有源代码了?

用余姚中学的数据测了一下, 结果看到自己:

(下面一个)

其实还是比较庆幸自己没有出大的失误, 但是 angrybirds WA 了两个点, 虚死了啊. (toy 那题是少复制了一个数据)

后来发现:

这数据造的真好啊.

今年联赛, 我想复仇.

Solution

Day1

A

直接按照题意在 \((\text{mod}\ n)\) 意义下模拟即可.

B

考虑一条 \(u \sim lca \sim v\) 的路径.

在 \(u \sim lca\) 这一段, 某个点 \(x\) 会观察到这个路径当且仅当 \(\mathrm{dep}(u) - \mathrm{dep}(x) = w_x\), 也就是 \(w_x + \mathrm{dep}(x) = \mathrm{dep}(u)\). 同理, 在 \(lca \sim v\) 这一段, 某个点 \(x\) 会观察到这个路径当且仅当 \(\mathrm{dep}(u) + \mathrm{dep}(x) - 2 \mathrm{dep}(lca) = w_x\), 也就是 \(w_x - \mathrm{dep}(x) = \mathrm{dep}(u) - 2\mathrm{dep}(lca)\).

通过将 \(+1, -1\) 事件挂在每个点上, 现在问题就转化为每个点有一个权值, 要求出每个节点的子树中加入的权值有多少等于某个值.

然后我在比赛时就愉快地线段树合并了… 典型的数据结构学傻了选手. 其实因为我们只关心某个特定的值, 我们只需维护一个全局的 \(cnt\) 数组, 然后进入这个子树前先将当前的 \(cnt(x)\) 记一下, 搞完这个子树后减一下就可以了.

C

首先 Floyd, 然后设状态为 \(dp(i, j, k)\), 表示考虑了前 \(i\) 个课, 用了 \(j\) 次机会, 第 \(i\) 节课的申请情况为 \(k\) (\(0\) 为未申请, 反之亦然). 直接利用期望的可加性转移即可.

Day2

A

直接 \((\text{mod}\ k)\) 意义下 \(O(n^2)\) 预处理组合数, 把答案全求出来即可.

B

当 \(q = 0\) 时, 每次将最大值 \(x\) 分裂为两个值 \(a, b\), 可以发现随着时间增加, \(x, a, b\) 都是单调递减的. 经典问题, 用队列代替堆可以做到线性.

当 \(q \ne 0\) 时其实也是一样的, 只用维护一个 \(add\) 表示每个元素的增量即可.

C

直接状压, \(O(n)\) 转移即可. (强制用 lowbit 转移)

然而我这题的做法非常迷, 是一个基于暴搜的做法, 跑得非常快, 民间数据最后几个点全都是 0.000s

Sigh

这次联赛, 我们机房大多数人都没有发挥出自己的真实水平, 有人受题目顺序的影响策略失误, 有人随便想出正解但是就因为打错了一些细节爆炸了.

这种心情, 我应该也是多次体会过的. 高一时的 NOIP, 一题超代码长度限制, 一题忘记取模, 当时考完联赛的我大概也就是这种, 日了狗了的心情吧.

但是悲伤的是, 这次并不一样. 因为我们高二了, 对于很多人而言, 也许这就是最后一次联赛.

不论如何, 悲伤过后, 还是得继续走下去的. 大家一起加油吧.

Songs

最后, 用一些歌来记录今年的联赛吧.

比赛前夜:

Day1 想 B 题的时候:

Day1 看懂 C 题之后:

Day2 从看题到看完题:

后来, 发现很多水平很高的人都挂了:

最后, 还是这首歌:

还有那首诗.

Comments

Comments powered by Disqus