JXOI 2018滚粗记

--Update5.2 成绩出了,见后文

听说省选VAN写游记是传统,本蒟蒻也来发一篇吧。

  • DAY 0

    本来以为省选不在JKFZ举行的结果又是在JKFZ,本校作战感觉终究会是好一些吧,和jyh一起向教父申请停了一天的课,没想到教父居然笑眯眯地答应了,有点出乎意料。

    上午和jyh一起打了yjw学长Yali集训时的模拟赛,T1线段树,T2。。。 T3。。。然后愉快地打了线段树,结果。。。爆0。

    中午吃完后dalao jyh讲了他T3思路,总之感觉很厉害。

    下午dalao jyh写出T3果然是满分,orz。然后被教练拉去和yjw谈一谈赛前经验,然后莫名其妙就变成模拟赛题解讲解,原来T1爆0原因是因为&和|运算不能简单地只是打个标记,我还是naive了。

    晚上终于回家了,随便打了下模板,本来想开CSGO,结果偷偷玩了几把混乱大枪战后就睡了。

  • DAY 1

    早上坐车来到JKFZ,打了几遍数论相关模板,连莫比乌斯这种不太会考的都打了一遍。

    然而。。。

    和jyh一起取考场的时候总是有些奇怪,但还算释然。上机试了下机子,除了键盘有些不适应之外还好没什么问题(一想到NOIP时机子打不开T盘就觉得好笑)。不久题目发了下来。

    第一眼看到题面,九条可怜?woc又是吉如一出题。把全部PDF浏览后开始做T1,T1一开始看不懂在草稿纸上推了一遍后却觉得思路还挺容易。

    T1大致题面:他先告诉你一个叫gobo sort的排序方法:对于一个成为n的序列a,随机生成另一个长为n序列p,然后构造一个长为n的序列b,使得(b_i) (=) (a_{p_i})。假如这个b是有序的,则停止操作,排序完成,反之不断重复生成p序列的操作.

    然后给你一个长为n的序列,和m,l,r。要求你在n长的序列后接上m个值域为[l,r]的数,使得gobo sort中随机生成序列的期望次数最多。

    草稿纸上搞了一下发现你只要让每个数字出现的次数平均就好了。具体怎么算这里不再赘述,然而在考场上我发现有几个地方需要注意:

    1. 离散化 2.可以用堆维护 3.由于有阶乘,除和取模操作,需要逆元.

    然而蛋疼的是我忘了逆元怎么打!!!在考场上手推好久,只得作罢,去做T2 T3

    T2打了暴力,T3连暴力都不知道怎么打...

    总之出了考场后很颓废,T1没打逆元,什么优化也没加,估计凉凉。

    然后下午yjw学长搞来份solution,看了一下T1思路确时没错,T2用sigma推了一大堆结果时间复杂度只有O(r)?T3区间DP,好难根本想不到。

    后面看了下逆元,发现原来这么容易求,考场上用费马小定理却没推出来...还是我太弱了。

  • DAY 懒得数了

    五一节后成绩出来了,居然有50分,我想应该是T1 30+T2 20+T3 0瞄了一眼大多都是这个分段,然而我的NOIP只有120,前面都是200+或300+,我还是太蒻了,学长进了A类,不过有一个赣州中学高一省队爷,真的强...以及一位爆0 A队女选手。

    然后在知乎上看到这个:

    厚颜无耻的出题人 %%%

  • 后记

    总之还是意料之中吧,也恰恰反映我的不足,以后还是要多刷题,坚持在NOIP前一月把算法竞赛进阶指南刷完,(现在看怕是没机会了)争取考400+(这么弱怎么可能)

    总之应用一句在其他dalao滚粗记中的话吧:

    一个人的命运啊,当然要靠自我奋斗,但是也要考虑到历史的行程 。 ——长者

原文地址:https://www.cnblogs.com/Rye-Catcher/p/8971004.html