summary-thought

Table of Contents

信息学竞赛是十分考验人的思维能力的(工业数据结构题给我滚).在此列出一些比较有用的思考方向,也许有用.

逆向思维

很多题目如果按照题目的要去做会有各种不便.如图论中的删点操作. 几乎所有的删点问题都可以通过某种方式转化为加点. 这只是一个小例子,具体的得大家自己体会. 某些高维状态的 DP 也许可以考虑对后面的状态的 贡献 来降维,甚至可以直接从后往前转移.

[YaliTraining 1119] 书本整理

无视无效信息

有时无视无效信息可以大大简化问题. 很多转化成二维平面然后求凸包的题也是基于此(忽略掉对答案无影响的点). 不仅如此, 单调队列 , 单调栈 也都是基于此(忽略掉不可能成为最优解一部分的元素).

[YaliTraining 1432] 土地购买

简化问题,挖掘本质

某些时候这一点很重要.有些没良心的出题人会把题意搞得很难懂,其实简化问题后就是些简单的问题. 但在简化问题时要注意:抓住本质.否则很有可能想偏.

问题转换

比较少见的思想.

巧妙运用题目的特点, 转换为另一个较简单的问题.

\(\textrm{mex}(a_1, a_2, ... , a_n)\)

可以考虑枚举 mex 值, 将式子写作 \(\sum_{i=1}^{ \infty } [\textrm{mex}(a_1, a_2, ... , a_n) \geq i]\).

转换为平面问题

有这么两类:

  1. 类似最大化 \((a - b) ^ 2 + (c - d) ^ 2\) (垃圾数学题),转换为平面上两点距离问题.
  2. ~区间~问题.比如有关区间 \([l, ~ r)\) 的最小值,将所有的情况用平面表示出来(点 \((x, ~ y)\) 对应的数记为区间 \([x, ~ y)\) 的最小值,然后在平面上表示出来)

[BZOJ 4540] [HNOI2016] 序列

二分答案

这是一个比较神的东西. 一般用于解决最优解的问题. 前提是次优解和无解有分界且连续 (其实不一定是次优解,是一些奇怪的东西也说不定,但一定要连续). 很多与~平均值~有关的东西都要用到这个.

分治

分治的复杂度是不太好分析的,这有可能会使得想到正解的人停下脚步. 分治经常用于"选一段……的……",所以我们可以考虑~递归~左半边,~递归~右半边,讨论跨过中间的情况.

点分治

往往在以下情况下使用:

  1. 最优点对问题或点对计数问题
  2. 最优路径问题或路径计数问题
  3. 修改或查询操作, 不好处理不在自己子树中的节点时.

简化状态

繁杂的状态往往会降低程序效率(尤其是记忆化),所以一定要设好状态,比如 最小表示法 便是基于此. 如果 插头DP 不用最小表示法而是普通的表示法,状态数量为原来的指数级别. HNOI2013 day1 T1 也是一道记忆化的题.关键是缩状态.

[BZOJ 3139] [HNOI2013] 比赛

高维问题

可以用到的方法: 扫描 (或 暴搜 ), CDQ分治 , 高级数据结构 (甚至 嵌套数据结构). 都组合试试,没准就想出来了.

[BZOJ 3140] [HNOI2013] 消毒

排序

别看这个东西很SB,其实不然.如果你可以对决策排序,最优解岂不是轻而易举?

生成树

有些与边有关的问题可以通过求 生成树 来解决问题.比如图中所有 奇环 的交等等.

EX 重构树

kruskal 构建最小生成树的时候, 我们可以让当前的边也加入到并查集中: 把边视为点,边权改为点权,连接两个点所属的并查集中. 这样的话,对于任意一个并查集中的点,其到达根的路径上点的点权是递增的.

调整法

生成树 上可以很好的应用. 总体思想是先使 叶子结点 满足一定的要求(用与父亲结点的边调整,即保留或不保留该边), 然后再考虑 所有子结点都已经调整好了 的结点,以此类推. 最终要么所有结点都满足要求,要么只有 根结点 不满足要求(因为 根结点 没有可供调整的边). 相关问题:去掉图中的一些边使得所有结点的度数满足一定要求. 注意调整法适用的问题很少,使用前要确保正确性.

缩点

与上面相反, 图论问题中与点有关的问题可能与这相关.比如做一些有可能改变 连通性 的操作.

树上两点问题转换为两节点及其LCA与树根的问题

大多数满足 区间可减性 的问题都可以如此.

dfs序

(感谢 prime21) dfs序 一般用于解决子树相关问题,由于任意一个节点的 dfn 值小于其所有的子孙结点,因此在某些情况下,可以将树形问题转为区间问题. dfs序 还有一些其他功能(如 链剖 便是基于链相关的特点,同时链剖也可以利用上面的特点维护子树信息),但不是很常用,此处略去.

欧拉序

虽然和 DFS序 有些区别, 不过还是写在这里. 如果将 DFS 的移动过程模拟出来, 每移动到一个节点就加入序列末, 那么每一个点都会被多次访问. 访问次数为 子节点个数+2. 可以借助 欧拉序RMQ 实现 \(O(n \log n)\) 预处理, \(O(1)\) 查询LCA.

优化建边

有一部分题目可以转化为经典的 图论 问题(如 最短路, 二分图 等),但是边数可能会很大. 这时我们要考虑优化建边,有两种思路:

不考虑不必要的边 (如: YALIOJ45675 双栈排序)

TODO 改进构图方式(如: UOJ111 [APIO2015] Jakarta Skyscrapers)

对DAG分层

我们可以将任意一个DAG分为 x 层层内互相没有连边的结点,其中 x 为 DAG 中的最长路径. 只需在求拓扑序时稍作修改即可.

运用: (带有限制地)构建 DAG.

优化暴力

什么鬼……暴力套个分块就A了?

压位

对于某些状态的转移,如果转移时只用到了类似位运算中 , 异或 运算,可以考虑压位,将状态用若干个 int 存.这样可以同时优化时间和空间上的常数. C++ 选手可以用 bitset.其他选手可手动实现.

Two-pointers

解决最优区间问题的有力武器. 最优区间问题无非是寻找满足某条件时的最长(最短)区间. 主要思路(这里以最长区间为例) 维护两个指针 L,R, 一开始两个都是0. 每一次 先执行 ++R ,然后检查当前的 L,R 是否合法.如果不合法,则执行 ++L ,然后继续检查,直到合法为止. 配合数据结构效果更佳.如~单调队列~.

状压

当数字规模较小时, 与 选与不选 相关的问题可以考虑 状压DP.

即使数字规模很大, 如果可以将限制(转移)用分层图表示出来, 且每一层的节点数很少时, 状压DP 同样适用.

[BZOJ 2734][HNOI2012] 集合选数

网络流模型

解决 多物品 问题的常用手段.

常出现的就是与物品移动有关的问题, 二选一的问题 以及 棋盘类问题.

容斥

对于 DP 而言, 如果状态不太好设, 如 \(dp(i, j)\) 表示属性 \(A\) 为 \(i\) , 属性 \(B\) 为 \(j\) 的状态数有多少, 这样一个方程无法转移, 那我们不妨将 \(j\) 的含义改为 属性 \(B\) 小于等于 \(j\) 的方案数, 然后容斥.

计数 问题稍作留意, 尤其是感觉自己的状态会把 方案算重算入不合法 的方案的时候. 广义的容斥是指作减法.

判重问题

集合判重: 给每一个元素随机一个 int64 级别的权值, 当两个集合所有元素权值的异或和相等时, 我们认为两个集合相等. 注意, 集合判重意味着元素没有重复. 有重复元素的话属于 无序数列.
有序数列判重: 哈希.
无序数列判重: 排序后再哈希…

差分

修改操作可以考虑差分.

可以快速差分的东西有: 区间加(减), 区间异或.

同样可以拓展到平面问题.

TODO calc ∑i f2(i)

未完待续

HOME