Day0

以下皆为废话各位可以跳过

在学校

早上在学校机房调了一下前一天剩下的题,感觉打得很对&&和题解说的就是一个东西,但是就是不对(好吧我的日常:嘴巴AC一下,打出来就萎了)。然后经过一番折腾发现因数分解挂了,线性筛求最大素因子我是这么打的

void pre()
		{
			for(int i=2;i<=10000000;i++)
			{
				if(!flag[i])prime[++primes]=i;
				unsigned long long v=i*prime[1];
				for(int j=1;j<=primes&&v<=10000000;j++,v=i*prime[j])
				{
					flag[v]=true;
					if(i%prime[j]==0)
					{
						fct[i]=prime[j];//嘻嘻,完全没考虑到fct[i]*i>1e7的情况,于是成功只筛出来一部分数的因数
						break;
					}
				}
			}
		}
		

发现问题之后和ViXbob讨论了一下(其实是请教ViXbob数学巨巨),发现我连线性筛都不会了😭。调过那组数据后就没测了,不想面对爆零的事实啊。
后来和机房众人一起打板子,顺便orz切ZJOI2019麻将的巨巨Wepdekr。ViXbob成功成为小黄鸭(小黄鸭调试法真棒!),打了什么板子记不清了,但似乎我打一个错一个。

下午难得睡了个午觉,醒来继续打板子、观摩小黄鸭调试法、观摩Edt巨巨打了一发我一直不会的2-SAT(2-SAT我开了3题,一题没调出来)。大家时不时呼唤着去试机,不过教练一直都没来说试机的事儿,就拖到了约莫16时才出发。

试机

试机向来是面基的好时机,虽然我从未面过基,但Edgration和ViXbob两位红太阳应该要受到膜拜的吧。
路上Zechariah和本校另一位巨巨因为一辆出租车坐不下惨遭抛弃qwq。
试机的时候

Day1

考场上

打开题目,T1暴力很好想到也比较好打,枚举区间、通过异或前缀和得到区间和即可,然后就是关于暴力的优化了。考场上脑子不太清醒,yy了一种复杂度非常不对的并行dfs方法,当时还以为复杂度是$O(klog)$级别的,考完出来后发觉非常不对,但心态平稳(关于心态,看官们可以移步我的退役感言)。尽管方法不对,我还是打了近2h才调过几个样例。当时预计得分100pts(瞧这愚蠢的我)。

此时开始看T2,题目老长,读了10+min才读懂(题读不懂千万不要慌,多读几遍就明白了)。看到支配关系、长度、无限长这几个信息发现需要根据前缀关系建图,就想到了朴素的暴力:枚举ab串判前缀关系,建图后先判环再topsort求最长路,于是火速开打SA!天知道我怎么想的,$O(n^2)$的方法跑去打SA,直接哈希多好啊,怕不是学SA学傻了。顺利打挂板子,调了1+h终于调过所有样例。预计得分40pts。
暴力打完之后开始思考复杂度优秀的暴力,莫名想起[NOI2018你的名字],yy了一种优秀的方法:
根据原串建出SAM,parent树上倍增找到每个A串对应的状态点,将对应的A串记录到状态点上去,然后可持久化线段树合并处理endpos集合,在有对应B串的状态点处即可得到每个B串是那些A串的前缀,这样在可持久化线段树上建边、再将对应点连向A串即可优化建图,建图复杂度大概是$O(nlog^2n)$吧。但是这种东西显然不可打啊,即使我开了挂,大约300+行的代码不是1h能打出来的,于是放弃。

最后还剩40min时开始看T3,真实《他改变了传统题》系列。
第1,2,3个点看了一遍,结合编号名称明白要求的就是$19^k\pmod{998244353}$,搞了5+min拿到12pts。
第4,5个点大概知道要干啥,但感觉不好打于是跳过。
第6,7个点一看编号名以及数据中的负数,明白是爆int了,但快速幂怎么改都有些爆负的地方和答案不一样。于是开始怀疑是不是需要暴力算,试了一下果真如此。但复杂度$O(n)$显然没法过#7啊,yy了半天还是不会优化,索性跳过。 此时还剩大约20min。
打开第8,9,10个点,一看名称中有字符,样例数据中的串似乎有些神奇间隔、重复的规律,就开始找规律。想过的可能有:以某种规律生成一个指定长度的序列(但第二组询问显然不符)、将某未知串的一部分循环若干次得到输出(这个也找不到规律)。就莫名其妙yy了10min,还剩10min时放弃。
又回到#4,迅速打了个暴力枚举模数的程序,跑第一组大询问跑出个模数,用它跑第二组询问得到的结果又不一样,心态有点不稳,于是用两个询问一起判模数。可能是枚举下界设大了,跑到考试结束大约1e14的范围内还是没找到模数。

考场外

刚出考场和本校巨巨wty(人称SAM爷)交谈两句,讲了一下我那个巨复杂的思路,突然灵感迸发,想到直接把SAM上的边建出来就好。这大概就是小黄鸭调试法的魔力吧qwq。心情有点激动,经过交流发现这样只有80pts,不过也很高了,有点亏啊。
吃饭路上得知Edt巨巨T1和我想到了一样的方法,但因为复杂度非常不对于是没打,我觉得T1我只有40pts,但大家纷纷表示出题人不卡可能就过了。
Edt大量时间用来刚T1,ViXbob大量时间用来刚T3,即使这样ViXbob最后1.5h直接爆切T1,T2拿了40pts,真的是太强了!

结果与讲评

咕咕咕是常态了,说是14:30,结果工作人员表示要咕到15:00+,最终又比15:00提前一些开始讲评。
讲评细节不表,反正当时没听懂,就浏览了一下ppt。
后来T2因为数据范围有点问题重测,虽然要求重测的选手是真的打挂了qwq。
Day1实际得分100+0+18。

T1还是要有梦想啊(虽然我是算错了复杂度,不然真的不敢打)。
T2忘记清零DAG求最长路的点权数组和dp数组,真实再现$$数据千万条,清空第一条。\\多测不清空,爆零两行泪。$$ T3没什么意料外的,就是正解真的把我整得一愣一愣的。果然还是不会找规律啊。
如果去除混的分、加上打挂的分,应该有98pts,还算大众分吧。T1用脚造数据(估计真没想到这么暴力的暴力)我也很无奈啊。

Day2

考前

路上思考了一些关于oi生涯的事情,有些茫然有些伤感,不过心态平稳。

考场上

T1看到题目名“皮配”就想起去年的劈配,看到两条关于权值和的限制以为真要考网络流,不过很快发现是计数题(Orz Edgration&&ViXbob昨天一口奶中)。
粗略想了想暴力,暂且感觉有个$O(4^n)$枚举的20pts。
开始研究递推,首先想到f[i][Y][r][Z][R]表示考虑到第i所学校,四个导师的选手分别为....的方案数,紧接着想到可以用$\sum s_i$优化掉一维状态,此法复杂度$O(nm^3)$,应该有30pts。
继续优化状态,用f[i][Yr][YZ]表示考虑到第i所学校,Y+r选手数、Y+Z选手数为多少的方案数,因为知道$\sum s_i$,所以可以分别对应地求得Z+R、r+R,此法复杂度$O(nm^2)$,以为卡一卡能有80pts。
为了稳妥我决定先打30pts的,结果打了2h没打出来,有点炸裂,打了个10pts(n=1)的就溜了(也许还打错了?)。

T2看题的时候有些急躁,脑子里有点乱,不过恢复了一下之后看懂了。观察到它是一颗树的形态,就想到可能需要递归求解、合并答案;又发现一个根节点的子树和子树之间不会产生冲突(即可以复用一部分内存段),进而想到用堆维护内存段大小、再怎么合并一下。觉得直接对第k大的内存段取max好像可以操作,然后就在纸上画了一会儿,虽然不太严谨,但基本觉得合并两条链时就是这么回事儿,为了混分就匆忙打了一发$O(n^2logn)$的75pts暴力。
后来看到有一条链的情况,为了稳妥特判掉了这档部分分,感觉至少这15pts稳了。

看了看T3,十分不可做的样子,于是回去打T1。
那30pts感觉打不动了,就去打50~80pts的暴力。在纸上把相关限制不等式以及变量别名列出来后,比较顺利地20min打出来了(喵喵喵?前2h在干嘛?)输出调试大约10+min过了小样例,结果一测大样例瞬萎,心里又有些懵逼了。输出调试半天发现根本不可调,于是魔改程序,计算只考虑第一个城市的方案(这样非常可调啊),调了一会儿发现非常正确。就在我滚动鼠标的一瞬,突然看见求答案时用错了变量,恍然大悟,终于过掉两个大样例。此时还剩20+min。为了多混点分,我把数组改成了1000*1000的,以为运气好有80pts。

T3直接看部分分,先觉得l=n可做,但我只会算一定包含某一个点的方案数,这样计算似乎需要容斥,遂放弃;又觉得k=1可做,yy了一发$O(n^2)$的计数方法,但看起来时间不够,遂放弃;最后还有8min去打$O(n2^n)$方法,应该有8~16pts,结果还剩2min时连求直径都没调出来,遂放弃。

考场外

和同学一交流,大家纷纷假了起来,说什么我155pts吊打全场。一问才知道ViXbob今天专注打暴力,Edgration今天跑去刚T3,好吧分数都不太理想。电梯上一本地老哥讲述了T2“取出来再zhou(上声)回去”的方法,有人和我方法差不多也许我是对的?但还是很伪的样子,就当15pts算吧。
吃完饭我想起来T1大样例好像要跑很久,和ViXbob交流后想起有多组数据,凉凉。

结果与讲评

讲评听不懂,9k的std和3k+的验题程序都向我甩来三个字:不可做。 分数看到后很有点惊讶,30+60比最坏预期高了一些,但T1只有30很不爽,T2的60分估计就是链的情况打挂了。。。不作死就不会死。。。
看起来Edt很可能进不了队了,ViXbob其实也被其他巨佬们翻盘了呢,李队的称号估计是没了。
说起来以后机房可能就只剩下ViXbob了,也挺孤单啊,但一个人也许就不会颓,希望ViXbob能拿到我校首块金牌吧。

总结

最理想情况下分数应该是day1:100+40+18,day2:50+75+0,总共283pts,这样也许就能进我省rank前8了吧,虽然我一心退役。

退役之战我应该算是脑子比较在线,时间分配说不上合理倒也没去赌某一道题,因为马上就退役了所以心态比较稳定,没有因为其他人的种种ak假象而心态炸裂,但是细节挂了好多有些遗憾。

也算是留下一些教训吧:

退役之战算是证明了我不比各位大佬差太多吧,虽然是混分选手,但大众分还是会的。
以后要回去学文化课了,也不知享受生活的小目标能实现多少呢。