JSOI 2017 ROUND2 游记

Author Avatar
dozbear 5月 04, 2017
  • 在其它设备中阅读本文章

各种惨啊

DAY -1

各种颓,不知所措

打了几个板子

DAY 0

报道

没有饭票很奇怪啊,名牌上没有编号很奇怪啊

下午本校神犇 ywq 讲课,构造啥的完全听不懂啊

大力接着打板子

跑过来一群人各种奶我……所以最后挂了啊?

DAY 1

早上起床好困,感觉要萎

打开题面

第一题,一看就像 \(\Theta(wys)\) 的样子,\(n^2\) 但是不好卡

那么把出度很大的点拎出来单独跑算了,卡了卡发现卡不掉

很棒棒啊

第二题,一看就很不可做的样子。想了想插头 DP 还是放弃了,手残写不出来,果断暴力骗分

第三题,每次加一定加在最小割上。什么,加的可以是实数?

??????????这咋做

出考场大爷们说只有最后一次加的是实数,很有道理,智力-=100

下午讲课集训队作业水题选讲,大力肝板子

哎没带电脑怎么办

突然来了一些 yjz csl,于是就开始颓游戏,滚动的天空、几何冲刺和duet 话说yjz手速真的快啊

然后紧张刺激的看成绩

哎第一题怎么爆了啊

合并答案的时候有的地方不用 /3 手残了,成绩 -= 70

为什么会变成这样呢……

突然发现对拍的时候随机的数据没有出度大的点连向出度小的点,boom

其余两题都是暴力分

出来一看张神120,原来第一题暴力就有80

悲剧啊准备退役了啊

DAY 2

早上起床更困了看题头晕眼花啊

大力开题

第一题后缀自动机板子题?大力码码码,对拍没问题

第二题smg,好像是贪心的策略是什么的感觉完全做不了啊

大力码码码出了一个 \(\Theta(nq \log n)\) 的贪心骗个 \(q=0\) 和 \(n\le200\) 的骗个40

第三题smg,大力推推推,求出gcd之后从最后的操作后往前扫?

找找规律除完gcd之后答案 \(k=0\) 都是 \(n+m-1\) 啥的,分成几段

码起来,woc细节好多

中途忽然想到第二题似乎是对每个事件和人的组合 计划先取的人向计划后取的人连边然后LCT搞搞维护独立集啥的,一看就码不出来

然后第三题细节太多码不动弃疗啊

woc只剩一个小时了,检查一波第一题好像没啥问题(flag++)

第二题……哎我的贪心策略是错的啊,怎么办只剩半小时了

大力码码码码出了一个新的贪心

woc只剩五分钟了,检查一波文件

总觉得这场标准分 240

出考场和神犇们一聊,woc 第一题写的是错的,有可能多 copy 一个的代价还不如打一个新的,其实更新的时候用个线段树就好了……

为什么这么强的限制我都想不出来TAT

第二题似乎被卡常?也 GG 了啊

第三题似乎没什么问题(暴力哎)

中午去 nfls 隔壁刘长兴吃饭,小笼包味道不错……但是吃的一点胃口都没有……被送退役啊TAT

出成绩一看第一题除了暴力全爆了

惨惨惨

张神稳进队啦

结果过一会儿学校老师过来说我也进了,真·守门员

rua!

神 tm 狗血剧情

还是代码能力要增强啊,还有早上精神好才能打比赛

UPD:

D1T1 把出度 \(\ge \sqrt{n}\) 的点单独拿出来跑是严格 \(\Theta(n \sqrt{n})\) 的

详见 BZOJ 3498 三元环

本作品采用 CC BY-NC-SA 4.0 Unported 进行许可
本文链接:https://dozbear.com/jsoi-2017-round2-notes/