思维CheatSheet

思路

多角度思维

这个题有多少种思路，目前选择一条路。每个思路都要想一点。如果是dp，有多种方程，那每个都要考虑一下。

推导Observation

眼看出来的
基本公式，基于基本公式的Ob

卡住了

你想的题根本不是原问题

中间推导错了
题目读错了

换角度理解问题

转换问题的表示方法。换一种理解方式

常规推导

考虑答案由什么组成(拆分出可以维护的情况)
考虑最简单的几种情况(best case)
考虑状态的转移
什么会产生贡献，哪些会对答案产生贡献
考虑答案的单调性，时空转移

分类讨论

问题可以分为几种情况

贪心

什么构成答案最好（构造一个最好的答案）

计算操作的最大值最小值：

以某种贪心的策略一定可以达到最优，模拟这种策略的步骤

分析最大值

二分/枚举

如给定某个参数，是不是会好做一定

动态规划、递推

考虑问题的子结构
考虑状态是什么，如何转移
换一种更好的状态
简化子结构（去除冗余状态）
通过贪心优化转移，减少转移的数量
用数据结构维护一维度

整理思维

筛选合理的推断和考虑不确定的推断

题目的位置与代码量和思路深度对应
一道题有看似很难维护的性质或者很难求的量，一定有一个巧妙的办法化简或者转化。
如果这题模拟的方法讨论情况很多，应该不是这个做法。
如果代码量过大，过于难写，一定有更好的解法(A-D)

本来很简单，却做不出来的题

EC Round 93 Good Subarrays

可以往这几个方面思考

找一些例子(简单的)来看，然后看能不能转化为这种简单情况
影响答案的因素是什么，是否只有这几个因素

部分枚举

long long 和取模注意事项

排序前不能取模

写 = 不写 +=

1	ans = (ans + (x % mod)*fa[j++]) % mod;

不能写

1	ans += (x % mod)*fa[j++]) % mod;

变量vector 的时候用 auto, 别手残 ll 写成了 int

vector<ll> val;
for (auto x : val) {
    ans = (ans + (x % mod)*fa[j++]) % mod;
}

函数传参的时候注意 ll 和 int
最大值这么写
1
ll ans = 1e18;

序列问题

考虑$x$ 和他邻居的关系

$A[x] - A[i-1]$

维护技巧

Map维护

可以维护，从 $[1, i]$ ，或者 $[i, n ]$有多少个 $x$ 出现了

例题

https://codeforces.com/contest/1420/problem/B

Hash动态维护

维护2个集合，但是只用到“是否在集合中”的操作，可以直接用数组模拟Hash降低复杂度。

例题

https://codeforces.com/contest/1420/problem/C2

变量维护

你有你条线段 $[l_i, r_i]$ , 对于某个坐标 $x$ 统计经过它的线段的数量，储存在 map里面

把左右端点按横坐标排序，左端点在右端点的前面。然后从小到大看，假设当前的坐标是 $x$. 我们用一个变量 $sum $ 来维护左端点在 $x$ 左边的值。具体就是从小到大看，如果这个坐标是左端点，那么 sum++ 如果是右端点，那么 sum-- 每次枚举到 $x$ 的时候，取当前的$sum$的最大值. 也就是 M[x] = max(M[x], sum) . 因为要考虑很多左右坐标端点相同的情况。

https://codeforces.com/problemset/problem/1420/D

预处理

预处理一半的答案

先维护一半的答案，存在数组里。然后在扫一遍做出完整的答案。

https://codeforces.com/contest/1409/problem/E

预处理前缀/后缀和

？

https://codeforces.com/contest/1400/problem/D

位运算问题

从二进制角度考虑

把数拆成二进制数组，然后考虑算法

例题

https://codeforces.com/contest/1395/problem/C

https://codeforces.com/contest/1420/problem/B

计数问题

考虑对答案的贡献

例题

https://codeforces.com/contest/1420/problem/D

调试CheatSheet

数据范围与题目不符、循环变量范围与题目不符

超级致命，很难察觉。

for (int i = 1;i <= n; ++i) { // 应该是 K 不是 n ，复制过来的时候没有改
    f[i] = mul(f[i-1], i);
    rf[i] = mul(rf[i-1], inv[i]);
}

1	const int maxn = 1e5 + 5; // 题目范围是 2e5 + 5

定义的状态有没有维护好？

比如 A[q.front()].second == 1 漏了，因为之前删除了元素，里面的状态不满足定义的 A[x]>1的性质所以删除的时候要维护一下.

for (int i = 0;i < A.size(); ++i) {
    if (q.empty()) break;
    else { 
        A[q.front()].second--; 
        cnt++; // 删1个连通块
        if (q.front() == i) q.pop(); // 状态没维护好
    }
}

数组初始化问题

写了全局的 $A$ 数组，没有初始化

算法冗余过多

想法对了一大半，但实现的步骤不够干脆利落。

输出了重复的答案

题目要求答案不一样，但是求的时候没有判断重复

常见思路

序列

对于任意长度为k的子序列都满足

维护两个相同元素的间隔

1416A

以时间为序的问题

按时间排序后动态规划，注意根据最简单的选择来简化方程

1437C

使得序列递增

若 $i$ 到 $j$ 为递增，则 $a_j-a_i \ge j - i$ 也就是 $a_j - j \ge a_i - i$

所以可以把原来序列每个 $A[i] - i$ , 使得条件变为 $A'[i] <= A'[j]$, 然后可以套用最长上升子序列的模型

1437E

把序列全部变相等

先在一个地方收集和，然后再发配

1416B

矩阵

交换行和列

二分图匹配行和列

树

树上博弈论

分析最终答案的布局，由此计算答案

1436D