Tricks

August_Light · 2023-09-21 18:25:32 · 个人记录

用多个队列代替优先队列

在优先队列内的元素如果有某种单调性，可以用多个队列代替优先队列。

• 模板：P6033 [NOIP2004 提高组] 合并果子 加强版
• 练习：P2827 [NOIP2016 提高组] 蚯蚓
  • 可以通过画图、打表等方式猜出函数具有的单调性。
• 练习：P7078 [CSP-S2020] 贪吃蛇
  • 读者请自己练习，因为笔者没做过。

匹配栈

遇到可以使用区间 DP 解决的问题时，可以考虑使用括号序列的匹配栈。

• 例题：P9753 [CSP-S 2023] 消消乐
  • 这题有明显的区间 DP 做法。
  • 匹配栈可以搭配哈希使用。

对数

当一个问题是加法版本时有简单解法，现在要解决乘法版本时，可以考虑对数。

• 例题：P4926 [1007] 倍杀测量者
  • 这题在加法版本为差分约束模板。可对边权取 \log 化为加法版本。
  • 当然也可以直接以乘法做差分约束。（商分约束？）
• 例题：CF487C Prefix Product Sequence
  • 这题的加法版本为 CF1822D Super-Permutation，难度较低。
  • 可以通过 原根 取对数。
  • CF487C CF1822D 两题双倍经验见 P3599 Koishi Loves Construction。

单调队列

单调队列并不是只可以维护定长区间。有单调性就可考虑。

• 例题：P4954 [USACO09OPEN] Tower of Hay G

当普通数据结构难以维护时：赋随机权

式子正着推成立而反着推可能不成立的情况，可以赋随机权，即哈希。

• 模板：P8819 [CSP-S 2022] 星战

根号分治

有复杂度互补的两种暴力，可以使用根号分治。

资料：国家集训队2014论文集 根号算法——不只是分块

• 模板：P3396 哈希冲突

打暴力：两两配对问题

• next_permutation 遍历所有排列，a_i 与 a_{i \oplus 1} 配成一对。

单调 map

面对以下场合，普通值域树状数组无法胜任：

• 查询：前缀 \max
• 修改：单点变大
• 值域很大且不允许离散化

有以下解决方案：

1. 动态开点线段树 / 平衡树（传统方案，码量太大）
2. unordered_map 动态开点树状数组（码量小，常数太大）
3. 使用单调 map。

• 练习：P4954 [USACO09OPEN] Tower of Hay G

奇奇怪怪的结论

1. \gcd(\text{fib}_n, \text{fib}_m) = \text{fib}_{\gcd(n,m)}

• 模板：P1306 斐波那契公约数

2. d(nm) = \sum\limits_{i|n}\sum\limits_{j|m}[i \perp j]

• 练习：P3327 [SDOI2015] 约数个数和

3. \sum\limits_{d|n} \mu^2(d) = 2^{\omega(n)}

结论题的结论：T365450 粉兔杯初赛

题意

有 n 种兔子，每种兔子有 a_i 只。给兔子两两配对（可能有一只兔子轮空），最大化种类不同的兔子对数量。n \le 10^6, a_i \le 10^9。

经典错解

每次找出最大的一堆和次大的一堆，然后把次大的直接和最大的全部配对。

反例：3 3 4。其实都能配上。

正确答案

设 s = \sum\limits_{i=1}^n a_i，m = \max\limits_{i=1}^n a_i。

答案为 \min\left(\dfrac s 2, s-m \right)。