NOIP2018真香记

~~于day0:由于不知道考试结果，所以标题先不填。~~ 于day1:貌似可以填“嗨翻” 于day2:貌似可以填“真香” 想要题解?没了!真香! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # 基本资料 | 项　 | 信息 | | -----------: | -----------: | | 坐标　| GD | | (当时)年级　 | 初二 | | level　 | 提高 | | 性别　 | 男 | | 名字颜色　 | 假红色 | -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # Day0 早上翘课在家睡到11点，坐上面包车一路摇摆来到了**广州二中**附近的**万达**~~某公寓~~。 房间号是$2^{10}=1024$ ! 下午步行3km去二中(广州二中)考场探路，回来之后大吃了一顿**McDonald**。 ------------ 万达楼下举办了一个“**跨界**歌手选拔赛”，我们回来的时候正赶上主持人念开场词：“欢迎各位参加**复赛**的选手们……”~~我差点上去给他来一首《膜你抄》~~。 结果就是听着各种杂七杂八的~~五音不全的~~歌曲写代码复习。 混响效果真的好！！！ 那些神仙还一直唱到了**10:30**！！！ 还有一个疯狂破音，~~把附近停的车都震得叽哇乱叫~~！！！ 都day0了还[有人](https://www.luogu.org/space/show?uid=149747)在luogu卡评测(整整卡了2000发)，搞得我没能好好复习~~(借口)~~ ~~我从未见过……~~ ~~day0居然没有颓废，还现场学了KMP~~ **Went to Sleep At 23:30** -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # Day1 **Got up at 06:35**(~~在学校又不见得你起那么早~~) 昨晚没太睡好，所以今天宜睡觉？ ~~隔壁大佬宜考试，怕是要AK~~ 老师说7:50走，所以疯狂复习。 ------------ 去考场的路上立了个**flag**：**T1=30min; T2=1h; T3=2H** 到达考场，解压密码好像是**飞雪连天**？ 拿出题一看，T1**原题**(事后发现,是**NOIP**2013原题)??? T2不是完全背包么??? T3看不出来。 10min切掉T1(~~差点忘了测试大样例~~) T2完全背包n次的话，复杂度$O(TN^2M)$感觉过不了,推敲一段之后发现了$O(TNM)$的做法(类似筛法)。 200分到手,省一稳辣！~~€€£万岁！~~ T3想了半天,一看到最小值最大就想了**二分**,想出了$O(NM)$的DP但是不想打,部分分也不想水。 后来想了45min终于想到一个靠谱的**贪心**,~~老是忘记自己是在写二分的check~~,性质证明消耗太多时间。 打了到还剩1h的时候过了小样例！ 大样例测一发！**WA！** ~~真的吓出一身冷汗……~~ 调了半天,发现节点合并的贪心是错的,没时间证性质了,内心凉凉。 后来想到了一个复杂度玄学的做法~~理论上能卡到平方~~但是大样例跑的飞快!**上善若水**!就是它了! (复杂度分析具体见题解区) ~~咱们赌5毛出题人没想过这个做法,不会出数据卡~~ 最后20min检查。 ------------ ~~二中的饭真好吃!~~ 石中一堆大佬AK,~~俺T3贪心被怒斥~~ 回来的路上看到一堆**杨超越粉**,膜拜并吸取RP。 才发现万达楼下并不是那么简单,露天舞台没有撤走,反而又有一批人登台唱戏? 发现从“**跨界**歌手选拔赛”变成了“小小主持人`!#%^*&`”(忘了)。 铁打的舞台,流水的活动? (汗 luogu居然闪电般出了自测!!! T1+T2=10min,A掉 T3回忆了1h,样例老是不过……后来发现贪心忘记排序了…… ### 一发A了!!!  美滋滋~ ------------ 晚餐照例是一顿**McDonald**。 晚上换成了来自少年宫的~~重金属~~乐队,电吉他声震十里,架子鼓陪《**逆战**》洗脑循环五次以上…… 复习了一晚上**字符串**算法。 写着代码突然**停电**了? 听说有人被困在电梯里。 ~~于是开始颓扫雷~~ **Went to Sleep At 23:30** -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # Day2 **Got up at 06:40** 早上有点困,起晚了五分钟。 去考场的路上又立了个**flag**：省一线350。 到达考场，解压密码好像是**笑书神侠**？ “飞雪连天射白鹿,笑书神侠倚碧鸳”! 默哀,江湖仍在,永失金庸。 ~~话说没人猜出来密码吗?~~ 拿出题一看，T1**基环树**。 45min才切掉。(太菜啦 T2提面什么鬼?看不出来,猜测是状压DP。 看了一眼T3~~,一口老血~~ 动态DP? 树链剖分? 模板黑题? 果断暴力44’走人。 T2状压搞了1.5h**不过样例**,最后打了个$n,m<=3$的表,然后搞了$n==2$的规律。 T3卡了卡常数,简单结束。 ------------ 考完了?考完了。 ~~AFO?~~ 二中的饭老味道,~~不过要20元~~。 听着大佬讲T2是**小学奥数**? 没考字符串啊啊啊~ 坐地铁回家,2h。 在家写luogu自测,T120min, T3写了超多bug,感觉考场上面的那份要凉…… T2采用大佬的方法骗了65’,感觉剪枝+打表能A?  %%%各位AK大佬!!! **估分450。** -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ # 后记 过去啦……备**期中考**去也。 GDKOI见! Winter Camp见! (考场程序洛谷自测500,美滋滋)