作者：党星宇

SCOI2019 游记

惊 险 刺 激 吃 四 人

Day 0

又一次来UESTC。

今年不知道为啥SCOI突然增加了笔试和面试，我一个退役选手你给我考NOI笔试就好像我能去NOI一样。

然后中午就被各种抽背，酒店门口的按摩椅还是除了一直催我“微信扫码支付”以外还是挺舒服的。

下午笔试，笔试题好多错，先是“竞赛一年“，然后又把题目改成“去年是第几届NOI”。

鼠标键盘坏了怎么办？ “将就使。”

也没什么有坑点的题，然后笔试就100了。

Day1

清晨听鸟叫。

压缩包的密码是一长串数字，不知道啥意思。

T1是个哈诺塔，大概搞了半个小时知道咋做了，然后打了一下F_i的表发现F_{30}*n有10^{23}左右，要写高精。。我觉得先把n除了再取模太麻烦了。于是用long\ double做快速乘取模，结果快速乘转long\ long的时候没加0.5，精度炸完了。最后炸成暴力分，只有50。

T2开始傻逼了一会儿，然后发现自己只会暴力边分主席树，我觉得边分有点难写，写的链剖主席树，然后再拿线段树维护一下答案，20分钟就写完了，基本没调就过了样例。最后开的T2，想着要去检查T1就没去写链。出来知道了怎么一个log，贼难写，还好我考试的时候不会。

T3以为是道神题，就开始想怎么暴力。出来后听魏精讲了就会了，标算应该是Min25筛，他写的线性筛过了。

估分100+60+50=210

实际50+60+0=110。

T3 无 端 爆 零，炸成一匹野马，全场rank 30+，当时觉得自己一定退役了。

面试问的是“如何看点成都七中实验学校的食堂食品安全问题”，随便瞎说了点东西，得了我们那一组最高分可还行。

晚上开始在酒店里思考人生，被林先生约谈了，心情稍微好了一点。

Day2

发现水从小瓶农夫山泉升级成大瓶怡宝了。

压缩包的密码还是一长串无意义数字。

T1看错了3次题，手动三倍加强。还好每次做不动了就看了一遍题，然后读题之后，发现题目要求就正好是自己想要的东西，不到一个小时过了大样例。

T2，这不是十二省联考hope一倍役满？省选出今年省选原题弱化版可还行。10分钟就写完了。

T3，淦了3.5h，还是不会，暴力走人。

还好中途拍了一下T1，调出来一个错。测了一组大数据发现没开long long。

下午出分发现没挂题，居然还是今天的rank 1，然后就。。。翻盘了？还翻进了A队。。。

 

也算有过真切的退役感受了。

大家NOI见。

 

校园的黄昏里

池塘的倒影里的很大

走下去，就能用池水清洗年华

在群山中回绕的钟声下

广府的风啊

是一人孤独凝望的晚霞

是布满繁星却漆黑一片的德令哈

是凝聚成掌心柠檬的白蜡

好久不见了，你还好吗？

Day -2

广二集训。。。

每天一道码农题。

哈哈我会做。

$fst$警告。

天天被吊打。

获得成就，11k特判。

继续阅读

本文讨论了两个关于square factor的趣题。

首先介绍一下square-free number（虽然和下面的内容没有什么关系）

我们称一个数是square-free的，当且仅当它没有平方因子（关于平方因子的定义在$Part\ I$中）

我们用$S(n)$表示$1$到$n$的square-free number的个数，有它的渐进式

$$
\lim_{n\rightarrow \infty} S(n)=\frac{6}{\pi^2}n+O(\sqrt{n})
$$

如果广义黎曼猜想成立，我们可以进一步减小误差：
$$
S(n)=\frac{6}{\pi^2}n+O(n^{17/54+\epsilon})
$$

继续阅读

NOIP考前集训，成绩起起伏伏，有一些题没改。

集训的时候，经常写挂，导致NOIP考完之后非常慌。

NOIP考试时心态也不是很好，写代码和想题效率低下，导致Day2T2时间不够。

继续阅读

顺为凡，逆为仙，只在其中颠倒颠

《无根树》张三丰

继续阅读

你的名字

Solution

由于水平有限，笔者对于后缀自动机的应用知之甚少。

这道题作为一道经典的后缀自动机题目，对于诸如笔者的后缀自动机初学者对于后缀自动机的认识有很大帮助。

继续阅读

取石子游戏

Solution

由于本人水平极低，所以觉得此题难死了。 通过看题解不难发现，对于一段区间$[L,R]$，若$L+1$ 到$R$每堆石子个数确定，那么使得这段区间上先手必败的$a[l]$有且只有一个。 证明非常的容易。首先假设没有先手必败的$a[L]$，那么所有的必胜态都会到一个必胜态，显然是不可能的。如果有$\geq 2$个必败态，考虑其中任意两个$x,y,x>y$，那么先手显然可以把$x$取成$y$，那么$x$就是一个必胜态。矛盾。 于是，我们定义$left[i][j]$表示在$[L,R]$区间左边添多少个变成一个必败态，$right[i][j]$表示在右边添多少个。那么答案就是$left[2][n]!=a[1]$。现在考虑如何求$left[l][r]$。设$L=left[l][r-1],R=right[l][r-1],X=a[r]$我们可以分以下几种情况讨论。 继续阅读

An unavoidable detour for home

Solution

由最短路唯一，不难发现以下性质：

1、原图可以通过对于$1$号点的最短路长度分层，成一棵树的形式，每一层的最短路长度相同。

2、剩下的边只能在树的同层内的点加。

3、由于要求对于$i>j$有$dis_i>dis_j$，所以每一层是一段区间。

于是，我们就可以$DP$了。显然有一个暴力的做法，$f[i][pre_1][pre_2][now_1][now_2]$表示上一层剩下的度数为$1$的点有$pre_1$个，度数为$2$的点有$pre_2$个。这一层的对应分别有$now_1,now_2$个。转移讨论一下$i$号点的连边情况。当$pre_1=pre_2=0$时，这一层就填完了，该填到下一层。

显然是可以通过预处理同层里的方案数直接每层转移。注意到度数为$2$的点的方案数要提前除$2$。

同时注意到，数据范围只有$50$，所以好写$n^5$暴力就可以愉快通过了。真好写

本文是一些关于黎曼$\zeta$函数的简单有趣的介绍。
里面有很多公式都打错了，您就当看着玩。

继续阅读