SCOI2018 AFO

翻盘失败,OI 再见……

DAY1

T1 就是给一个 $n$ 个节点的树,点有点权,要求支持单点修改,询问某个点到所有点距离的最大值。傻逼点分树套线段树,开场 10 min 开始写,30 min 写完后过掉大样例,然后被卡空间,被 64 MB 内存 MLE 送走。

T2 给出一棵树,求满足 $v$ 是 $u$ 的祖先且 $a_u ^ 2 + A a_u a_v + B a_v ^ 2 \equiv 0 \pmod P$ 的点对数量。忘了 Cipolla 算法怎么求的了,咸鱼写暴力和特判….

T3 给出一些 $M$ 维坐标的关键点,从原点开始关于这些点对称,每次给出一个点,询问能否到达。完全不会,暴力写不出,弃疗….

预计 100 + 55 + 0,实际 15 + 20 + 0,T1 MLE 成智障,T2 不知为何暴力都爆了,难道说 $O(1)$ 快速乘爆了???

DAY2

DAY1 完爆,期待 DAY2 翻盘…..

看完三题,这 T1 好傻啊,由于昨天 MLE,赶紧再看一眼空间,128 MB……
T1 就是给一个序列 $a$,要求支持单点修改,询问区间 $[l, r]$,给这个区间内某连续三个数加上 $v$ 后,序列 $a$ 的所有元素绝对值之和的最大值,询问中加的 $v$ 不会影响原序列。
显然 $|x + v|$ 是 $\max\{x + v, -x - v\}$,然后对于连续三个数,并在一起就只有 $8$ 种搭配,然后用线段树维护就完了……

由于 T1 的大讨论做法太暴力,写完开始拍已经 2.5 h 了,想了想 T2,没什么思路,咸鱼写 $m = 0$ 的暴力,然后开 T3。

T3 就是有一个商店,一个人去买东西,每个时刻会有一种操作:

  1. 商店引进一种热量为 $a$,价格为 $b$,价值为 $c$ 的物品。
  2. 询问购买热量 $\leq a$,价格 $\leq b$ 的商品的最大价值。
  3. 回到第 $i$ 个时刻。

强制在线,对于 $3$ 操作时间上就是形成了一棵时间树。

想了想,可持久化三维凸包???不会啊……
然后开始写单纯形,$2 \times n$ 的单纯形似乎跑的挺快啊…..
在想了想,似乎单纯形中间很多地方不用重复计算啊,然后写可持久化平衡树维护一下感觉有很多分。

写完调过了第一个大样例,跑了跑第二个,居然过了,也不算慢,感觉 T3 60 pts 稳了……

100 + 30 + 60 似乎翻盘有望????
下来发现是 100 + 0 + 15,这个 T2 怎么卡精度啊,T3 这个大样例好假啊!!!!!

翻盘失败,OI 再见……
只能祝大家 NOI 顺利吧……

一些OJ的一部分代码,我也不知道全不全,至少 BZOJ 似乎挺全的(想刷某些题榜的同学似乎可以看看???)

总之明日は明日の风が吹く,安心准备高考,祝你们接下来一路顺利吧……

分享到