NOIvp小记

· · 个人记录

5.16

NOI2017 Day 1：60+40+10=110

P3822 [NOI2017] 整数

[P3823 [NOI2017] 蚯蚓排队](https://www.luogu.com.cn/problem/P3823) $40$：$O(n^2)$ 暴力和全为 $0$ 的部分分 $100$：发现 $k$ 很小，所以用 **哈希表** 在每次合并和分裂的时候维护每个 $k$ 的答案，同时用 **链表** 维护队伍。时间复杂度 $O(nk+ck^2+\sum|s|)

P3824 [NOI2017] 泳池

10$：$n=1

5.17

NOI2017 Day 2：50+44+20=114

P3825 [NOI2017] 游戏

30$：$\text{dfs} $100$：现在考虑 $x$ 地图，假设它也只适合两种赛车，那么暴力枚举每个 $x$ 地图不适合赛车 $A$ 或不适合赛车 $B$（因为不适合赛车 $A$ 就是适合赛车 $BC$，不适合赛车 $B$ 就是适合赛车 $AC$，这样就包含了 $ABC$ 三种赛车），这样每种地图就都只适合两种赛车了。复杂度 $O(2^d\times (n+m))

P3826 [NOI2017] 蔬菜

[P3827 [NOI2017] 分身术](https://www.luogu.com.cn/problem/P3827) $20$：$O(n^2)$ 暴力 ### 5.18 **NOI2018 Day 1**：$100+36+0=136

P4768 [NOI2018] 归程

[P4769 [NOI2018] 冒泡排序](https://www.luogu.com.cn/problem/P4769) $36$：打个表可以发现好排列满足要求排列中不存在长度 $\ge 3$ 的下降子序列。设 $f(S,lst1,0/1)$ 表示填入的数状态为 $S$，钦定目前最大值在第一个上升子序列，另一个上升子序列结尾为 $lst1$，是否在 $q$ 的下界，可以记忆化搜索 $100$：[题解](https://www.luogu.com.cn/blog/user45775/solution-p4769) [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770) ### 5.19 **NOI2018 Day 2**：$50+40+10=100

P4774 [NOI2018] 屠龙勇士

$100$：excrt [P4775 [NOI2018] 情报中心](https://www.luogu.com.cn/problem/P4775) $45$：$O(m^2 n)$ 暴力 $+$ 前两个特殊性质（不知道为什么挂了 $5$ 分） [P4776 [NOI2018] 多边形](https://www.luogu.com.cn/problem/P4776) $10$：$\text{dfs}