NOIP 2024 Day-10 训练
Day -10
2024.11.20
模拟赛
T1
怎么挂了？怎么挂了？怎么挂了？怎么挂了？怎么挂了？怎么挂了？怎么挂了？怎么挂了？
急了。
注意到，字典序具有传递性，于是把大于前缀转化为仅需大于上一个。
一个符合人类朴素价值观的贪心就是，钦定
讲课
CF1251D Salary Changing
考虑二分答案。
中位数大于等于
考虑先让所有数取下界，按达到
P4823 [TJOI2013] 拯救小矮人
考虑两个人的情况，显然
推广到有一车人也是对的。
但是要决策一下是否逃走，排序之后背包一下就行了。
跟 AT_dp_x Tower 好像 /se
P4698 [CEOI2011] Hotel
好像买东西题。
发现
然后贪心就行了
Day -9
模拟赛
T1
背包。
神秘结论。
T2
背包。
考虑平均数为
那么
然后仅需要保证正数负数之和为
发现正数范围为
于是问题转化为从
多重背包预处理一下，然后枚举这个相等的和即可。
计数多重背包的前缀和优化
直接当作完全背包做，减去不合法的部分即可。
讲课
P2605 [ZJOI2010] 基站选址
考虑一个
转移是不困难的
[AGC018C] Coins
感觉很早之前就看过这个题了（？）
考虑钦定初始所有都是金币，然后把三元组
先 Exchange Argument 决定一下顺序，然后问题就变成，选择
Day -8
模拟赛
暴力 92，kd-tree 40 /cy/cy/cy
这下 rp -= inf 了
讲题
NN Country
考虑倍增先跳到 lca 之前。
然后就是要寻找一条穿过 lca 的路线。
容易发现这个的限制是路线的两个端点在两个起点所在的子树中，容易用
Day -7
模拟赛
鉴定为省选模拟赛。
最高分 130。
讲课
P10430 [JOISC 2024 Day1] 鱼 3
观察到操作有交换律，因此考虑先把所有 A 操作完成了，再去做 B。
因为 B 操作只能凑出单调不降的序列，因此我们的目标实际上是通过尽可能少的 A 操作把序列变成单调不降的。
而这个单调不降的序列的形态其实是不重要的，因为我们仅需要最小化 A 的操作次数。
然后在
然后就考虑离线。
把询问的
我们发现，对于
于是我们把这个看作连续段，考虑颜色段均摊，用一个栈维护连续段，每次可能会把栈顶合并掉。
此外，还需要一个线段树，维护区间减法，以处理连续段一起减的操作和单点查询。
P3769 [CH弱省胡策R2] TATT 题解
树状数组套 kd-tree
恐怖 /jk
先按照
然后对于每一个
一个小 trick 是先把每个点的
然后进行一个数据结构优化 dp 即可。
P6189 [NOI Online #1 入门组] 跑步
好像还挺典的。
考虑朴素的暴力 dp ，发现就是做一个完全背包。
记
容易写出转移
但是这个是
大哭。
考虑根号分治，对于所有小于
对于较大的数，我们采取另一种
一个观察是，所有拆分数都可以由一下两种操作得来：
- 向可重集中加入一个
- 把当前可重集中的所有数都增加
于是可以记
有转移
注意到可重集的大小为
不妨取
然后把两部分卷一下就对完了。
Day -6
xtq xtq xtq
Day -5
zyz zyz zyz
讲课
Make Q
考虑枚举环上向外连的那个点和那条边。
然后注意到这条边一定是那个点前三小的出边。
然后就枚举这个，删去，然后再求最小环就行了。
最小环仅需要构造一个最短路树，选取子树不同的两个点，钦定在环上即可。
Day -4
Day -3
- Title: NOIP 2024 Day-10 训练
- Author: rainbow-auto
- Created at : 2024-11-20 16:30:52
- Updated at : 2025-10-01 19:29:43
- Link: https://rainbow-auto.github.io/2024/11/20/NOIP-2024-Day-10-训练/
- License: This work is licensed under CC BY-NC-SA 4.0.