Public NOIP Round
Public NOIP Round
yzxoi
2022-10-21 (Updated: 2022-10-21)
DP, 二分, 二分图, 决策单调性, 剪枝, 爆搜, 线段树, 线段树优化 DP, 背包, 贪心
A
经过一定分析可以发现合法数很少,写个爆搜+剪枝把所有答案先跑出来,查询二分即可。
O(?X+Q\log X)
B
很容易设出一个简单的 DP,设 f_{i} 表示当前子序列结尾为 a_i,且保证最终一定含 a_i,长度最大值。
设 g_{i,j} = \min { j> i \land a_j > a_i}
有转移:
其中,
其中 a_j>a_ia_i 从小到大枚举即可。
线段树辅助转移。
特别注意,初始合法的点仅为 [1,g_1]。
O(n\log n)
C
每个连通块独立,分别考虑。
根据提示,容易想到按图是否为二分图分类。
若该连通块为二分图,将该图黑白染色,两图的左黑+右白、右黑+左白数量相等,容易证明这是充要的。
若该连通块不为二分图,即其必含奇环,注意到变换之和为偶数,故黑、白点奇偶性相同,且权值集合相同,容易证明这是充要的。
D
只需要考虑 1\times x+ 5\times y 即可。
贪心地想,容易发现每次只会选一个物品。
综合上述,一个代价为 a_i 的物品价值为 5\lceil \frac {a_i}5\rceil-a_i,其新代价为 \lceil \frac {a_i} 5\rceil,而总新容量为 \lfloor \frac m5\rfloor,初始答案为 m\bmod 5。
注意到价值很小,可以将价值放到状态里,设 f_{i,j} 表示考虑所有代价 \leq i 的物品,获得价值为 j,所需要的最小代价。
显然其满足决策单调性,将所有代价为 i 的物品抽出来排序求前缀和,转移即可。
O(n\log n)
Copyright © 2019-2022 yzxoi
相关文章
- SQL保留小数点前面的0 round trunc 上取整,下取整[通俗易懂]
- Codeforces Round #806 (Div. 4)(A~F)
- Codeforces Round #754 (Div. 2) C-E
- SnackDown 2017 Online Elimination Round Prefix XOR
- POJ3252 Round Numbers 题解
- 「LibreOJ β Round #7」匹配字符串
- python中 global_python中round的用法
- 【算法竞赛】Codeforces Round #841 (Div. 2) C, E
- A. The Fair Nut and Elevator (Codeforces Round #526 (Div. 2))
- C. Prefixes and Suffixes ( Codeforces Round #527 (Div. 3) )
- MySQL Error number: MY-011247; Symbol: ER_SHA_PWD_FAILED_TO_GENERATE_MULTI_ROUND_HASH; SQLSTATE: HY000 报错 故障修复 远程处理
- 利用Oracle ROUND函数实现四舍五入(oracle四舍五入函数)
- aspFix、Int、Round、CInt函数使用说明
- php笔记之:php函数range()round()和list()的使用说明