HNOI2018思记

4-13

顺顺利利到了湖南。晚上认真研读cf毒瘤题题解,未果。

发现这里含铁丰富的高温多雨式红土地。以及窗户特别深,总有一圈小阳台的房子,门楣深邃如瞳。

看了一波miaom的ZJOI游记,思考了一下解题流程和策略。(先通读题意。找到最可写的开写。写得卡住了换一题,敲完暴力分回头跑。认真思考解法,不要放弃希望。写完了拍一下。检查。再见。)

 

4-14 

大概是按照昨天想好的策略考的,感觉状态比ZJOI好多了。估出来50,就是50,比较稳。写题的速度还可以再快一点,干脆些。

突然就上手noi-linux,亏得习惯很快。

第一题只写了10分暴力,思路跑到网络流最小割建模啊、fft集合卷积这些地方去了,然而并不可做。

经过交流发现只要从后往前做,对于最后一个判断一下是与还是或,还是两个都可以。

第二题又只有10分。感觉就是一个贪心,往单调递减的方向去了。然而似乎正确思路是发现只会绕一圈,然后用set维护ti-i贪心跳步。miaom还说离线的可以分块什么。zzs大爷说可以数据结构加速枚举起点的过程,树套树。//然后他0分。

第三题30分,一看就很可做,暴力dfs和树形dp。想容斥,但卡在大小为1~n的连通块个数不会求,弃。基环树以一个顶点破环成链然后分顶点选或不选两种情况算,好像很套路。n+1条边只要讨论环交点,两种情况。(n-1<=m<=n+10,差<=10感觉可以状压,建一棵生成树,然后暴力枚举11条边)70pts就是dp[i][j]表示以i为根的子树,j条非树边的一个端点被选取。然后也是类似于树这样转移。要枚举子集所以是3^11*n。100pts大概是容斥一波把枚举子集预处理掉O(n+3^n)。花絮:bitset.any():是否有1。all:是否都是1。none:是否都是0。

中午噎煲仔饭,时已三点(hnoi没有面包,差评)。下午赖在hjq房间里口胡题目(不想写题),后来就聊聊天啊、观摩打游戏啊,后来ckr从隔壁王者归来,于是大家听歌互奶。

也竟有一刹那Oier的“矮纸斜行闲作草,晴窗细乳戏分茶”之感。

吃个晚饭被路人张带偏半天。找路找了一个小时。不过湘菜还是很资瓷的。晚上应老师买来水果,向他请教了一下题目。

应老师说,做题要找关键点,找可供切入的地方,平时做题也要留心记住解题的关键步骤。这一次反思下来自己思路还是很有问题(代码能力倒还行),不能一眼看出大概做法(可能有时还有点偏)。之后要留心思路了。

加油呗!追根,你的骨子里必然淌着战士的血。

 

4-15

睡了七个小时吧,有点困。

大早上搞事情,zzs导航到另一个校区,我就不动声色地看着他表演。时间也不动声色地过了八点。到考场八点半了,真是戏剧。

T1看了两分钟开始写,8:50写完假算法。思考一波,改个递归应该就好了吧。9:30写完,再暴力的不会写,就手动测了几组小数据。

时间复杂度很不对的样子。大概算法是:不同向的判掉,线段树找到需要最左/最右的钥匙,转换成子问题两个函数互相调。为了防止毒瘤数据,加了个带容量上限的map记忆化。居然没有发现是梁大大讲过的。(我作为zhzx的准学生实在说不过去)

9:30~10:30 开T2,我只会阶乘暴力。

~11:00 终于排到上厕所,不明白为什么男女不能分开排队。。。开T3,二叉树很可做的样子。dep<=40,谨遵应老师的dp教诲,12:00一遍过样例,空间比较慌,用了vector啦啦啦。

后面写了个暴力对拍了一下,没查出错。(悲伤的是我不会linux的批处理)

考完啦——60+20+95=175。T1据说暴力部分分就有60,我记忆化亏得不行(说到底跟满分算法的思路还是有点出入)。满分算法是有讨论包含关系,预处理每个点往左往右走到的最远距离。T2:40pts:状压dp[state]表示某几个排列被选了的最大价值,然后转移判断一下是否有交集的限制,再算一下状态里有几个1算贡献。90pts:按照限制关系建树,从底往上考虑,把叶子扔进堆里。具体细节还不是很会。

T3:95是什么鬼?miaom用记忆化100了啊,我不会是被卡空间了吧。

中午被煲仔饭辣死,被阿萨姆奶茶拯救。只是噎一口需要被拯救一下。(内心阴影)

飞机飞回宁波啊~安检太过刺激~好吧海星。

那我回去多锻炼一下思维吧。:)

果然是游记看的人最多,我知道你们的心思。(打个调皮的响指)

 

原文地址:https://www.cnblogs.com/Scx117/p/8836052.html