NOIP2018 打味极鲜记

 

初赛

上午:

去体检

回来颓废

下午:

颓废

随便做做就79了


Day 0

上午去了玩了一会 2048 , 然后打板子,惊险刺激。

中午去面基,看到了 rqy zyb ckw 和 ytez 的一堆神仙 , %%%

下午本来打算做那个树剖的题,最后好像板子都没打完,于是就放弃了。( 晚上看了看题解,发现自己  脑子大概退化了,这么显然的性质没立刻想到,惨的一比。)

到了傍晚仍旧没打完一堆板子,打了 20k 代码手疼的一比。

去找 gjh 玩,聊了一会还挺开心的。

然后去找 ycr 大爷拿到了牛氪的衣服。

去试机的时候竟然忘记身份证在口袋里了,急急忙忙跑回十楼拿,结果发现了。

打了一个树剖板子 一个 Dinic ,就差不多结束了。

走的时候还没忘试了试带的那个 python 2.6.6 好不好用。

晚上水群,颓废了一会osu! ,然后看了一集《终将》就睡觉了。

感觉晚上睡得还是挺香的。


Day 1

早上早起,在机房见到了 LHHH , 开心。

没想太多就直接下去考试了。在考场外面和 gjh 不过脑子地聊了一会,正好都放松一下。

进场离开始还早。今年的压缩包没法提前打开了,所以好像没法提前建文件夹了。QAQ。

不慌不慌, Day1 一般都很简单的吧,争取 A 两题。

开考先盯着第一页看了两分钟,然后往下一翻……

smg???我没眼瞎么??i7-8700k ?? 32GB??每个题都 512MB??

哇……这太良心了……随便用内存啊

开考瞅 T1 ,卡了半天没思路。

继续没思路。

还是没思路。

写个暴力吧。 70 拿到手。

滚去看 T2 了。一开始考虑把每个物品用剩余物品表示,那就是解个式子 a_j = \sum_{i=1}^{n}{a_ix_i} \,\,(i \ne j) 嘛。

exgcd ? 不是不是,唔,好像是完全背包。完全背包的 DP 方程是什么来着?

写了一气,过了样例。造好数据对拍。

好,才九点四十,继续搞第一题。

然后决定沿用那个分治的思路,每次找最小值。上个高级数据结构 O(\log) \sim O(1) 级别求值。

最后写了分治+ ST 表,拼命调了一会,过了。

和暴力拍着,10:00 , 还有充足的时间,去看 t3 。

诶? m=1 ? 我会 DP ……

链?二分+贪心嘛,挺显然的。

菊花图? 哦,可以双指针。

写写写,写了3k 代码把这三个部分分全写了。

随便手造了几个小样例过了就算了。

最后 15min 检查代码,检查文件,手动编译+测样例。

然后就考完了,走出考场估计 255 。

听说今天一堆人 255 ?


下午去学校的路上,在某一瞬间突然意识到自己的直径 DP 写挂了。

woc? 好了,现在我 d1t3 有多少分 完全取决于每个数据的 1 号点在不在直径上了。

240+ ,难受。

努力不去想这件事,下午和 rqy 还有 gjh 一起闲聊了一下午。

前半段挺开心的。

后面听说 yt 写炸的事情了,难受。

晚上在家休闲。去洛谷背了前两题的代码+讨论试题 + 打板 ,最后也是照例打一会 osu! 就睡觉了。

好像今天送了一批人退役。


Day 2

早起,又在机房见到了 LHHH ,心情平静。

开考,密码大致上被大家猜中了。

照例先看第一页,看 t1 。

想了一小会就会了,于是开始写。

我觉得在考场上写无向图判环是我最大的失误。这个破函数调了很久但是还是没有过。

最后放弃判环了,直接分别删去每条边一次,再判断连通性。

调试的时候强忍住没有崩心态,一直逼自己相信还有希望。

大概 10:00 调过了。从 09:30 到 10:00 大脑完全是混乱的。

还是慌了。心理还是不够强大。

还是自己太弱,远远没有达到要求的缘故。

瞅了 15 分钟第二题还是一点思路都没。去搞 t3 。

当时考场想到是个 DDP 模型了,可惜我没学过怎么写 DDP 。

看部分分。前 44 很轻松的想到了树形 DP。

后面搞了十分钟没啥思路,于是花十五分钟把树形 DP 写+调了。

实在不敢搞了,就去刚 t2 了。

t2 随便口胡了好几种 DP 方法都被我自己叉了。

n=2 决定写个状压,看起来挺靠谱的。

然后测了几个数据发现这玩意有规律。 \mathrm{ans} = 4 \times 3^{m-1}

这就非常尴尬。但是我也懒得改了,开始写前面的 DFS 。

还是调不对,还是逼着自己别崩溃,然后最后也是调出来了。

尝试爆跑 n=m=5 ,花了五分钟跑出来了。DFS 似乎是对的。

考场调试真的 真的很难受。

出考场估分 194 。今天这个题好像彻底送了一批选手退役。

和 gjh 跑去找 rqy ,他也没 A 掉 t2t3 。

然后回家听说 wxh 也被 t2 安排了。

今天题好难啊。

晚上回家写了 Day2 ,洛谷 194 。数据好水啊。听说牛客出数据了测了一波,也是 200+194 。


Day 3

上午去考语文。半点心情都没有,写了写选择趴桌上睡了。

班主任千方百计骗我们来考试,又说不让我们考了,都没学,找间教室自习。

唉。

下午考英语。 阅读好像无比简单,1h 做完卷子趴桌上睡了。

然后就跑机房了。下午测了一波正睿的数据。

意识到自己把 d2t2 的 n \leqslant 2 看成了 n = 2

难受,和 R 哥讨论了一波发现这样丢掉大概有十分。

发现自己去不了 pkuwc 或者 thuwc 了,崩溃了。

晚上没精神学习,看了两集数学视频,大部分时间都在水群。


Day 4

早起来机房。大概九点多的时候教练来了,把我的数据从考试机上搞出来了。

测的时候手一直在发抖。

洛谷 349 , 正睿 324 , 牛客 314

看了一眼 track.cpp , 意识到一个无比残酷的事实:

我菊花图写炸了。

我菊花图写炸了。

我菊花图写炸了。

双指针……随着右指针的左移,我左指针是可能固定的。

也即我没有用过之后把左指针右移。

完了,彻底是错的。

心脏难受。

这个时候浙江的民测成绩也出了,看了一眼,觉得自己

可能就没有希望了吧 ?

(NOIP.score=random(404,439))>420?在役:AFO

就这样吧。

听天由命。


Day 7

来机房颓废一下……

继续听天由命 发现这几天的局势并没有什么新的变化

所以大概没啥好写的。


Day 9

照旧来机房,还是没法做题,继续颓废

大家心态都很炸

可能我也很炸

等明天吧。


Ending

不到一周之前出了成绩。和很多人也谈了很久

我最后的想法大概是这个不上不下的名次实在不好搞,不过毕竟期盼已久的 noiwc 大概能去,就继续搞省选吧。

大概潜意识里要是这样就 AFO 了,也是不太甘心的。不过理性的一部分还是督促我滚回去学文化课罢了。

还有很多想说的话就留给退役记吧。

NOIP2018 说实话就像上赌场,但是这段时间流的飞快,也没有抓住什么值得好好说的感受。

总之还有一个大坑是一定要挖开的。高中这几年 OI 经历太多,不写一写怎么行啊。


「远处的事物看起来渺小又模糊 , 近处的东西却非常清晰 ; 回忆也是同样 , 遥远的曾经非常模糊 , 方才发生的事能记得一清二楚 , 本应这样才对。」

「但我最近总能清晰地回忆起往事 , 」

「我活在我的时间里 , 她活在她的时间里 , 所以我们的时间互相交错的瞬间 , 对我而言比任何事物都宝贵。」

——   她与她的猫 – Everything Flows –


– END –

随便搞搞 ICG (公平组合游戏) 和其余的博弈

写在阅读之前:

本文是我在 10 月份期间开始的对一些见过或者想要学习的博弈模型的一个总结计划。本文篇幅较长,覆盖多种模型,以下是一份可以帮助阅读、理清主干的主题清单:

(待填充)

请注意本文分多页,可以在文末翻页

文章中数学证明、公式较多,请做好阅读理解的准备。这篇文不是闹着玩的,读就请认真读它。先说一句比较自以为是的话:

读这篇文学习博弈论的过程,并不是去背公式或者记性质,而是去熟悉并掌握处理博弈问题的一般思维方式。

快速索引:

Wythoff Game –  第 1 页

Nim Game – 第 2 页

从 Nim Game 到其他组合游戏 ||  归纳与推广、泛化模型 – 第 3 页

SG 函数的构造 || 更进一步的推广 – 第 4 页

Anti-Nim 与 Anti-SG – 第 5 页

Multi-SG || Every-SG – 第 6 页

翻硬币游戏 || NimK || 扩展 NimK第 7 页

树上删边游戏 || 无向图的删边游戏 – 第 8 页

扩展阅读列表  – 第   页

记号约定清单:

对于集合,用 \mathbb{A} 的字体表示。

对于局面,用 \mathbf{a} 的字体或 \mathrm{S},\mathrm{T} 来表示。

\text{s.t.}  → “ 使得 ”  , such that subject to 的缩写。

\forall \exists 分别为 “ 任意 ” 和 “ 存在 ” 的意思(数学量词)。

\oplus  → 代表 xor ( 按位异或 ) 运算。

DAG → 有向无环图。

ICG → 公平组合游戏。

SG → Sprague-Grundy 函数


Wythoff Game

经典的 Wythoff 博弈模型。

这个模型的描述是这样的:地上有两堆石子,其中一堆有 m 个石子,另外一堆有 n 个石子。两名玩家轮流取走石子,规定每次要么从其中一堆石子中取走任意多个石子,要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了,谁就输了。也就是说,取到最后一个石子的玩家获胜。

这玩意其实还可以描述为:

把国际象棋棋子皇后放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。

描述局面、获得结论

我们知道博弈的关键就是局面,那么我们考虑用一个数学模型去描述局面好了。我们把局面记作一个无序二元组 (n,m)

  • 首先我们知道 (0,0) 是一个必败态
  • 其次, (n,0) \,(n \in \mathbb{N}_{+}) (n,n) \,(n \in \mathbb{N}_{+}) 是必胜态,因为先手拿走 n 就好了。
  • 再然后,我们考虑一个更加一般的状态 A=(n,m) \,( n,m \in \mathbb{N}_{+} \,\, , n \ne m)

我们先给出结论:所有先手必败的数对(我们称为奇异局面)分别是:

(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)

更严格地来说,其实是:

\mathbb{S} = \{(\lfloor 1 \cdot \varphi \rfloor , \lfloor 1 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 2 \cdot \varphi \rfloor , \lfloor 2 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 3 \cdot \varphi \rfloor , \lfloor 3 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 4 \cdot \varphi \rfloor , \lfloor 4 \cdot \varphi^2 \rfloor ) \}

其中的 \varphi \frac{ \sqrt{5}+1 }{2}

关于这个结论最科学的推法(而不是什么打表找规律),这里有我整理的一份文档,可以读一读 : Wythoff Game

证明结论

这里我们尝试证明这些状态的三个性质,从而证明这个构造是先手必败的(设状态为 \forall A \in \mathbb{S} )  :

  • 状态 A 无法一步转移到状态 (0,0)
  • 状态 A 无法一步转移到 \mathbb{S} 的另一个状态。
  • 状态集合 \mathbb{S} 之外的任何非零状态都可以一步转移到一个零状态\mathbb{S} 中的某一状态。

这样我们的博弈策略是后手始终把当前状态转移到 \mathbb{S} 中的状态,从而可以胜利。

对于上面三条性质的证明,可以在这里找到。我有空再仔细补坑

exgcd 合并同余方程组

\begin{cases} x\equiv a_1\ \left( \text{mod\ }p_1 \right) \\ x\equiv a_2\ \left( \text{mod\ }p_2 \right) \\ x\equiv a_3\ \left( \text{mod\ }p_3 \right) \end{cases}

以前做 CRT 一直是用那个构造性的暴力式子 ( q_{ji} 表示 p_jp_i 下的逆元 ):

x \equiv \sum_{i=1}^{n}{( a_i \cdot \prod_{j \ne i}{(p_j \cdot q_{ji})} )} \mod {(\prod_{i=1}^{n}{p_i})}  

(不过这个式子无比好记&&好用)

现在我们来考虑用 exgcd 去合并 CRT 方程。

直接先考虑俩方程

x \equiv a_1 \mod p_1

x \equiv a_2 \mod p_2

搞成某种加法形式

x + y_1p_1 = a_1

x + y_2p_2 = a_2

减一下

y_1p_1-y_2p_2=a_1-a_2

我习惯把减号改成加号

y_1p_1+y_2p_2=a_1-a_2

 

直接暴力 exgcd 这个方程,无解的条件是当且仅当 \gcd(p_1,p_2) \nmid (a_1-a_2)

求出解后记得 \mod p_2 ,这相当于合并方程了(注意 CRT 方程组最后的解的模数是 \prod_{i=1}^{n}{p_i} 。)

然后回代出第一个方程的特解 x_1 

x_1 = a_1-y_1p_1

(代码上的一个小技巧:因为这特解和 a_1相等同余的并且我们还要合并其他方程,所以直接更新 a_1

然后我们考虑通解是这玩意 : 

x \equiv x_1 \mod \mathrm{lcm}(a_1,a_2)

所以记得变一下模数。(可以维持那个特解不用变,因为在 \mathrm{lcm} 下是同余的)

大概的(伪)代码:

 

[SCOI2008] 天平

差分约束,套路地连边,套路地枚举得到答案

c1: \min(A-i) > \min(j-B)

c3: \min(i-A) > \min(B-j)

c2: \min(A-i)=\max(A-i) \,\, \min(B-j)=\max(B-j) \,\, A-i=B-j

具体式子看代码吧:

 

洛谷 P1660 数位平方和

最大的 xS(999999) \,\, (K=6) ,这个数字是 3188646 。其余待求函数值的 x 都小于这个数字。

所以最多是 4 \times 10^6 个元素求函数值然后再求个和,直接暴力。

试一下样例发现会出环,环上答案为环上最小值。

做完了。

 

[USACO06FEB] Steady Cow Assignment

首先 O(B^2) 枚举答案。

然后暴力网络流:

源向每个牛棚连边,容量为牛棚容量。

牛向汇连边,容量为 1

然后对应区间的牛棚向牛连边,容量为 1

感觉好sb的题啊。。。我更sb,居然没想到网络流的解法。

 

HDU 1534 Schedule Problem

考虑把几个约束关系用数学式子描述( s 为起始时间,v 为持续时间)

FAF: s_a + v_a \geqslant s_b + v_b \rightarrow s_a - s_b \geqslant v_b - v_a

FAS: s_a + v_a \geqslant s_b \rightarrow s_a - s_b \geqslant - v_a

SAF: s_a \geqslant s_b + v_b \rightarrow s_a - s_b \geqslant v_b

SAS: s_a \geqslant s_b \rightarrow s_a - s_b \geqslant 0

然后暴力建图最长路

注意判正环。

这题可以说很入门了 😉

 

POJ 1364 King

继续套路地把每个位置 a_i 拿出来当做“值”。

然后再套路地把前缀和搞出来 s_i = \sum_{j=1}^i{a_j}

然后题面的约束条件就成了:

s_r - s_{l-1} > ki

s_r - s_{l-1} < ki

差分约束用的是 \leqslant\geqslant 。 

那么就全转化成 A - B \leqslant C 算了。

那么就

s_{l-1} - s_r \leqslant -1-k

s_{r} - s_{l-1} \leqslant k-1

判负环。

 

POJ 1201 Intervals

首先复习一下差分约束系统建图基本知识:

  • 对于约束条件 a-b \leqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最短路,得到的是最大解。(负环无解
  • 对于约束条件 a-b \geqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最长路,得到的是最小解。(正环无解

我们来观察这个题。

尝试向差分约束去靠拢,那么观察题面,条件是

r_i - l_{i-1} \geqslant c_i

这玩意怎么来的呢? 首先我们把这个题看成“选子集”的问题(一个位置代表一个元素)

套路地,我们设 x_i 是第 i 位置的”值” ( 选中-> 1 未选中-> 0 )

套路地,我们设 s_i 是前 i 位置”值”的前缀和。

那么就可以得出以上的约束式。

并且以这样的转化,我们一定可以建立关系

0 \leqslant s_{i} - s_{i-1} \leqslant 1

这些关系已经够了。但是有个地方很不舒服,就是上面的两个 \leqslant

把式子倒过来:

s_{i} - s_{i-1} \geqslant 0

s_{i-1} - s_{i} \geqslant -1  

做完了。

注意 s_{0-1} 会爆炸所以把所有下标 +1