2017-5-14 省赛模板

作者: 染微言 | 来源:发表于2017-05-12 21:36 被阅读41次

简介
搜索
- 迷宫（BFS+队列）
最短路
- Dijkstra+邻接矩阵
- Dijkstra+链式前向星+优先队列
- Bellman-Ford + 链式前向星
- Bellman-Ford（标准）
- Floyd
- SPFA+邻接矩阵
- SPFA+DFS
- 最短路例题
生成树
- Kruskal
- Prim
- 次小生成树例题
并查集
- 一般并查集
- 带权并查集
- 并查集例题
线段树
- 漂浮法
- 线段树例题
动态规划
- 最长公共子序列
- 最长非降子序列（朴素）
- 最长非降子序列（二分）
- 最大字段和
- 递推例题
- 01背包
- 初始化的细节问题
- 完全背包问题
- 多重背包问题
- 数位DP例题
- 状压DP
- 树形DP
数学
- GCD与LCM
- 简易扩展欧几里得算法
杂项模板
- 万金油小算法
- STL用法
- 其他

简介

自用模板。

尽量选用题目来对模板进行解释。

搜索

迷宫（BFS+队列）

用结构体作为队列元素，三维数组存储地图。找到起点，入队，遍历前后左右上下移动，分别入队。用vis数组进行判重。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

struct node{
int x, y, z;
int step;
};
int sx, sy, sz; // 储存起始点坐标
int to[6][3]{1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1}; // 移动方向
int L, R, C; // 长宽高
char map[30][30][30];
int cnt, vis[30][30][30];

int check(int x, int y, int z){ // check it is illegal or not
if(x<0 || x>=L || y<0 || y>=R || z<0 || z>=C) return 1;
if(vis[x][y][z] || map[x][y][z] == '#') return 1;
return 0;
}

void bfs(){
queue<node> q;
node a, b;
a.x = sx, a.y = sy, a.z = sz;
a.step = 0;
vis[a.x][a.y][a.z] = 1;
q.push(a);
while(!q.empty()){
a = q.front(); q.pop();
if(map[a.x][a.y][a.z] == 'E'){ // 遇到终点结束
cnt = a.step;
return;
}
for(int i=0; i<6; i++){ // 前后左右上下移动
b = a;
b.x += to[i][0];
b.y += to[i][1];
b.z += to[i][2];
if(check(b.x, b.y, b.z)) continue;
b.step = a.step + 1;
vis[b.x][b.y][b.z] = 1;
q.push(b);
}
}
cnt = -1;
}

int main(){
while(scanf("%d%d%d", &L, &R, &C), L){
for(int i=0; i<L; i++)
for(int j=0; j<R; j++)
scanf("%s", map[i][j]); // input
for(int i=0; i<L; i++)
for(int j=0; j<R; j++)
for(int k=0; k<C; k++)
if(map[i][j][k] == 'S'){
sx = i; sy = j; sz = k; // find start
}
memset(vis, 0, sizeof(vis)); // initial
bfs();
if(cnt == -1) { printf("Trapped!\n"); } // output
else printf("Escaped in %d minute(s).\n", cnt);
}
return 0;
}

最短路

Dijkstra+邻接矩阵

邻接矩阵设置为全局变量，无向边存储两次。结果是起点到所有点的最短距离数组，不能判负环。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000;

int map[maxn][maxn];
int pre[maxn], dis[maxn];
bool vis[maxn];
int n,m;

void Dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;++i){
dis[i]=map[s][i];
pre[i]=s;
}
dis[s]=0;
vis[s]=true;
for(int i=2;i<=n;++i){
int mindist=INF;
int u=s;
for(int j=1;j<=n;++j)
if((!vis[j])&&dis[j]<mindist){
u=j; mindist=dis[j];
}
vis[u] = true;
for(int j=1;j<=n;++j)
if((!vis[j]) && map[u][j] < INF){
if(map[u][j] + dis[u] < dis[j]){
dis[j] = map[u][j] + dis[u];
pre[j] = u;
}
}
}
}

Dijkstra+链式前向星+优先队列

该模板需要初始化。
通过addnode方法加边，无向边读取两遍。优先队列优化时间效率，链式前向星遍历某节点下所有边，同时优化空间效率。结果是一个从起点到所有点的最短距离数组。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1000;

struct node{
int d,u;
friend bool operator<(node a,node b){
return a.d>b.d;
}
node(int dist,int point):d(dist),u(point){}
};

struct Edge{
int to,next;
int dist;
}edge[maxm];
int head[maxn],tot;
int pre[maxn],dis[maxn];

void init(){
memset(head,-1,sizeof(head));
tot=0;
}

void addedge(int u,int v,int d){
edge[tot].to=v;
edge[tot].dist=d;
edge[tot].next=head[u];
head[u]=tot++;
}

void Dijkstra(int s){
priority_queue<node> q;
memset(dis,0x3f,sizeof(dis));
memset(pre,-1,sizeof(pre));
dis[s]=0;
while(!q.empty()) q.pop();
node a(0,s); q.push(a);       //起点入队列
while(!q.empty()){
node x=q.top(); q.pop();
if(dis[x.u]<x.d) continue;
for(int i=head[x.u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(dis[v]>dis[x.u]+edge[i].dist){
dis[v]=dis[x.u]+edge[i].dist;
pre[v]=x.u;
q.push(node(dis[v],v));
}
}
}
}

Bellman-Ford + 链式前向星

我个人感觉这个算法的优化在于重边，以及松弛函数与主算法的分离。某些只针对松弛的题目变化可以很方便地使用。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
struct Edge{
int u, v;
double r, c;
}edge[maxn*2];

double mostMoney[maxn];
int n, m, s;
double v;
int tot;

void addedge(int u, int v, double r, double c){
edge[tot].u = u;
edge[tot].v = v;
edge[tot].r = r;
edge[tot++].c = c;
}

bool relax(int n){
double temp = (mostMoney[edge[n].u] - edge[n].c)*edge[n].r;
if (temp > mostMoney[edge[n].v]){
mostMoney[edge[n].v] = temp;
return true;
}
return false;
}

bool bellman_ford(){
bool flag;
for (int i=0; i<n; i++) mostMoney[i] = 0.0;
mostMoney[s] = v;
for (int i=0; i<n-1; ++i){
flag = false;
for (int j=0; j<tot; ++j)
if (relax(j)) flag = true;
if (mostMoney[s] > v) return true;
if (!flag) return false;
}
for (int i=0; i<tot; ++i)
if (relax(i)) return true;
return false;
}

Bellman-Ford（标准）

用简单的结构体来存储数据、遍历。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1000;

struct Edge{
int u,v; //起点、终点
int dist; //长度
}edge[maxn];

int dis[maxn]; //最短距离数组
int n, m; //结点数、边数

bool Bellman_ford(int s){
memset(dis, INF, sizeof(dis));
dis[s]=0;
for(int k=1; k<n; ++k){ //迭代n-1次
for(int i=0; i<m; ++i){  //检查每条边
int x = edge[i].u, y = edge[i].v;
if(dis[x] < INF)
dis[y] = min(dis[y], dis[x] + edge[i].dist);
}
}
bool flag=1;
for(int i=0; i<m; ++i){   //判断是否有负环
int x = edge[i].u, y = edge[i].v;
if(d[y] > d[x] + edge[i].dist){
flag = 0; break;
}
}
return flag;
}

Floyd

此算法三重循环是有顺序的。

最短路松弛算法为：
map[i][j] = min(map[i][k]+map[k][j], map[i][j])

最外层循环为中继点，第二次为起点，第三层为终点。

void floyd(){
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if (map[i][j] > map[i][k] + map[k][j]) //松弛
map[i][j] = map[i][k] + map[k][j];
}

SPFA+邻接矩阵

void spfa(int s){
for(int i=0; i<=n; i++) dis[i]=0x3f3f3f3f; //初始化每点到s的距离
dis[s]=0; vis[s]=1; q[1]=s;  //队列初始化,s为起点
int i, v, head=0, tail=1;
while (head++<tail){   //队列非空
v=q[head];  //取队首元素
vis[v]=0;   //释放队首结点，因为这节点可能下次用来松弛其它节点，重新入队
for(i=0; i<=n; i++)  //对所有顶点
if (a[v][i]>0 && dis[i]>dis[v]+a[v][i]){
dis[i] = dis[v]+a[v][i];   //修改最短路
if (vis[i]==0){  //如果扩展结点i不在队列中，入队
q[++tail]=i;
vis[i]=1;
}
}
}
}

SPFA+DFS

用a[i][j]存储从i到j所需要的距离。

用b[i][j]=w存储从i到w是i结点下的第j条边。

void spfa(int s){
for(int i=1; i<=b[s][0]; i++)  //b[s,0]是从顶点s发出的边的条数
if (dis[b[s][i]]>dis[s]+a[s][b[s][i]]){  //b[s,i]是从s发出的第i条边的另一个顶点
dis[b[s][i]=dis[s]+a[s][b[s][i]];
spfa(b[s][i]);
}
}

最短路例题

CSU - 1808

题意

最短路。

给出n个地铁站，m条边，给出每条边的首尾地铁站a、b，和这条边所属的地铁线c，以及这条边的边权d。

地铁线之间需要换乘，换乘时间为abs(ci-cj)。
因为多了一个换乘时间，所以需要拆点。

用链式前向星存边，用map<int,int>拆点，用vector存当前点所在的地铁。

思路

首先读边。用map[u][x]来表示u地铁站在x号线上，存储一个标记值cnt，代表这个点是第几个点（重新编号）。然后取出这个点。v点同样。最后addedge两遍。

遍历所有点。对每个点下的vector排个序，这样就可以避免取绝对值。对每个点遍历vector，对于vector中的每条地铁线，将这个点取出添边。

制图之后就按照模板跑Dijkstra，注意最后获取结果的时候要跑一遍n点的vector找最小值。

代码

/******************************
*File name: csu1808.cpp
*Author: wzhzzmzzy
*Created Time: 一  4/17 20:54:29 2017
*TODO: CSU 1808 最短路
******************************/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int maxn = 300005;
const int inf = 0x3f3f3f3f;

int n, m;
struct Edge{
int to, next;
int w;
}edge[maxn<<1];

int head[maxn], tot;

void init(){
memset(head, -1, sizeof(head));
tot = 0;
}

void addedge(int u, int v, int w){
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}

vector<int> num[maxn];
//某站所属的线路
map<int,int> mmp[maxn];
//某站是记录的第几个地铁站（拆点）
int dis[maxn], cnt;

struct node{
int now, c;
node(int _n=0, int _c=0):now(_n), c(_c){}
friend bool operator <(node a, node r){
return a.c > r.c;
}
};

void Dijkstra(){
priority_queue<node> q;
while (!q.empty()) q.pop();
for (int i = 1; i < cnt; ++i) dis[i] = inf;
for (int i = 0; i < num[1].size(); ++i){
int st = mmp[1][num[1][i]];
dis[st] = 0;
q.push(node(st, 0));
}
node temp;
while (!q.empty()){
temp = q.top(); q.pop();
int u = temp.now;
int cost = temp.c;
if (cost > dis[u]) continue;
for (int i = head[u]; ~i; i=edge[i].next){
int v = edge[i].to;
int w = edge[i].w;
if (dis[v] > cost+w){
dis[v] = cost + w;
q.push(node(v, dis[v]));
}
}
}
}

int main(){
int u, v, x, w;
while (~scanf("%d%d", &n, &m)){
init();
cnt = 1;
for (int i = 1; i <= n; ++i){
num[i].clear();
mmp[i].clear();
}
for (int i = 0; i < m; ++i){
scanf("%d%d%d%d", &u, &v, &x, &w);
if (!mmp[u][x]){
mmp[u][x] = cnt++;
num[u].push_back(x);
}
u = mmp[u][x];
if (!mmp[v][x]){
mmp[v][x] = cnt++;
num[v].push_back(x);
}
v = mmp[v][x];
addedge(u, v, w);
addedge(v, u, w);
}
for(int i = 1; i <= n; ++i){
sort(num[i].begin(), num[i].end());
for(int j = 0; j < num[i].size()-1; ++j){
u = mmp[i][num[i][j]];
v = mmp[i][num[i][j+1]];
w = num[i][j+1] - num[i][j]; //同一站点不同线路的拆点之间的差值
addedge(u, v, w);
addedge(v, u, w);
}
}
Dijkstra();
int ans = inf;
for (int i = 0; i < num[n].size(); ++i){
u = mmp[n][num[n][i]];
ans = min(ans, dis[u]);
}
printf("%d\n", ans);
}
return 0;
}

生成树

Kruskal

用并查集来将所有的节

点组织成一棵树。不需要正反读无向边，默认无向。

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn;
int fa[maxn];
int n, m;

struct Edge{
int u, v, w;
}edge[maxn];

bool cmp(Edge a,Edge b){
return a.w < b.w;
}

int find(int x){
return fa[x] == x? x: fa[x] = find(fa[x]);
}

int Kruskal(){
int ans = 0;
for(int i=0; i<=n; ++i)
fa[i]=i;
sort(edge, edge+m, cmp);
for(int i = 0; i < m; ++i){
int x = find(edge[i].u);
int y = find(edge[i].v);
if(x != y){
ans += edge[i].w;
fa[x] = y;
}
}
return ans;
}

Prim

void prim(){
int mi, v = 0;
for(int i = 0; i < n; i++){
dis[i] = map[0][i];
vis[i] = false;
}

for(int i = 1; i <= n; i++){
mi = INF;
for(int j = 0; j < n; j++)
if(!vis[j] && mi > dis[j]){
v = j;
mi = dis[j];
}
vis[v] = true;
for(int j = 0; j < n; j++)
if(!vis[j] && dis[j] > map[v][j])
dis[j] = map[v][j];
}
for(int i = 1; i < n; i++)
dis[0] += dis[i]; //统计生成树长度
}

次小生成树例题

POJ-1679

题意

套用kuangbin的次小生成树模板。

只要找到次小生成树，然后和最小生成树比较一下即可。

代码

/******************************
*File name: poj1679.cpp
*Author: wzhzzmzzy
*Created Time: 五  4/21 17:18:59 2017
*TODO: POJ 1679 次小生成树
******************************/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 105;

bool vis[maxn], used[maxn][maxn];
int lowc[maxn], pre[maxn], Max[maxn][maxn];

int prim(int cost[][maxn], int n){
int ans = 0;
memset(Max, 0, sizeof Max);
memset(used, false, sizeof used);
memset(vis, false, sizeof vis);
vis[0] = true;
pre[0] = -1;
for (int i = 1; i < n; ++i){
lowc[i] = cost[0][i];
pre[i] = 0;
}
lowc[0] = 0;
for (int i = 1; i < n; ++i){
int minc = inf;
int p = -1;
for (int j = 0; j < n; ++j) if (!vis[j] && minc > lowc[j]){
minc = lowc[j];
p = j;
}
if (minc == inf) return -1;
ans += minc;
vis[p] = true;
used[p][pre[p]] = used[pre[p]][p] = true;
for (int j = 0; j < n; ++j){
if (vis[j]) Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]);
if (!vis[j] && lowc[j] > cost[p][j]){
lowc[j] = cost[p][j];
pre[j] = p;
}
}
}
return ans;
}

int ans;
int check(int cost[][maxn], int n){
int Min = inf;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (cost[i][j] != inf && !used[i][j])
Min = min(Min, ans + cost[i][j] - Max[i][j]);
if (Min == inf) return -1;
return Min;
}

void solve(){
int cost[maxn][maxn], n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j){
if (i == j) cost[i][j] = 0;
else cost[i][j] = inf;
}
while (m--){
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
--x, --y;
cost[x][y] = cost[y][x] = w;
}
ans = prim(cost, n);
if (ans == -1 || ans == check(cost, n)) printf("Not Unique!\n");
else printf("%d\n", ans);
}

int main(){
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}

并查集

一般并查集

int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void join(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
}

带权并查集

而带权并查集，其中的权需要转化成子节点与父节点之间的联系。这样向上查找时就能发现父节点和子节点之间的关系，以此来进行计算。

带权并查集的压缩路径方法是，在递归向上查找的同时，因为递归是直接到达最深处然后向上回溯的，所以只需要对每个点都做一次累加，这样回到原来的位置时就是全部的累加。合并树操作各有不同，主要是创建父节点的操作。

举个例子，虫子的一生（ POJ - 2492 ）中用权数组表示两个虫子的性别关系，更新时就只要考虑一下同性还是异性即可。

并查集例题

POJ - 1733

题解

并查集+离散化。
有一个01串，1e9位。给出一些子串，和他们中有奇数个还是偶数个1，求这些中有几个是对的。
因为长度太长所以开不下这么多数组，而子串只有五千个，所以需要哈希一下。只要存最多一万个数字就可以。为了避免不在一起的相邻所以多存一位，就是两万位。然后用一个数组存当前下标之前有奇数还是偶数个1，最后用并查集求解。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;

int fa[maxn], val[maxn], n, m;
int hashSet[maxn];

struct {
int u, v, w;
}node[maxn];

int find(int n){
int k = fa[n];
if(fa[n] != n){
fa[n] = find(fa[n]);
val[n] = (val[n] + val[k])%2;
}
return fa[n];
}

void init(){
for (int i = 0; i <= n; ++i)
val[i] = 0, fa[i] = i;
}

int main(){
while (~scanf("%d", &n)){
int i, k = 0;

//init放在这里会RE

scanf("%d", &m);
for (i = 0; i < m; ++i){
char s[5];
scanf("%d%d%s", &node[i].u, &node[i].v, s);
node[i].w = s[0] == 'e'? 0:1;

hashSet[k++] = node[i].u - 1;
hashSet[k++] = node[i].u;
hashSet[k++] = node[i].v - 1;
hashSet[k++] = node[i].v;
}
hashSet[k++] = n;
hashSet[k++] = n - 1;

sort(hashSet, hashSet+k);
n = (int)(unique(hashSet, hashSet+k) - hashSet);

init();
//init放这里就AC

for (i = 0; i < m; ++i){
int u = (int)(lower_bound(hashSet, hashSet+n, node[i].u-1) - hashSet);
int v = (int)(lower_bound(hashSet, hashSet+n, node[i].v) - hashSet);

int fu = find(u), fv = find(v);

if (fu == fv && (val[u] + node[i].w)%2 != val[v])
break;
if (fu < fv){
fa[fv] = fu;
val[fv] = (val[u] + node[i].w - val[v] + 2) % 2;
}
if (fu > fv){
fa[fu] = fv;
val[fu] = (val[v] - node[i].w - val[u] + 2) % 2;
}
}
printf("%d\n", i);
}
return 0;
}

线段树

漂浮法

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

int t, n, a, b;
#define maxn  10001
int l[maxn], l[maxn];
int ans[maxn];

void cover(int a, int b, int to, int id) {
while (to <= n && (b < l[to] || a > r[to]))
to++;
if (to == n+1) {
ans[id] = b - a + 1; return;
}
if (a < l[to])
cover(a, l[to] - 1, to + 1, id);
if (b > r[to])
cover(r[to] + 1, b, to + 1, id);
}

int main() {
scanf("%d", &t);
while (t--) {
memset(ans, 0, sizeof(ans));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d %d", &l[i], &r[i]);
for (int i = n; i >= 1; i--)
cover(l[i], r[i], i + 1, i);
int cnt = 0;
for (int i = 1; i <= n; i++)
if (ans[i])cnt++;
printf("%d\n", cnt);
}
}

线段树例题

POJ-3468

代码

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

#define maxn 100010<<2
#define maxm 1000000000

int n, m;
long long A[100010];
long long Sum[maxn];
long long Add[maxn];

void pushup(int rt) {
Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1];
}
void build(int l,int r,int rt) {
if (l == r) { Sum[rt] = A[l]; return; }
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
pushup(rt);
}
void pushdown(int rt,int ln,int rn) {
if (Add[rt]) {
Add[rt << 1] += Add[rt];
Add[rt << 1 | 1] += Add[rt];
Sum[rt << 1] += Add[rt] * ln;
Sum[rt << 1 | 1] += Add[rt] * rn;
Add[rt] = 0;
}
}
void update(int a, int b, int c, int l, int r, int rt) {
if (a <= l&&b >= r) {
Sum[rt] += c*(r - l + 1);
Add[rt] += c;//本区间正确，子区间Sum仍然要用Add增加
return;
}
int m = (l + r) >> 1;
pushdown(rt, m - l + 1, r - m);
if (a <= m)update(a, b, c, l, m, rt << 1);
if (b > m)update(a, b, c, m + 1, r, rt << 1 | 1);
pushup(rt);
}
long long query(int a, int b, int l, int r, int rt) {
if (a <= l&&b >= r) { return Sum[rt]; }
int m = (l + r) >> 1;
pushdown(rt, m - l + 1, r - m);
long long ans = 0;
if (a <= m)ans += query(a, b, l, m, rt << 1);
if (b > m)ans += query(a, b, m + 1, r, rt << 1 | 1);
return ans;
}
int main() {
while (~scanf("%d %d", &n, &m)) {
memset(Add, 0, sizeof(Add));
for (int i = 1; i <= n; i++) {
scanf("%lld", &A[i]);
}
build(1, n, 1);
char s[10];
int a, b, c;
for (int i = 1; i <= m; i++) {
scanf("%s", s);
if (s[0] == 'Q') {
scanf("%d %d", &a, &b);
printf("%lld\n",query(a, b, 1, n, 1));
}
else {
scanf("%d %d %d", &a, &b, &c);
update(a, b, c, 1, n, 1);
}
}
}
}

动态规划

最长公共子序列

if (a[i] == b[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

最长非降子序列（朴素）

dp[i]存储a[i]位置及之前最长非降子序列长度。

for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
if (a[i] >= a[j])
dp[i] = max(dp[i], dp[j]+1);

最长非降子序列（二分）

for (int i = 1; i <= n; ++i){
int k = upper_bound(a[i]);
b[k+1] = a[i];
}

最大字段和

int f(int n){
bool flag = false;
for (int i = 1; i <= n; ++i){
if (!flag && a[i] > 0) flag = true;
if (dp[i-1] + a[i] < 0) dp[i] = 0;
else dp[i] = dp[i-1] + a[i];
}
if (!flag){
int ans = 0;
for (int i = 1; i <= n; ++i)
ans += a[i];
return ans;
}
else return dp[n];
}

递推例题

POJ - 1661

题意

Jimmy从坐标为(x,y)的点掉落下来，速度1单位/s，如果掉落下去的距离超过了max就会摔死。空间中有许多横着的木板，属性为(x1,x2,h)。在木板上可以横向移动，速度1单位/s。求最快到达地面的时间。

题解

基础DP。

用dp[i][0]表示从第i块木板左侧掉落的到达地面时间，dp[i][1]表示右侧。转移方程为：

dp[i][0] =
p[i].h - p[k].h +
min(dp[k][0]+p[i].x1-p[k].x1,
dp[k][1]+p[k].x2-p[i].x1);
dp[i][1] =
p[i].h - p[k].h +
min(dp[k][0]+p[i].x2-p[k].x1,
dp[k][1]+p[k].x2-p[i].x2);

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

struct plat{
int x1, x2, h;
}p[1005];
int maxn, dp[1005][2];

bool cmp(plat a, plat b){
return a.h < b.h;
}

void calc_left(int i){
int k = i - 1;
while (k > 0 && p[i].h - p[k].h <= maxn){
if (p[i].x1 >= p[k].x1 && p[i].x1 <= p[k].x2){
dp[i][0] = p[i].h - p[k].h + min(dp[k][0]+p[i].x1-p[k].x1,
dp[k][1]+p[k].x2-p[i].x1);
return;
} else --k;
}
if (p[i].h - p[k].h > maxn)
dp[i][0] = 0x3f3f3f3f;
else
dp[i][0] = p[i].h;
}

void calc_right(int i){
int k = i - 1;
while (k > 0 && p[i].h - p[k].h <= maxn){
if (p[i].x2 >= p[k].x1 && p[i].x2 <= p[k].x2){
dp[i][1] = p[i].h - p[k].h + min(dp[k][0]+p[i].x2-p[k].x1,
dp[k][1]+p[k].x2-p[i].x2);
return;
} else --k;
}
if (p[i].h - p[k].h > maxn)
dp[i][1] = 0x3f3f3f3f;
else
dp[i][1] = p[i].h;
}

void solve(){
memset(dp, 0, sizeof dp);
int n;
scanf("%d%d%d%d", &n, &p[0].x1, &p[0].h, &maxn);
++n, p[0].x2 = p[0].x1;
for (int i = 1; i < n; ++i)
scanf("%d%d%d", &p[i].x1, &p[i].x2, &p[i].h);
p[n].x1 = -20001, p[n].x2 = 20001, p[n].h = 0;
sort(p, p+n+1, cmp);

for (int i = 1; i <= n; ++i){
calc_left(i);
calc_right(i);
}

printf("%d\n", min(dp[n][0], dp[n][1]));
}

int main(){
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}

01背包

每个物品只能放入一次。

思路

用f[i][v]表示，第i个大小为v的物品放入时的总价值。

c[i]表示第i个物品的价值。w[i]为第i个物品的大小。

状态转移方程：f[i][v] = max(f[i-1][v], f[i-1][v-w[i]]+c[i]);

状态转移方程表示，取放入或者不放入第i个物品两种情况的最大值。

空间优化（滚动数组）

初始状态方程的空间复杂度是O(V*W)，可以进一步优化。

可以将空间优化为O(2*W)，即纵向大小为2。

for(i=1; i<=N; i++){
for(j=t[i]; j<=V; j++)
f[t^1][j] = max(f[c][j-w[i]]+c[i], f[t][j]);
t ^= 1;
}

异或滚动可以在0和1之间切换，可以利用上下反复更新。

空间优化（一维数组）

既然可以用两行进行更新，那为什么不能用一行。

观察问题，两行更新时，用上一行的前部分更新下一行的后部分。

所以单行更新时要从后往前遍历，这样可以用前面的更新后面的。

for(i=1; i<=N; i++)
for(j=V; j>=w[i]; j--)
f[j] = max(f[j-w[i]]+c[i], f[j]);

这样就可以用一维数组来进行更新。

可以写成函数，封装起来。

void ZeroOnePack(int cost, int weight){
for(int i=V; i>=weight; i++)
f[i] = max(f[i], f[i-weight]+cost)
}

初始化的细节问题

一般问题会有两种问法：

刚好装满背包
不用装满背包

如果是第一种，f[0]=0,f[1]……f[N]=INF;

如果是第二种，f[0]……f[N]=INF;

理解：

如果是第一种，初始状态只有0符合理想状态，只有0才能被空“装满”。

如果是第二种，所有都符合理想状态。

完全背包问题

和01背包相似，所不同的是可取的物品数是无限。

前置小优化

对于i``j两个物品，如果c[i]>c[j] && w[i]<w[j]，就舍去i物品。

另外，针对背包问题而言，比较不错的一种方法是：首先将重量大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。

基本思路

状态转移方程f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]},(0<=k*w[i]<=V)

转化为01背包求解

一件物品最多只能放V/c[i]件，所以可以把一件物品，看成V/c[i]件物品，作为01背包解答。

另一种更好的办法是把第i种物品拆成大小为w[i]*2^k、价值为c[i]*2^k的若干件物品，其中k满足w[i]*2^k<=V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/w[i]))件物品，是一个很大的改进。

`O(VN)`算法

for(int i=1; i<=N; i++)
for(int j=w[i]; j<=V; j++)
f[j] = max{f[v], f[v-w[i]]+c[i]};

这个算法和之前的01背包相比只是第二层的遍历方向改变了。因为01背包要保证每个物品只能选择一次，但是完全背包不必，所以改变遍历方向就可以得到结果。

这个算法也可以从另外的思路中得出，
例如，基本思路中的公式可以化作这个形式：
f[i][v]=max(f[i-1][v], f[i][v-w[i]]+c[i]);

用函数封装：

void CompletePack(int cost, int weight){
for(int i=weight; i<=V; i++)
f[i] = max(f[i], f[i-weight]+cost);
}

多重背包问题

每件物品数量不一定为1但有限。

基本思路

问题和完全背包很相似。
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[I]}(0<=k<=n[I])
复杂度为O(V*Σn[i])。

转化为01背包问题

用n[i]存储，可以将每种物品转化为n[i]件物品，然后用01背包方案求解。复杂度不变。

如果要进行优化的话，依然用二进制思想，同上。

这样可以将时间优化为O(V*Σlog n[i])。

void MultiplePack(int weight, int cost, int amount){
if(cost * amount >= V){
CompletePack(cost, weight);
return;
}
int k = 1;
while(k < num){// num 为物品种数
ZeroOnePack(k*cost, k*weight);
amount = amount-k;
k *= 2;
}
ZeroOnePack(amount*cost, amount*weight);
}

数位DP例题

HDU - 2089

题意

求从l到r的所有数字中，不含有4和62的数字有多少。

题解

数位DP入门。

用dp[i][j]表示j开头的i位数。首先打表，然后根据读入的数字挨个匹配累加即可。

递推公式：

for (int i = 1; i < 7; ++i)
for (int j = 0; j < 10; ++j)
for (int k = 0; k < 10; ++k)
if (j != 4 && !(j == 6 && k == 2))
dp[i][j] += dp[i-1][k];

代码

/******************************
*File name: hdu2089.cpp
*Author: wzhzzmzzy
*Created Time: 二  4/25 20:05:44 2017
*TODO: HDU 2089 数位DP
******************************/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

int dp[8][10];
void init(){
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (int i = 1; i < 7; ++i)
for (int j = 0; j < 10; ++j)
for (int k = 0; k < 10; ++k)
if (j != 4 && !(j == 6 && k == 2))
dp[i][j] += dp[i-1][k];
}

int calc(int x){
int digit[8], len = 0, ans = 0;
while (x > 0){
digit[++len] = x%10;
x /= 10;
}
digit[len+1] = 0;
for (int i = len; i; --i){
for (int j = 0; j < digit[i]; ++j)
if (j != 4 && !(digit[i+1]==6&&j==2))
ans += dp[i][j];
if (digit[i] == 4||(digit[i]==2&&digit[i+1]==6))
break;
}
return ans;
}

int main(){
int n, m;
init();
while (~scanf("%d%d", &n, &m) && n && m){
printf("%d\n", calc(m+1)-calc(n));
}
}

状压DP

HDU - 1074

题意

给出n门作业的名称、截止时间和所需时间。当超过截止时间时会扣分。求最小的扣分数和做作业的顺序。

题解

状态压缩DP。
看了题解才知道这样做。
首先是二进制法遍历集合全排列，然后遍历当前排列中包含的上一个做完的作业，即遍历每一种作业，找出扣分的最小值作为上一个做完的作业。记录这一状态，并且记录前驱（输出用）。

代码

/******************************
*File name: hdu1029.cpp
*Author: wzhzzmzzy
*Created Time: 日  4/23 20:01:35 2017
*TODO: HDU 1029 状压DP 水
******************************/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

char name[16][200];
int t[1<<15], deadline[16], finish[16];
int pre[1<<15], dp[1<<15];

void output(int m){
if (!m) return;
output(m-(1<<pre[m]));
printf("%s\n", name[pre[m]]);
}

int main(){
int T;
scanf("%d", &T);
while (T--){
int n;
scanf("%d", &n);
int maxn = 1<<n;
for (int i = 0; i < n; ++i)
scanf("%s%d%d", name[i], deadline+i, finish+i);
for (int i = 1; i < maxn; ++i){
dp[i] = 0x3f3f3f3f;
for (int j = n-1; j >= 0; --j){
int te = 1<<j;
if (!(i&te)) continue;
int score = t[i-te]-deadline[j]+finish[j];
if (score < 0) score = 0;
if (dp[i] > dp[i-te]+score){
dp[i] = dp[i-te]+score;
t[i] = t[i-te]+finish[j];
pre[i] = j;
}
}
}
printf("%d\n", dp[maxn-1]);
output(maxn-1);
}
return 0;
}

树形DP

HDU - 4044

代码

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <math.h>
#include <map>
#define ull unsigned long long
#define ll long long
#define mp map
#define FOR(a,b) for(int i=a;i<=b;i++)
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
using namespace std;

int m;
const int maxm = 210;
const int maxn = 1010;

vector<int>aaa[maxn];

int weaponChoice[maxn];
int cost[maxn][52];
int power[maxn][52];
int dp[maxn][maxm];    //dp[i][j]:i与其子树消耗j资源的最薄弱链最大值

void dfs(int u,int fa){
for(int i=m;i>=0;i--){
for(int j=1;j<=weaponChoice[u];j++){
if(cost[u][j]<=i)dp[u][i]=max(dp[u][i],power[u][j]);
}
}

if(aaa[u].size()==1&&u!=1) return;

int maxson[maxn];        //maxson[i]:u子树花费资源i时最大值
memset(maxson,0x3f3f3f3f,sizeof(maxson));
for(int e=0;e<aaa[u].size();e++){//枚举u的子节点
int v=aaa[u][e];
if(v==fa)continue;
dfs(v,u);                    //计算v树的最优解，dp[v]系
for(int i=m;i>=0;i--){        //枚举给u子树分配的资源
int maxx=0;
for(int j=0;j<=i;j++){
maxx=max(maxx,min(maxson[i-j],dp[v][j]));    //其他子树分i-j，v树分j
}
maxson[i]=maxx;
}
}
for(int i=m;i>=0;--i)
for(int k=0;k<=i;++k)
dp[u][i]=max(dp[u][i],dp[u][i-k]+maxson[k]);
}
int main(){
int tcase;
scanf("%d",&tcase);
while(tcase--){
memset(dp,0,sizeof(dp));
int n;
scanf("%d",&n);
for(int i=0;i<=n;i++)aaa[i].clear();
int a,b;
for(int i=1;i<n;i++){
scanf("%d %d",&a,&b);
aaa[a].push_back(b);
aaa[b].push_back(a);
}

scanf("%d",&m);
for(int i=1;i<=n;i++){
scanf("%d",&weaponChoice[i]);
for(int j=1;j<=weaponChoice[i];j++){
scanf("%d %d",&a,&b);
cost[i][j]=a;power[i][j]=b;
}
}
dfs(1,-1);
printf("%d\n",dp[1][m]);
}
}

数学

GCD与LCM

GCD计算方式来自公式gcd(a,b)=gcd(b,a%b)

int gcd(int a, int b){
return b>0? b : a%b;
}

LCM计算方式来自性质ab=gcd(a,b)*lcm(a,b)

int lcm(int a, int b){
return a * b / std::__gcd(a, b);
}

还有一个性质lcm(m*a,m*b)=m*gcd(a,b)

简易扩展欧几里得算法

void gcd(int a, int b, int& d, int& x, int& y) {
if (!b) { d = a; x = 1; y = 0; }
else { gcd(b, a%b, d, y, x); y -= x*(a / b); }
}

杂项模板

万金油小算法

快读

通过getchar和强制类型转换加快读取整形数字的速度。

int Input(){
char c;
for (c = getchar(); c<'0' || c>'9'; c = getchar());
int a = c - '0';
for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
a = a*10 + c - '0';
return a;
}

交换

指针交换变量值。

void swap(int* a, int* b){
int t = *a; *a = *b; *b = t;
}

前驱路径输出

递归回溯输出pre数组中的路径。

void output(int cur, int pre[]){
if (cur == 0) return;
output(pre[cur], pre);
printf("%d\n", cur);
}

矩阵快速幂

#include <cstdio>
#include <algorithm>
#include <string.h>
#include <iostream>
using namespace std;
#define maxn 101    //题目极限尺寸

int n;              //实际矩阵尺寸
struct Matrix {
long long mat[maxn][maxn];
};

Matrix operator * (Matrix a, Matrix b) {
Matrix c;
memset(c.mat, 0, sizeof(c.mat));
int i, j, k;
for (k = 0; k < n; ++k) {
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
c.mat[i][j] %= 10000;
}
}
}
return c;
}

Matrix operator ^ (Matrix a, int k) {
Matrix c;
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
c.mat[i][j] = (i == j);    //初始化为单位矩阵

for (; k; k >>= 1) {
if (k & 1) c = c*a;
a = a*a;
}
return c;
}

int main() {
int t;
while (scanf("%d", &t) && t != -1) {
Matrix fib;
n = 2;
fib.mat[0][0] = fib.mat[0][1] = fib.mat[1][0] = 1;
fib.mat[1][1] = 0;
fib = fib^t;
cout << fib.mat[0][1]%10000 << endl;
}
}

STL用法

struct 重载运算符、构造函数

struct node{
int d,u;
friend bool operator<(node a, node b){
return a.d > b.d;
}
node():{}
node(int dist, int point): d(dist), u(point){}
};

std::sort()

按照a字段降序排序，a相同时按b降序。

bool cmp(node a, node b){
if (a.a == b.a)
return a.b > b.b;
else
return a.a > b.a;
}

std::map

map<string,int> a;
a["hello"] = 1;
a["world"] = 2;
for (map<string,int>::iterator i = a.begin(); i != a.end(); ++i)
cout << i->first << " " << i->second << endl;
a.count("world") == 2; // Ture;

auto 变量

C++11，auto为一块指向无类型内存的变量。

int a = 0;
auto it = &a;
cout << *it << endl;

BigInteger

import java.math.BigInteger;
import java.util.*;

public class test {
public static void main(String args[]){
BigInteger
a = new BigInteger("32"),
m = new BigInteger("12");
BigDecimal b = new BigDecimal("1.0");
a = a.pow(1);
a = a.add(a);
a = a.divide(a);
a = a.mod(a);
a = a.abs();
a = a.gcd(a);
a = a.modPow(a, m);
System.out.print(a.toString()+"\n");
}
}

STL去重

sort(xs.begin(),sx.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end()); //unique将同样的元素排至vector末位，返回首个重复元素地址

STL算法离散化

思路：先排序，再删除重复元素，然后就是索引元素离散化后对应的值。

假定待离散化的序列为a[n]，b[n]是序列a[n]的一个副本，则对应以上三步为：

sort(sub_a,sub_a+n);
int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数
for(i=0;i<n;i++)
a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值

对于第3步，若离散化后序列为0, 1, 2, ..., size - 1则用lower_bound，从1, 2, 3, ..., size则用upper_bound，其中lower_bound返回第1个不小于b[i]的值的指针。

而upper_bound返回第1个大于b[i]的值的指针，当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果，两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

其他

Vim 配置

set nu
set mouse=a
set cursorline
set confirm
set tabstop=4
set smarttab
set shiftwidth=4
set smartindent
set cindent
set nobackup
set matchtime=1
set showmatch
set setnocompatible

colo evening

syntax on
syntax enable

G++ 运行

g++ a.cpp
./a.out

2017-5-14 省赛模板

简介

搜索

迷宫（BFS+队列）

最短路

Dijkstra+邻接矩阵

Dijkstra+链式前向星+优先队列

Bellman-Ford + 链式前向星

Bellman-Ford（标准）

Floyd

SPFA+邻接矩阵

SPFA+DFS

最短路例题

题意

思路

代码

生成树

Kruskal

Prim

次小生成树例题

题意

代码

并查集

一般并查集

带权并查集

并查集例题

题解

代码

线段树

漂浮法

线段树例题

代码

动态规划

最长公共子序列

最长非降子序列（朴素）

最长非降子序列（二分）

最大字段和

递推例题

题意

题解

代码

01背包

思路

空间优化（滚动数组）

空间优化（一维数组）

初始化的细节问题

完全背包问题

前置小优化

基本思路

转化为01背包求解

O(VN)算法

多重背包问题

基本思路

转化为01背包问题

数位DP例题

题意

题解

代码

状压DP

题意

题解

代码

树形DP

代码

数学

GCD与LCM

简易扩展欧几里得算法

杂项模板

万金油小算法

快读

交换

前驱路径输出

矩阵快速幂

STL用法

struct 重载运算符、构造函数

std::sort()

std::map

auto 变量

BigInteger

STL去重

`O(VN)`算法