NOIP2018 去世祭

### noip2018 游记 #### day-1： 机房下午模拟考试，t1大模拟ac，t2不会写，t3是贪心+优化，刚开始思路出了点小问题，线段树维护，然后发现不是求区间最值，是求小于等于某个数的最大值。一顿乱搞，然后比暴力扫数组多得了五分。（后来发现题解用了平衡树。。。。）（**刚开始思路对真的很重要**） 晚上线段树写“借教室”，tle#13，~~比较颓，吸氧ac了~~。 #### day0： 中午到了燕山大学附近住下，打了点板子，看了不少可能会有用的文章。重点复习数据结构。~~（考完才有学长说logn数据结构noip不考）~~ 下午试机发现没有去年考普及组用的codeblocks了，但是惊喜的发现了vc6版本的msdn.....然后后两天考试的考场都没有msdn，有codeblocks，屏幕也没有试机去的考场大。 晚上颓fps，后来惨遭教练围观，怂的一批。~~跟别人合住千万不要让他听见敲门就开门，还不提醒你。~~ 睡前打了树状数组，线段树，最短路板子。~~（一个都没用上）~~，11点睡觉。 #### day1： ##### T1： 进考场，看到T1，先想起线段树~~（跟数据结构过一辈子）~~，然后怀疑是不是需要枚举区间，按照数据范围好像会TLE。 然后想起差分，发现不知道怎么用。 然后试图找规律，数据范围不是o（n）就是o（nlogn）。刚开始以为是要把较低的点填成两遍高于它的较低的点，发现过不了样例。 然后发现貌似可以把这个思路略作修改写分治。~~但是我从来没写过分治。~~ 强迫自己继续肝，d1t1必须ac，然后想出空间o（1），时间o（n）的正解。没敢关io流的同步，但是民间数据和原题都AC。 **期望得分：100.** ##### T2： 看到之后立刻想起去年d1t1，同时还想起自己数论只会gcd~~（其实gcd也不会）~~，立刻滚去t3（后来滚回来了。） 滚回来之后开始找规律，想了半个多小时，感觉是拼数，删去序列里的，可以被序列里其他的数拼出来的数，想起exgcd，不会（依然把它当成数论题） 然后成功忘记完全背包的存在~~（一个半月没写过背包）~~。 胡乱写了个爆搜（部分原因是一直以为正解是数论，然后想起牛客模拟赛的随机生成树，就用dfs筛过去了。），利用max（a【1~n】）限制深度。**洛谷45，牛客80，em...** **期望得分：~~看脸~~ 50** ##### updata 2018.11.13： _当时考场上一开始没看到多组询问，想骗序列里有 **1** 的分，遇到 **1** 把ans赋值为 1。_ _然后看到多组询问，又发现是拼数之后这个**if(arr[i]==1)ans=1;** 没有删除。然后会导致所有序列里有 **1** 的询问我都输出二。_ 刚刚下载了数据才知道为什么洛谷会WA这么多点。 目前心态极度炸裂，想自挂东南枝。 期望得分updata：20 ##### updata:2018.11.23 CCF给了90分。~~8700kNB~~ ##### T3： 看完题面，黑人问号脸。 开始删除无用信息，最后确定题面含义：在一棵树上选出m条互不重叠的链，要求最短链最长，求最短链最长长度。 想到无根树转有根树后二分答案，然后不会了（二分答案一时爽，一写check火葬场。） 看了数据点，发现单源最短路只能骗5分，干脆直接输出样例或者**随机数**，滚回t2。（后来才知道眼瞎忽视了有20分的所有边接在同一点上的菊花图，白给的20分扔了。） 出来感觉心情不太好，下午，听说是三道原题，遍地ak，心态差点炸了，颓了一下午fps调整心情。~~还通关了。~~ **期望得分：0~~~100~~** #### day2： ##### T1： 看完题面，想到贪心，但是不知道怎么，以为是瞎搞，把链缩成点再瞎贪心..... 担心炸系统栈，人生**第一次**写手写栈dfs~~（谁给我的勇气）~~，自己都不知道写了个啥，到是一遍过了两个n-1的样例，试着改一改来优化，**发现改了就wa，然后就不敢改了**。 m=n的四十分想到断边，但是因为根本没发现这题其实是个dfs板子，还是想着上面的瞎搞思路，然后就不会了（**而且我还造了一个m=n+1的数据卡我想到的断边思路**，出考场想明白是dfs板子之后才发现了这个问题，觉得自己就是个zz） 很神奇，牛客和洛谷上都有60分。 **期望得分：60** ##### T2： 刚开始当成状压dp，看到m，就感觉是考组合数学。**（组合数学靠运气，计算几何瞎暴力）** 然后手推n=2规律，过了2 2和手算的2 3（手算的还不一定对。）。还忘记了n=1的情况。。。。。 也输出了样例。 洛谷，牛客都有五分。 **期望得分：5** ##### T3： 发现是树上dp。而且瞬间想起“没有上司的舞会”。每次询问dp一遍应该就有70分。~~后来才知道又眼瞎，应该是44分~~ 但是没有上司的舞会这题我也不会。 反正t1，t2已经炸了，硬着头皮写树上dp~~（谁给我的勇气x2）~~。 一个小时写了一百多行，没过样例，也没时间了（也没指望能写出来）。 样例都懒得输出，就把这个100% 0分的代码交了。 ~~期望得分~~**不期望得分** 最后几分钟很慌张的用虚拟机编译防止ce，过了下样例，又检查文件输入输出和文件名。~~（因为憋不住了，还去了下厕所）~~ 出了考场感觉自己要省四，然后看了~~哀鸿遍野的~~洛谷灌水区，心里平衡了一些~~（而且对自己水平也有B tree，红黑染色二叉的那种）~~ ### 总结： 1. **思路正确很重要**，noip似乎不会有什么让你瞎搞的题，别老想瞎搞。 2. **千万小心文件格式这些东西**，机房好几个兄弟死在了freopen上（虽然我用fstream）。 3. ** 心态不要炸**。（我这个人心比较大，但是有个学长考场上心态差点崩了） 4. **认真看数据范围**，尽量多骗分。 5. **化简题面的能力非常重要**，可以让你尽快确定哪题AC,哪题骗分，哪题不可做。（比如d1t3对于本蒟蒻） NOIP2018 大概是保省三，基本稳省二，省一肯定没戏的样子。 反正高一，明年继续考就是了。~~心大。~~ ~~不想写作业啊。~~ #### updata 2018.11.13： **d1t2炸了。考后崩心态可还行。mmp。** #### updata 2018.11.23 CCF给了260，~~今年分数线看来会很高了.~~