TYOI 省选集训 and 2024 GD 省选游记
TYOI 省选集训 and 2024 GD 省选游记
集训
Day -INF
知道可以来集训，感觉特别开心，因为可以合法逃学两周！
Day -3 \(\sim\) Day 0
大年初五就从潮州回到广州，收拾了一下东西，年初七大家就到了学校。
很好，又和高中生一起住，不过这次我们来得很早，所以高二还没有开学。一开始宿舍里面只有我、includeCPP、jr_linys 三个人。所以 includeCPP 非常放纵。
Day 1 \(\sim\) Day 17
每天都是比赛，每天都爆零。不过 Day 17 有奶茶，还有一帮 D 班 xxs 家长过来参观。当时我们在打球，真的好尴尬。
虽然每天都爆零，但是还是改出来了几题，
。
比赛
Day 0
中午出发，下午 \(2\) 点左右就到了。开始试机，简单打了一个 Dijkstra，运行正常。然后又写了一个经典的 dlt 代码，一坤秒电脑就黑屏了，闪了一下正常了。感觉松山湖电脑性能很好，准备在虚拟机里面打题。但是 VSCode 不装 CPP 插件真的是只有 CCF 干得出来。没办法，打算用 vim。有一说一， vim 的手感是真的很好，高速输入的时候几乎感觉不到一点延迟。
试机完出来才知道原来 NOI Linux 里面的 Sublime Text 是有自动补全的，于是决定赛时用 Sublime。
试机之后，回到熟悉的 klyd 酒店，一起看超脑少年团第二季，ljy 没加大 Y 是真的很搞笑~
晚上请 sly 帮忙点了外卖，感觉还行。
Day 1
T1
一眼二分，考虑如何 check。很容易发现，原式可以这样化简：
\[
\begin{align}
\sum_{i=0}^{m-1}\left(x_{i}^{\prime}+x_{i \! \mod \! n}\right) &= x
\newline
\sum_{i=0}^{m-1}x_{i}^{\prime}+ \sum_{i=0}^{m-1} x_{i \! \mod \!
n}&= x \newline
\sum_{i=0}^{m-1}x_{i}^{\prime} &= x - \sum_{i=0}^{m-1}x_{i \! \mod
\! n}
\end{align}
\] 又因为 \(x_{i}^{\prime}\)
是实数，于是： \[
x_{i}^{\prime}= \frac{\left|x - \displaystyle\sum_{i=0}^{m-1}x_{i \!
\mod \! n}\right|}{m}
\] 因此我们可以用此判断是否合法，对于 \(y\)，也可以如法炮制。
先是写了一个 \(\mathcal{O}(m)\) 的
check()，测样例需要很长时间。想了一会突然发现可以预处理整个数列的和，然后用
\(\mathcal {O}(n\, \%\, m)\)
的时间就可以统计出答案。但是发现即使这样可无法通过样例。因为 C++ 的
double 精度不够，改成 long double
就可以通过小样例。但是如果你测试大样例，仍然无法通过。
我们考虑将实数转化为整数。我们可以讲不等式左右两边同乘 \(m\)，如下： \[
\begin{align}
\frac{\left|x - \displaystyle\sum_{i=0}^{m-1}x_{i \! \mod \!
n}\right|}{m} &\leq k \newline
{\left|x - \displaystyle\sum_{i=0}^{m-1}x_{i \! \mod \! n}\right|}
&\leq km
\end{align}
\] 然后我们用 __int128
存一下就可以通过样例。然后你就可以通过样例。但是如果你测试大样例，仍然无法通过。赛时的我以为是没有特判
\(k = 0\)
的情况。特判之后仍然调不出来，摆了。
赛后才知道原来是解一下那个不等式，wssb。
T2
不会，随便打了暴力。
T3
SB 出题人，题目看不懂，摆了。
Day 2
T1
不会，打了一个暴力，拿下 \(25 \rm pts\)。
T2 & T3
不会，摆了 (o_ _)ﾉ。
赛后
mod 剑神 rk. 6，飞神 rk. 20。