JSOI2015 分组赛记

分组赛结束了,虽然跟我关系不大,但是去了还是学到了不少东西

day1 上午报到,在宾馆遇到大神wzy,orz

好像没有参赛证发了,于是给我发了一个【工作证】,233我是工作人员了,高贵冷艳

下午是常中的大神xy讲课,是world final的题,前两题都是做过的题,后面的题没做过就没太听懂……

晚上是wy大神讲课,wy大神今年参加了WF2015拿到银牌orz。晚上讲的是凸包相关

观察了一下wy大神平均5min喝一次水(大雾),感觉晚上的内容还是相对简单,当然点、线段与凸包的问题并没有搞太清楚

这次在刘长兴吃特别坑爹,小笼包等了好久最后是催上来的(似乎把我忘了),……以前从没有发生过……

day 2上午依然是wy大神讲课,讲的是跟凸包相关的一些问题

感觉收获还是蛮多的,学了最小乘积树模型,感觉像这样的题用计算几何做好神奇

下午是wzk大神讲课,讲的是构造题,我这种智商当然是从头被虐到尾啦……

事实的真相是我并没有怎么听,因为下午有百度之星……

其实我本来是不打算参加的,可zxy用我的号看题,写了一道1003,然后用我的号交了……于是我就被带入坑了

而且1003也没有过,因为1003是道坑爹题,xyz大爷也被坑了好久

结果我这么弱,bc掉下黄名了T T

晚上没有事情,因为明天要考试

day3 考试啦考试啦,然而我比较困,所以感觉要挂掉了……看题

T1 贪心?乱搞?

T2 我只会60分暴力,随机看起来比较神的样子

T3 我想到了3514……

先写了60分暴力玩玩,然后写了T1贪心,一度感觉很靠谱(智商下线)

然后看了看T3,感觉和3514应该差不多,估摸着是lct+主席树,然而不知道怎么搞(智商再次下线)

于是再回过头来看T1,md,贪心错误不是很明显吗?

又胡乱想想网络流,感觉不能搞……于是写了个贪心+随机化

闷声滚大粗……

下午是先讲课,然后晚上再讲题+复测

下午还是wzk的构造题,认真听了一下,感觉好有意思

跟着玩了一道题,构造1到N期望路径大于10^6的图,真的很有意思

……不过感觉我的交流能力严重退步……

晚上zz,zyh,oyff跑老远去吃麦当劳,我机智的没去,先看到了成绩:

30+60+20=110 滚蛋,第一题混到30还是不错的。正解区间dp,其实还是非常好想,但很多人包括我现场都没有想出来……

更坑爹的这TMD是CERC的原题,MD,又想起R3 d2 t2也是CERC的原题,MD出题人你节操呢?

第二题好像只有zl大神过了,方法没太听懂

第三题就是和3514类似的做法,考试这都想不出来简直是拉低OIer的平均智商……

听oyff说T3是长郡镇海中学联考的题(UPD:现在发现又是CERC的原题)……掀桌,出题人你能不弄原题吗?

不过这场似乎有些省队爷考挂了,我竟然排在了Rank 14左右……

day4 上午原创题答辩,每个人的都记不大清楚了,具体记得这么几个印象深刻场景

1. 第一个上去的zzj弄了个生成函数吓傻了,本以为只有浙江人才喜欢搞这东西,是不是Au爷都喜欢搞这种东西(感觉noi根本不会考……)

2. zxy的原创题被zzj发现是集训队作业的某道题……大囧

3. hrz的原创题……………………真是能乱搞

4. 数学省队dlh就是厉害,从数学集训队作业(UPD:罗马尼亚数学国家队选拔赛的题,orz)里出了道题到OI上……

5. zl好神,wrh讲完后zl立刻跳上出讲了另一个方法

6.oyff和zyh下了好长时间棋……

下午是wyt讲课,感觉最喜欢听wyt讲课了,感觉特别长知识,而且听得也非常清楚

顺便明天把APIO2015做完吧……

day5 最后一天了,反正考试和我并没有什么关系,随便考啦

T1 感觉暴力就能过?

T2 感觉是道SB数据结构

T3 这是什么玩意?

先想T2,感觉没有想象中的那么简单,想了半天并没有想到log的复杂度

于是感觉T1 暴力kmp就能过,于是先写T1冷静一下

码了一会过了样例,然后发现7组数据需要剪枝,于是又剪了剪枝,这下就跑得飞快

然后我自己随便造了几个数据,duang的一声,wa了……

心中顿时一惊:好像不能这样暴力判定……感觉头大了

这时候应该冷静下来想想正确的判定怎么做,但是我太SB,浪费了不少时间

静了静看看T2,造了几个数据发现中位数要么不变要么+1,于是想到了O(nsqrt(n)*log(sqrt(n)))的分块大法

码了一下发现超级卡,连40都过不去,于是调了调常数,最终40%的数据稳定在1.3s左右出解

然而100%的数据要跑6s,实在无能为力

还剩1h看t3,卧槽n<=20连最弱的部分分都不知道怎么做……随便yy个模拟退火好了

(仔细想想今年jsoi出题人是不知道部分是什么啊?省选一系列比赛部分分都给的很少,不是A就是20~30分,分差特别容易拉开

像今天T2 50000的数据好歹应该给到60啊)

然后分析了一下T1,在n比较小时还是不容易出错的,感觉还能能拿一点分……

于是结束了……

出来zsa说:我感觉你们都能A掉两题,玛雅……

zsa说他A了第一题,其实一开始我是不信的,因为他昨天也说他能A第一题,但爆了

结果,zsa今天真是A了第一题,而且是只有他一个人……竟然这么靠谱orzorz

然而很可惜,由于最后三个点数据给大(jsoi数据怎么又出问题了……),导致重造数据重测,zsa就变成90了,然而就有多个人A了

因为在讲解的时候zl跳上去指出zsa dp检验的错误——也是错误的算法啊……不过拿到这么多分甚至一度AC还是不错的

zl大神今天怒A t1,t3 rank1实在太凶,orz

然而我这个蒟蒻只有60+40+0=100……最后一题退火次数少了导致少拿了分……

不过似乎和d1一样,好些人挂了?

最终还是结束了,A队爷:zzj,ywq,wzy,zl 无限ym orz

何时才能这么神?何时才能考场上不SB呢?

加油!离NOI还有一个多月!还没有结束!

原文地址:https://www.cnblogs.com/phile/p/4564031.html