OI坑
RoderickQiu
2019-02-02 21:18:04
~~感觉不做一个这样的总结帖我迟早得挂。~~
做到了什么整理什么，暂时不打算挖掘远古错误。
# 思路永远是最重要的，优化、特判、反方向操作……
# 0. 论检查的重要性
- 检查变量名是否**写错**，是否把函数当变量，……
- 检查程序是否**符合逻辑**。
- 检查变量是否清零、是否再清零。
- WA之后修改了再提交之前一定要先在**本地做测试**，~~以免影响AC率~~。
- 是否数组开错或开小。
- ……
# 1. DFS
```cpp
void dfs(int steps, int x, int y) {
if (checker()) {
if (steps < minSteps) minSteps = steps;
return;
}
if (steps >= minSteps) return;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (x != i && y != j) {
allChanger(x, y);
dfs(steps + 1, i, j);
allChanger(x, y);
}
}
}
}
dfs(0, 1, 1);
```
上错下对。
```cpp
void dfs(int steps) {
if (checker()) {
if (steps < minSteps) minSteps = steps;
return;
}
if (steps >= minSteps) return;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
allChanger(i, j);
dfs(steps + 1);
allChanger(i, j);
}
}
}
dfs(0);
```
问题所在：
**不要在第0步就限定状态，比如按照上面的做法，就必过一次(1, 1)必然不可取。**
# 2. 01背包与完全背包
01背包的正确写法：
```cpp
void pack01() {
for (int i = 1; i <= n; i++) { //倒序
for (int j = m; j >= 1; j--) {
dp[i] = max(dp[i], dp[i - v[j]] + c[j]);
}
}
}
```
完全背包的正确写法1：
```cpp
void packfull1() {
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) { //倒序
for (int k = 1; k <= MAX_K; k++) {
dp[i] = max(dp[i], dp[i - v[j] * k] + c[j] * k);
}
}
}
}
```
完全背包的更优写法：
```cpp
void packfull2() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) { //正序，可以选择好几次
dp[i] = max(dp[i], dp[i - v[j]] + c[j]);
}
}
}
```
对写法的解释 **（尤其是对循环正序、倒序的那段很重要）**：
> 为什么这个算法就可行呢？首先想想为什么 01 背包中要按照 v 递减的次序来循环。 让 v 递减是为了保证第 i 次循环中的状态 F[i,v] 是由状态 F[i−1,v −Ci] 递推而来。 换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策 略时，依据的是一个绝无已经选入第 i 件物品的子结果 F[i−1,v−Ci]。而现在完全背 包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时， 却正需要一个可能已选入第 i 种物品的子结果 F[i,v−Ci]，所以就可以并且必须采用 v 递增的顺序循环。这就是这个简单的程序为何成立的道理。
# 3. Dijkstra的正确链式前向星做法
```cpp
#include <bits/stdc++.h>
#define MAXN 500005 //之前貌似开小了
#define INF 2147483647
using namespace std;
int n, m, s;
struct Edge {
int from, to, val;
} e[MAXN], *p; //使用链式前向星储存（类邻接表解法）
//边编号从1开始，0代表没有下一条边，对应链表的NULL
// hd[i]代表点i边集中的第一条边编号，对应链表的hd指针
// nxt[i]代表边i的下一条边编号，对应链表中的nxt指针
// e[i]代表边i的信息
int hd[MAXN], nxt[MAXN], etop = 1, now;
int d[MAXN]; //从出发点到指定点的最短路径
bool vis[MAXN];
priority_queue< pair< int, int >, vector< pair< int, int > >,
greater< pair< int, int > > >
q; //通过操作，让成对的元素按照元素从小到大的顺序出队，此处使用是为了优化Dijkstra算法每一步中找“最接近的点”的步骤
void insert(int from, int to, int val) {
e[etop].from = from;
e[etop].to = to;
e[etop].val = val;
nxt[etop] = hd[from];
hd[from] = etop++; //单向链表从头部插入
}
void dijkstra(int from) {
d[from] = 0;
q.push(make_pair(0, from)); //将起点加入队列，与自己距离为0
while (!q.empty()) { //类BFS过程
now = q.top().second; // second获得pair的第二项
q.pop();
if (!vis[now]) { //一个访问过的点即无用了，因为一定已经取得最短路了
vis[now] = true;
for (int i = hd[now]; i; i = nxt[i]) { //遍历所有边
p = &e[i];
if (d[p->to] > d[now] + p->val) {
d[p->to] = d[now] + p->val; //松弛操作
q.push(make_pair(d[p->to], p->to)); //进入下一步
}
}
}
}
}
int main() {
scanf("%d %d %d", &n, &m, &s);
for (int i = 0; i <= n; i++) {
d[i] = INF;
}
int f, g, w;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &f, &g, &w);
insert(f, g, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << d[i] << ' ';
}
return 0;
}
```
尤其是 _**etop要初始化为1**_ ，否则：
```cpp
for (int i = head[now]; i; i = next[i]) { //遍历所有边
p = &e[i];
if (d[p->to] > d[now] + p->val) {
d[p->to] = d[now] + p->val; //松弛操作
q.push(make_pair(d[p->to], p->to)); //进入下一步
}
}
```
不会正常进行。
此外， _**无向图不能使用vis数组加快运算，因为有时需要走回来**_ 。详见[P1339](https://www.luogu.org/problemnew/show/P1339) 。
***另外一个重要的点是：在保存priority_queue的时候，距离永远放在第一个，这是优化的模式所在。***
# 4. Prim
```cpp
#include <bits/stdc++.h>
using namespace std;
struct edge {
int from, to, val;
} e[400005];
int n, m, x, y, z;
int head[5005], next[400005], etop = 1, dis[5005], visitcnt = 0, ans;
bool vis[5005];
priority_queue< pair< int, int >, vector< pair< int, int > >,
greater< pair< int, int > > >
q; //链式前向星
void inserter(int from, int to, int val) {
e[etop].from = from;
e[etop].to = to;
e[etop].val = val;
next[etop] = head[from];
head[from] = etop;
etop++; //标准的链式前向星操作
}
void prim() {
ans = 0; //最小生成树边权值的和
dis[1] = 0;
q.push(make_pair(0, 1)); //随意选取一个点作为已访问集合的第一个点
///距离永远放在第一个，这是priority_queue的优化模式！！！
while (!q.empty() &&
visitcnt <
n) { //只需要访问n-1次就可以完成遍历，之后浪费时间
int now = q.top().second,
nowd = q.top().first; //类似于dijkstra的处理方案
q.pop();
if (!vis[now]) {
vis[now] = true;
ans +=
nowd; ///把这个点加入生成树中，因而是加入当下这个点的dis
visitcnt++;
for (int i = head[now]; i != -1;
i = next[i]) { //遍历相连的，展开到下一步
if (e[i].val <
dis[e[i].to]) { //从堆中找到最小的连接集合内和集合外点的边，将边加入最小生成树中
dis[e[i].to] =
e[i].val; ///和dijkstra的主要区别：Prim的dis是相对于U中的任意一点而言的；而Dijkstra的dis是相对于v0而言的
q.push(make_pair(dis[e[i].to], e[i].to));
///距离永远放在第一个，这是priority_queue的优化模式！！！
}
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
vis[i] = false;
dis[i] = INT_MAX;
head[i] = -1;
}
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &z);
inserter(x, y, z);
inserter(y, x, z); //无向图存两次
}
prim();
if (visitcnt == n)
cout << ans;
else
cout << "orz"; //如果没有遍历完所有的边，则不连通
return 0;
}
```
此处，我们生成的是生成树，因此**Prim的dis是相对于集合中的任意一点而言的**；而Dijkstra的dis是相对于出发点而言的。
# 5. Kruskal与并查集相关
```cpp
#include <bits/stdc++.h>
using namespace std;
struct edge {
int from, to, val;
} e[400005];
int n, m, x, y, z;
int visitcnt = 0, ans = 0, etop = 1; // visitcnt：经过边的数量
int f[400005]; //并查集的操作数组
void inserter(int from, int to, int val) {
e[etop].from = from;
e[etop].to = to;
e[etop].val = val;
etop++;
}
int finder(int x) {
if (f[x] != x)
return f[x] = finder(f[x]);
else
return x;
} //递归法查询最高层父节点，也就是查询在哪个集合中
bool cmp(edge a, edge b) { return a.val < b.val; } //从小到大排序
void kruskal() {
sort(e, e + m,
cmp); //按照边权排序，既然是最小生成树，就要从最小的开始
for (int i = 1; i <= m && visitcnt < n - 1; i++) {
x = finder(e[i].from);
y = finder(e[i].to);
if (x !=
y) { //查询是否已经联通，也就是是否已经在同一个并查集里面
ans += e[i].val;
f[x] = y; //合并
visitcnt++;
}
}
} /* Kruskal:
先把边按照权值进行排序，
用贪心的思想优先选取权值较小的边，
并依次连接，若出现环则跳过此边（生成树没有环）
（用并查集来判断是否存在环）继续搜，
直到已经完全遍历所有的点。*/
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
f[i] = i; ///最开始时，并查集每个元素都单独属于自己
}
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &z);
inserter(x, y, z); /// kruskal对无向图不需要特殊处理
}
kruskal();
if (visitcnt ==
n - 1) /// visitcnt只会到n-1，因为连结n个点只需要n-1条线
cout << ans;
else
cout << "orz"; //如果没有遍历完所有的边，则不连通
return 0;
}
```
Kruskal使用了并查集。**需要注意的是，Kruskal遍历的是边，而不是点，因此它的visitcnt只能到达n-1，因为连结n个点只需要n-1条线**。
并查集在使用前要先**初始化**：
```cpp
for (int i = 1; i <= n; i++) {
f[i] = i; ///最开始时，并查集每个元素都单独属于自己
}
```
# 6. 线段树
- **写线段树很容易乱，比如搞混用于定位base[]的变量和用于定位tree[]的变量！！**
- **总是从root出发，一层层往下找，比如`change(int l, int r, int now, int target, int val)`，就是当前范围l、r用于base定位，now和lS(now)、rs(now)用于定位tree，target是目标的base值，val是要改成什么。最后通常也输出root。**
- **由于lazytag等，change完了要pushdown或者pushup之类。**