NanoApe's Blog

既是咸鱼又是辣鸡

GDKOI2016

NanoApe posted @ 2016年2月23日 17:40 in 蒟蒻只会玩泥巴QwQ , 906 阅读

颓了整个寒假,然后就去比赛了

Day 0

喜闻乐见,早上到了高铁站才发现自己某个斜挎包没带落在家里,身份证啊钱包啊都在里面

临时身份证明 Get√

路上无非就是打打Jubeat刷刷成绩

用笔记本打Osu,体会到了延迟的快感

到了宾馆再一次吃到了西苑特色的黑椒牛柳,然而以前吃得不错的菜貌似少了挺多

但GDKOI的伙食还是爽极

宾馆说WiFi是有的?!还是很慢啊……

然后晚上还是叫了KFC全家桶,明明最近一家KFC就100+m远仍然叫外卖送

然后几个人一边吃一边看民工漫死神

 

Day 1

早餐基本吃不饱

然后就坐着一个站两块钱的地铁跑到六中去了

去年NOIP也是在这里

准确来说在广州大部分比赛都在这里

见不到监考员Ieb

然后就入场了

 

试题密码:TheProblemIsEasy

虽然我智商快没了但对于出题人的提醒还是十分感动

T1

维护 n 个数,支持单点修改+区间询问某区间的所有子区间的异或和的和,数最多才到 1000

分位讨论,建 10 棵线段树咯

写完发现大数据4s+

想到了GDOI的无时限题目……应该能过吧

T2

嗯栽在“同个点有多个传送门如何安排顺序”

写了个30分的暴力

T3

分数规划完就不会了

一直在想割

T4

一眼插头DP,暴力分写到手

 

考完,在LSJ老司机的帮助下,才发现T3是最大权闭合图,当初学的东西刚好差这个漏洞 = =

T2在评讲的时候才发现显然的贪心安排选择顺序,排序用的比较函数就交换后的代价差

白白丢了两题 QwQ

T1由于常数问题也被后面两个测试点卡了

第一天 80+30+30+50=190 分,排名大概在 20+ 左右

 

晚上和给王去跳河城打机,顺便拿到了之前的斜挎包(给王快递,给力!)

两台Jubeat一台震键简直感动

在iPad上打太久不适应机台的大按键简直感动

经常时不时就用那小小的手掌来次失败的天按地

爽的是魔改过的机台歌多啊 =w=

最后还忘记把币还给给王

回宿舍,看了眼历届GDOI的题,昏昏欲睡

 

Day 2

早餐……

 

进了考场,诶诶诶昨天自设的配置居然还在?!电脑一夜未关

十分感动,省去了别人在看题我在打批处理的十分钟

试题密码:HopeYouCanAK!!

谢谢出题人但我的智商条件不足以AK,感动

T1

数据范围暴露出这是道傻叉状压?!

写完调过样例发现不会写暴力,那就全程静态差错吧

T2

数据范围暴露出这是道傻叉数位DP?!

对拍容易写哦爽到

T3

回文串?回文树能不能搞啊

对称项链是由一个或两个回文串连在一起的字符串

那么原串复制两倍,找回文串?

发现一算法的复杂度为$O(n*玄学)$,Fail树太深的话就变成$O(n^2)$

加了个剪枝发现全是字符 a 的数据跑得飞快?

T4

数论

最后还是搞不出来

 

评讲,T3貌似是Manacher+数据结构,$O(nlogn)$

做法都和我不一样啊,然而我怂不敢上去说水(毕竟最后成绩上最慢的那个点我才跑了0.02s)

T4的解法就是把没逆元的数单独提出来,组成一个递归函数

$$H(n,p,k)=1^{-1}+2^{-1}+3^{-1}+...+(p-1)^{-1}+(p+1)^{-1}+...+n^{-1} \pmod{p^k}$$

$$G(n,p,k)=1^{-1}+2^{-1}+3^{-1}+...+(p-1)^{-1}+p^{-1}+(p+1)^{-1}+...+n^{-1} \pmod{p^k}$$

$$G(n,p,k)=H(n,p,k)+H(n/p,p,k-1)$$

第二天 100+100+100+10=310 分

总分 190+310=500 分,排 #5

能去 APIO 和 CTSC 打酱油+面基辣!

晚上在宾馆看了点兔,感觉全身心都被治愈升华辣!

 

Day 3

早餐瞒着带队老师去KFC吃

然而想点正常汉堡,被告知要等25+mins

帕尼尼能再小点么……

车上继续点兔,妮可的声音真入戏啊

 

End

Next Station:GDOI

Time:2016.5.1

It's may be the LAST STATION. Luggage ready please.

Avatar_small
NanoApe 说:
Mar 05, 2016 05:32:12 PM

啊能看就行啦
更喜欢GitHub的风格

Avatar_small
NanoApe 说:
Mar 06, 2016 01:59:36 PM

可以……
但是不会写QwQ

hjthjthjt 说:
Mar 06, 2016 02:27:15 PM

_(:з」∠)_你要改成啥样,我会写一点点

Avatar_small
NanoApe 说:
Mar 06, 2016 04:22:45 PM

啊好看简洁就行啦_(:з」∠)_你会做么

HjtHjtHjt 说:
Mar 06, 2016 05:10:17 PM

啊像我都是自己搭建博客的¯\_(ツ)_/¯


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter