程序设计实践考试的入门模板

字数统计: 8.5k字   |   阅读时长: 40分

程序设计实践考试的入门模板

前言

其实从大二开始就在整理有关如何学习C语言以及如何应对程序设计实践（和C语言考试）的经验和相关模板，由于各种原因，这件事情也没有一个很好的进展。前不久邹大佬提起这事儿的时候，突然觉得是应该好好整理一份类似于参考资料的东西了。

我打算先由自己整理出来这份模板，主要面向应对程序设计实践考试的同学。
本文当中可能会存在一些错误和遗漏的东西，还请指正。（email 1278683056@qq.com）

使用这份模板之前，你需要学会最基本的C语言（C++）语法，所以关于语法部分如果还不是很熟悉，这份模板对你而言没有任何帮助。

在信工院程设挂科率奇高的大环境下，我觉得整理出一份适合于入门者使用的模板很有必要，希望能够帮助到大家。

第一章 关于程序设计入门

- 1.online judge

oj指的是在线评测系统，程序设计实践考试在oj上进行，所以首先我们需要对oj有一个大致的了解。

1.1 根据测试，xtuoj 1秒钟大约能够运行3e7次，这一点在避免得到TLE很重要，学会计算时间复杂度和空间复杂度是数据结构课程的内容，在此不赘述。

1.2 介绍几种常见错误的原因，以便于对症下药。
|类型|原因 |解决方案|
|—|–|–|
| WA（答案错误） | 程序输出跟标程输出不一致，算法设计上有错误，或存在逻辑错误 | 改进算法，检查逻辑问题 |
| TLE（超时） | 程序未能在限定时间内结束，算法复杂度过高，或存在死循环 | 检查是否存在死循环，判断算法时间复杂度是否可行，如果确认复杂度可行，有可能是被卡常了 |
|RE（运行错误）|除0，栈溢出，内存访问越界等| ①检查除法运算的地方是不是除0了 ②如果使用了递归算法，判断是不是爆栈了 ③ 下标超过范围，数组开小，会访问越界 |
|MLE（内存超限）|申请的内存超过了题目限制范围，一般是数组开大了，也可能是因为在死循环里不停地申请内存|改进算法，计算空间复杂度|
|PE（格式错误）|答案对了，但是输出格式有问题|仔细检查换行，空格等问题，距离AC很接近了|

在此解释一下何为卡常：
卡常指的是，程序算法本身复杂度符合题目要求，按理说是能够AC的，但可能由于自己代码写了很多不必要的东西，导致超时。当然，不排除会有出题人故意卡常。解决方法是尽量避免不必要的额外运算，另外，在输入输出上能通过使用外挂从而加速运行。外挂会在接下来的模板中给大家贴出。

何为爆栈：
递归层数太多，导致栈溢出。（这类似于死循环，但是程序还没超时就因为爆栈而终止运行了。）如果确实是因为层数太多，也可以手动模拟栈（stack），或者改为队列（queue）。

- 2.分析题型

程设考试一般6题，对于绝大多数人而言，通过2题意味着考试及格，当然也有少部分人可以1题及格。

一：暴力，所谓的签到题
二：执行
三：贪心
四：模拟
五：数据结构
六：图论
七：动态规划
八：数学相关

对于以上题型，一到四项没有什么很好的模板可供参考，更多的是平时的积累和练习，然而在考试时这些题相对后面的题型来说，属于简单题；针对五到八项，接下来我会整理出一些适合的模板。

第二章 数学相关

- 1 素数相关

1.1单个数n的判定，时间复杂度O(sqrt(N))

1
2
3
4
5
6
7
8
bool isprime(int n){
	if(n<2)return 0;
	if(n<4)return 1;
	for(int i=2;i*i<=n;i++){
		if(n%i==0)return 0;
	}
	return 1;
}

解释：
素数的因子只有1和它本身，那么如果从1到sqrt(n)都没有数字是n的因子，那么n一定是质数。
可以发现，一个数的所有因子，一定均等地分布在sqrt(n)的左右两边。
比如数字9的因子{1，3，9}，左边是{1，3}，右边是{3，9}。

1.2素数表，时间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
const int maxn = 1e5+10;
bool notprime[maxn];
void getprime(){
	notprime[0]=notprime[1]=1;
	for(int i=2;i<maxn;i++){
		if(notprime[i]==0){
			for(long long j=1LL*i*i;j<maxn;j+=i){
				notprime[j]=1;	
			}
		}
	}
}

解释：
notprime[i]==1表示i不是素数，反之表示i是素数。
对于一个素数a，它的倍数一定都不是素数，所以我们可以对于遇见的每个素数，都把它的倍数标记为非素数，以上代码就是实现这一过程的。
由于i*i可能会溢出，为了避免溢出，j使用long long型。j从i^2开始，因为小于i倍的部分都已经被修改过了，不需要重复修改。

1.3 合数分解（值域为int的）
把一个合数a分解为 a = 1 * p1^x1 * p2^x2 * … *pn^xn 的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn = 1e5;
int p[100],x[100];
void getheshu(int n){
	int cnt=0;
	for(int i=2;i<maxn&&n>1;i++){
		if(n%i==0){
			p[++cnt]=i;
			while(n%i==0){
				n/=i;
				x[cnt]++;
			}
		}
	}
	if(n>1){
		p[++cnt]=n;
		x[cnt]=1;
	}
}

解释：
调用这个函数后，n的分解结果存储在p数组和x数组中，表达形式如上述。
如果能够分解出一个质数p，那么循环分解出的p的最高次幂。
最后剩下的“尾巴”如果大于1，说明这个数字一定是个质数。

- 2 最大公约数

gcd和lcm
最大公约数主要用到的是辗转相除法

1
2
3
4
5
6
7
8
int gcd(int a,int b){
	int c;
	while(b){
		c=a;
		a=b;
		b=t%b;
	}return a;
}

当然我们可以直接使用库函数__gcd(,)它是内部已经实现好了的函数，所以可以省去上面的代码，请注意该函数前面有两条下划线。

至于a和b的最小公倍数，等于a*b/gcd(a,b)
我们可以实现函数：

1
2
3
int lcm(int a,int b){
	return 1LL*a*b/gcd(a,b);//避免32位整型溢出
}

- 3 组合数

3.1组合数打表

对于较小的组合数，我们一般采用打表的方式存储答案，主要有以下两种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[30][30];
for(int i=0;i<30;i++){
	dp[i][0]=dp[0][i]=1;
}
for(int i=1;i<30;i++){
	for(int j=1;j<30;j++){
		dp[i][j]=dp[i-1][j]+dp[i][j-1];
	}
}
/**解释：dp[i][j]表示从i+j个物品中选择i个物品，不选择j个物品，
那么它可以由dp[i-1][j]和dp[i][j-1]转移得到，满足加法定理。
C(n,k)对应dp[n-k][k]
**/

第一种方法是我喜欢的写法，不过以下第二种方法可能更加方便。

1
2
3
4
5
6
7
8
9
int dp[30][30];
for(int i=0;i<30;i++){
	c[i][0]=c[i][i]=1;
	for(int j=1;j<i;j++){
		dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
	}
}
/**解释：这种写法的C(n,k)对应的值是dp[n][k]
**/

以上打表的算法，时间复杂度都是O(n^2)的，所以当复杂度过高时，请使用卢卡斯定理。
另外，根据数据范围调整32位整型和64位整型，如果要求取模，记得每次运算都要取模。

下面我们介绍卢卡斯定理。

3.2 卢卡斯定理

具体原理可以自行百度学习，这里还牵涉到了乘法逆元的知识点，初学者不妨把它当作黑箱子来使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef long long ll;
const int maxn = 1e5+10;
const int mod  = 1e9+7;

ll qpow(ll a,ll n){
    ll ret=1;
    while(n){
        if(n&1)ret=ret*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ret;
}

//除以一个数x，等同于乘以x的逆元，x的逆元 = x^(mod-2)%mod
//所以有p/q%mod = p*qpow(q,mod-2)%mod成立

ll fac[maxn];

void init(){
    fac[0]=1;
    for(int i=1;i<maxn;i++){
        fac[i]=fac[i-1]*i%mod;
    }
}

//C(n,m) = n!/(m!*(n-m)!)

ll C(ll n,ll m){
    if(n<m)return 0;
    return fac[n]*qpow(fac[m],mod-2)%mod*qpow(fac[n-m],mod-2)%mod;
}

小结：至于其他的数学知识，暂时还没有怎么见过，主要还是素数筛法考来考去。

第二章 数据结构

  • 1 排序
    在数据结构里，我们学习了很多种各有特色的排序算法，但在这里我只介绍一种最方便的排序工具：STL里的sort()函数。
    什么是STL？这个问题在我另一篇很久没更新的博客上可以找到答案：点我，我是传送门
    上面的链接里有很多可用的STL介绍，在此不赘述。
    讲到排序，不妨再深入学习一下其他的STL工具。
    这里列举可以深入了解的STL工具：
    stack
    queue
    vector
    map
    set
    以及一大堆好用的函数

  • 2 双指针尺取法
    之所以把这个东西单独拿出来讲，是因为eric多次出过这种类型的题，O(nlogn)过不去，而这个O(n)的算法可以过题。
    举个例子：给个序列，序列中每个值都是正数，序列长度为百万级别的，问有多少个区间[L,R]，使得区间累加和为k。
    朴素做法是对于每个点都以它为起点，暴力扫描一遍，复杂度O(n²)。
    可以把朴素做法用二分搜索优化到O(nlogn)。
    最快做法如下（这个链接的D题题解就是双指针原题）：

1
2
3
4
5
6
7
8
9
10
11
12
13
ans=0;//答案初始为0
int l=1,r=1;//定义双指针的初始位置
while(l<=n&&r<=n){//当双指针都在序列范围内时
	if(pre[r]-pre[l-1]==s){//pre[]是前缀和，这一段的值如果满足条件，答案累加
		ans++;
		l++;r++;
	}
	else if(pre[r]-pre[l-1]>s){//如果超过，那么拿掉左边的一个
		l++;
	} else {//如果不足，从右边添加一个
		r++;
	}
}
  • 3 前缀和
    前缀和是一种可以用来快速查询区间和的数据结构，常见题型有“区间内素数个数”，“序列区间和”等。
1
2
3
4
5
6
const int maxn = 1e5+10;
int a[maxn],pre[maxn];
for(int i=1;i<=n;i++){
	pre[i]=pre[i-1]+a[i];//从1到i的累加和，等于从1到(i-1)的累加和，再加上a[i]的值。
}
//那么我们要查询区间[L,R]的累加和，只需要用pre[R]-pre[L-1]便可。
  • 4 树状数组
    既然前缀和可以处理区间和，那如果需要对单点进行修改操作呢？我们可以借助树状数组来实现。由于这个知识点需要很多前置知识，所以在这里只贴模板。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define maxn 1000060
int a[maxn],c[maxn];
int lowbit(int x){
    return x&(-x);
}
int n;
int sum(int i){
    int s=0;
    while(i) {
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

void add(int i,int v){
    while(i<=n) {
        c[i]+=v;
        i+=lowbit(i);
    }
}

//如果需要在结点i处加上x，那么只需要调用函数add(i,x)
//如果需要查询区间[L,R]的区间和，这个值会等于sum(R)-sum(L-1)

时间复杂度分析：修改操作和查询操作，复杂度均为O(logn)。

  • 5 指针实现二叉树
    二叉排序树是一个很经典的数据结构，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct node{
    bool used;      //标记该结点是否有值
    int v;
    node *l,*r;     //左右子节点
    node():used(false),l(NULL),r(NULL){};//构建函数
};
node* root;
node* newnode(){return new node();} //构建新结点
void build(node* u,int val){
    if(val < u->v){
        if(u->l!=NULL)
            build(u->l,val);
        else
            u->l = new node(val);
    }
    else{
        if(u->r!=NULL)
            build(u->r,val);
        else
            u->r = new node(val);
    }
}

//至于查询操作，由于树的结构是有特点的，所以访问到某个点的时候，只需要判断应该往左还是往右走便可，
//代码跟addnode操作是差不多的。

戳我，这篇博客的E题是一个二叉排序树的考试原题

戳我，这篇的E题也是一个二叉排序树的考试原题，学会这两题就能掌握BST了

  • 6 dfs
    我发现其实很多人都不太会深度优先搜索（depth first search），所以贴一个原理和解释吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
//问题：有一个100*100的迷宫，告诉你起点终点，以及障碍物的位置，问你至少需要几步从起点走到终点。
这里我们用dfs解决（也可以用bfs解决，bfs是广度优先搜索）。
void dfs(int step,int x,int y){
    if((x,y)是终点，那么step就是最小的答案);
    vis[x][y]=1;
    /**
    这里写往4个方向搜索的代码，如果那个点以前没有访问过，那么就往下搜
    if(......)dfs(step+1,x+1,y);如果这个点不是障碍物，并且以前没有到达过，那么我们就往下走。
    if(......)dfs(step+1,x-1,y);
    if(......)dfs(step+1,x,y+1);
    if(......)dfs(step+1,x,y-1);
    **/
}

这里贴一个dfs例题题解的链接，里面有完整代码，可作为模板使用。

  • 7 bfs
    我们可以认为dfs的实现过程像是一个栈，而bfs的实现过程像是一个队列。
    以下代码也是以迷宫为原型的bfs
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    struct node{
        int x,y,step;
        node(int x,int y,int step):x(x),y(y),step(step){}
    };
    void bfs(){
        int vis[100][100]={0};
        queue<int> q;
        q.push(node(起点坐标));
        while(!q.empty()){
            node now = q.front();q.pop();
            vis[now.x][now.y]=1;
            if(now这个点的坐标是终点坐标){ 答案就是now.step; }
            if(......)q.push();如果这个点不是障碍物，并且以前没有到达过，那么我们就压入队列，等待访问。
            if(......)q.push();
            if(......)q.push();
            if(......)q.push();
        }
        如果队列访问空了都没有找到答案，说明无解。
    }

按理说，“搜索”应该放在算法一类讲，不过这样分类也无大碍，接下来是一些最基础的搜索原题和代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//题意：
//定义一个二维数组： 
//它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，
//要求编程序找出从左上角到右下角的最短路线。

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

int mp[5][5];
int ans[30][2];
int vis[5][5];

int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};//这里是表示(+1,0),(-1,0),(0,+1),(0,-1)的四个不同方向

void print(int cnt)
{
    for(int i=0;i<=cnt;i++)
        printf("(%d, %d)\n",ans[i][0],ans[i][1]);
}

bool check(int x,int y)
{
    if(x<0||y<0||x>4||y>4||vis[x][y]||mp[x][y])//如果要访问的点超出边界，或者以前访问过，或者是墙壁，则不能走
        return 0;
    vis[x][y]=1;//把这个点标记为已经访问过
    return 1;//否则能走
}

void dfs(int x,int y,int cnt)
{
    ans[cnt][0]=x;
    ans[cnt][1]=y;//记录路径
    if(x+y==8)//如果到达终点，直接输出答案
    {
        print(cnt);
        return;
    }
    for(int i=0;i<4;i++)//遍历四个方向
    {
        if(check(x+fx[i],y+fy[i]))//如果能走
        {
            dfs(x+fx[i],y+fy[i],cnt+1);//dfs下去，步数+1
        }
    }
}

int main()
{
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
        scanf("%d",&mp[i][j]);
    dfs(0,0,0);
    return 0;
}
  • 8 二分搜索
    使用二分的先决条件是，二分对象满足单调性。
    比如：有一个序列a[]，你想知道x在这个序列中的排名，假使这个序列有序，那么我们就可以对序列进行二分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
const int maxn = 1e5+5;
int a[maxn];
void binary_search(int len,int x){
	sort(a+1,a+1+len);//如果无序，先对它排序
	int low = 0,high = len+1;
	while(low+1<high){
		int mid=low+high>>1;
		if(x>a[mid])low=mid;//如果x大于a[mid]，说明x比任何在mid前面的数字都要大，所以我们要找的位置在后面区间
		else high=mid;//否则在前面区间里
	}
	return low;
}

二分搜索可以做一个经典的题型就是，二分答案。
思路是：如果答案满足单调性，那么我们可以先二分一个答案，然后检查这个答案是否可行，
然后不断地缩减区间，最后就能找到最终的答案了。
这里贴一个原题的代码：

Alice是游戏中的一名工匠，游戏中最近“恶魔手套”很热，她准备做一批，正好可以赚一笔。 
制作一件“恶魔手套”需要n种原材料，第i种原料需要ai份，Alice已经有第i种原料bi份。 
Alice还有k份兑换券，兑换券可以去商店兑换任意的原料，但一份兑换券只能兑换一份。
请问Alice最多可以制作多少件“恶魔手套”。
（[题目来源](http://202.197.224.59/exam/index.php/problem/read/id/1269)）

#include <bits/stdc++.h>
using namespace std;
#define ll __int64
ll n,k;
ll a[1005],b[1005];

bool check(ll num){
    ll sy=k;
    for(int i=1;i<=n;i++){
        if(b[i]<a[i]*num){
            sy -= a[i]*num - b[i];
        }
        if(sy<0)return 0;
    }return 1;
}

int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%I64d%I64d",&n,&k);
        for(int i=1;i<=n;i++)scanf("%I64d",a+i);
        for(int i=1;i<=n;i++)scanf("%I64d",b+i);
        ll l=0,r=2e9+5;
        while(l<r){
            ll mid=(l+r)>>1;
            if(check(mid))l=mid+1;
            else r=mid-1;
        }
        if(!check(l))l--;
        printf("%I64d\n",l);
    }
    return 0;
}

三 图论

  • 1 建图
    在了解这一个知识点之前，你需要前置知识《离散数学.图论》和《数据结构》。
    对于稠密图，我们直接用邻接矩阵存储。也就是说，图中有多少个点，我们就开个多大的二维数组
    1
    2
    int mp[maxn][maxn];
    //那么，从点u到点v的距离就是mp[u][v]了，非常方便。
    对于稀疏图，我们采用邻接表存储，这里有两种存储方式

1.1 vector存图
1.2 前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
struct edge{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
}
const int maxn = 1e5+10;
vector<edge> mp[maxn];

void addedge1(int u,int v,int w){
	mp[u].push_back(edge(v,w));
}

个人并不喜欢前向星建图，认为在当下很少有人会卡常数，而且编译器能够把常数优化掉，
所以面向萌新的你们还是不贴前向星了，有兴趣的可以自己去学习。
  • 2 单源最短路之dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//邻接矩阵版本
const int INF=0x3f3f3f3f;
const int maxn=1200;

int dist[maxn],g[maxn][maxn],N;
bool vis[maxn];

void dijkstra()
{
    for(int i=1;i<=N;i++)
        dist[i]=(i==1)?0:INF;
    memset(vis,0,sizeof(vis));

    for(int i=1;i<=N;i++)
    {
        int mark=-1,mindis=INF;
        for(int j=1;j<=N;j++)
        {
            if(!vis[j]&&dist[j]<mindis)
            {
                mindis=dist[j];
                mark=j;
            }
        }
        vis[mark]=1;

        for(int j=1;j<=N;j++)
        {
            if(!vis[j])
            {
                dist[j]=min(dist[j],dist[mark]+g[mark][j]);
            }
        }
    }
}

// 堆优化dijkstra
//这份模板用到的建图方式是前向星

#include<bits/stdc++.h>
using namespace std;
int head[100001],ne[200001],to[200001],w[200001],edgenum=0;
int dis[100001];
bool vis[100001];
int inf;
struct node{
    int pos,val;
    bool operator <(const node &a)const {return a.val<val;}
};
priority_queue<node> que;
inline void addedge(int f,int t,int co)
    {
        ne[++edgenum]=head[f];
        head[f]=edgenum;
        to[edgenum]=t;
        w[edgenum]=co;
    }

inline int read()
    {
        int x = 0, w = 0; char ch = getchar();
        for(;!isdigit(ch);w |= (ch == '-'), ch = getchar());
        for(;isdigit(ch);x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar());
        return w ? -x : x;
    }

inline node make_node(int x, int y)
    {
        node a;
        a.pos = x, a.val = y;
        return a;
    }

void Dijkstra(int s)
    {
        memset(dis,0x3f,sizeof(dis));
       // inf = dis[0];
        dis[s]=0;
        que.push(make_node(s, dis[s]));
        while(!que.empty())
            {
                node x=que.top();que.pop();
                int u = x.pos;
                if(x.val > dis[u]) continue; //这一步就相当于是删除了那些不够优的节点
                vis[u]=true;
                for(int i=head[u];i;i=ne[i])
                    {
                        int v=to[i];
                        if(vis[v])    continue;
                        if(dis[v]>w[i]+dis[u])
                            {
                                dis[v]=w[i] + dis[u];
                                que.push(make_node(v, dis[v]));
                            }
                    }
            }
    }
int main()
{
    int n = read(),m = read(),s = read(),x,y,l;
    for(int i=1;i<=m;i++)
        {
            x = read(), y = read(), l = read();
            addedge(x,y,l);
        }
    Dijkstra(s);
    for(int i=1;i<=n;i++)  printf("%d ",dis[i]);
    printf("\n");
    return 0;
}

  • 3 多源最短路之floyd
    floyd的过程像是一个动态规划，复杂度O(n3)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #define MAX 500
    #define INFE 1<<20
    int N; 
    int map[MAX][MAX],b[MAX],path[MAX][MAX];  //path[i][j]记录路径
    void init(){
           int i,j;
           for(i=1;i<=N;i++)
                  for(j=1;j<=N;j++) {
                         map[i][j]=INFE;
                         path[i][j]=j;
                  }
    }
    void floyd(){
           int i,j,k;
           for(k=1;k<=N;k++)
                  for(i=1;i<=N;i++)
                         for(j=1;j<=N;j++)
                                if(map[i][j]>map[i][k]+map[k][j]) {
                                       map[i][j]=map[i][k]+map[k][j];
                                       path[i][j]=path[i][k];
                                }
    }
    //最后点u和点v的距离就是map[i][j]了，如果map[i][j] == INFE，说明不存在（u,v）的路径。

  • 4 最小生成树之克鲁斯卡尔
    前置知识：并查集。（不会也没关系，照抄就是了）
    最小生成树：给出一个无向图，有n个点和m条边，要你从中选出n-1条边，
    使得这个图变成一棵树，并且边权之和最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
Description
求一个非负权边的无向连通图的最小生成树，如果这个无向图存在两个或两个以上的最小生成树，
就输出Not Unique，否则输出最小生成树的边的权值和。
输入：
第一行是一个整数K，表示有多少个测试用例，以后每个测试用例占m+1行。
每个测试用例的第一行为两个整数n，m（3<=n<=100），表示图的顶点数和边数，
从第二行开始每行为三个整数i，j,w,表示从i到j顶点的权值。
输出：
每行输出一个测试用例的结果。如果这个无向图存在两个或两个以上的最小生成树，
就输出Not Unique，否则输出最小生成树的边的权值和。
（这个题目就是202.197.224.59/exam上的1045）

#include<bits/stdc++.h>
using namespace std;
#define r(t) scanf("%d",&t)
int f[101];
int flag[101*101];
struct dis
{
    int x,y,d;
    friend bool operator < (dis A,dis B)
    {
        return A.d<B.d;
    }
}dis[101*101];
int t,n,m;

int find(int a)
{
    return a==f[a]?a:f[a]=find(f[a]);
}

void check(int a,int b)
{
    int fa=find(a),fb=find(b);
    if(fa!=fb)
    {
        f[fa]=fb;
    }
}

int main()
{
    r(t);
    while(t--)
    {
        int ans=0;
        int ok=0;
        memset(flag,0,sizeof(flag));

        r(n);r(m);
        for(int i=1;i<=n;i++)f[i]=i;
        for(int i=1;i<=m;i++)
        {
            r(dis[i].x);r(dis[i].y);r(dis[i].d);
        }
        sort(dis+1,dis+1+m);

        for(int i=1;i<=m;i++)
        {
            if(find(dis[i].x)!=find(dis[i].y))
            {
                check(dis[i].x,dis[i].y);
                flag[i]=1;
                ans+=dis[i].d;
            }
        }
        for(int q=1;q<=m;q++)
        {
            if(flag[q]==1)
            {
                int cnt=0;
                for(int i=1;i<=n;i++)f[i]=i;
                for(int i=1;i<=m;i++)
                {
                    if(q==i)continue;
                    if(find(dis[i].x)!=find(dis[i].y))
                    {
                        check(dis[i].x,dis[i].y);
                        cnt+=dis[i].d;
                    }
                }
                if(cnt==ans)ok=1;
            }
        }
        if(ok)cout<<"Not Unique\n";
        else cout<<ans<<endl;
    }
    return 0;
}

四 动态规划

动态规划是一个庞大的知识块，它有很多种解决不同类型问题的变形，所以我只贴一些原题的代码。
1303

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
n(1≤n≤60)个整数组成的序列(a1,a2,…,an),1≤ai≤8。
每次你可以从序列的头部或者尾部取一个数，第i(i=1,2,…,n)轮取数为ak，那么其代价为ak×2i−1。 
求将序列取完的最小代价。

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
int a[64];
int t;
int n;
ll dp[64][64];

ll dfs(int l,int r)
{
    if(dp[l][r])return dp[l][r];
    dp[l][r]=min(dfs(l+1,r)*2+a[l],
                 dfs(l,r-1)*2+a[r]);
    return dp[l][r];
}

int main()
{
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
            dp[i][i]=a[i];
        }
        cout<<dfs(1,n)<<"\n";
    }
    return 0;
}

某个模拟考试E题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
给一个整数序列{a1,a2,…,an}，存在这样的子序列{ai1,ai2,…,aim}∣1≤i1<i2<…<im≤n，
使得ai1<ai2<…<aik−1<aik>aik+1>…>aim。求最长的满足条件的子序列的长度。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a[10005];
    int pre[1005];
    int suf[1005];
    int t;cin>>t;
    while(t--){
        memset(pre,0,sizeof pre);
        memset(suf,0,sizeof suf);
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            for(int j=1;j<i;j++){
                if(a[i]>a[j])
                    pre[i]=max(pre[i],pre[j]+1);
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=n;j>i;j--){
                if(a[i]>a[j]){
                    suf[i]=max(suf[i],suf[j]+1);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(pre[i]&&suf[i]){
                ans=max(ans,pre[i]+suf[i]+1);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

三的倍数，原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
思路：

1.我们知道，一个数字是3的倍数，当且仅当这个数字的数位和能整除3，那么我们只需要找出那些使得数位和能整除3的种类。

2. 
dp[i][j]表示以第i个数字为数字的开头，能构成多少种符合条件的数字（此时不考虑前导0） 
那么有递推式： 
①:当前位模3余0： 
dp[i][0]=dp[i+1][0]<<1|1; 
dp[i][1]=dp[i+1][1]<<1; 
dp[i][2]=dp[i+1][2]<<1;

②:当前位模3余1： 
dp[i][0]=dp[i+1][0]+dp[i+1][2]; 
dp[i][1]=dp[i+1][1]+dp[i+1][0]+1; 
dp[i][2]=dp[i+1][2]+dp[i+1][1];

③: 
dp[i][0]=dp[i+1][0]+dp[i+1][1]; 
dp[i][1]=dp[i+1][1]+dp[i+1][2]; 
dp[i][2]=dp[i+1][2]+dp[i+1][0]+1;

此时，对于这个数字，dp[0][0]就是要求的答案。

3.问题在于如何去除含有前导0的种类数： 
对于s[i]==0： 
它的种类数应该是dp[i+1][0]+1; 
(当前位是0，后面要凑成3的倍数，共有dp[i+1][0]种，然后后面全部不选，只选第i也满足，故种类数是dp[i+1][0]+1)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
int main()
{
    char s[10000];
    int v[10000];
    ll dp[10000][3];
    while(scanf("%s",s)!=EOF)
    {
        int len=strlen(s);
        for(int i=0;i<len;i++)
            v[i] = (s[i]-'0')%3;
        dp[len][0]=dp[len][1]=dp[len][2]=0;
        for(int i=len-1;i>=0;i--)
        {
            if(v[i]==0)
            {
                dp[i][0]=dp[i+1][0]<<1|1;
                dp[i][1]=dp[i+1][1]<<1;
                dp[i][2]=dp[i+1][2]<<1;
            }
            else if(v[i]==1)
            {
                dp[i][0]=dp[i+1][0]+dp[i+1][2];
                dp[i][1]=dp[i+1][1]+dp[i+1][0]+1;
                dp[i][2]=dp[i+1][2]+dp[i+1][1];
            }
            else
            {
                dp[i][0]=dp[i+1][0]+dp[i+1][1];
                dp[i][1]=dp[i+1][1]+dp[i+1][2];
                dp[i][2]=dp[i+1][2]+dp[i+1][0]+1;
            }
            dp[i][0]%=mod;dp[i][1]%=mod;dp[i][2]%=mod;
        }
        ll ans=dp[0][0];
        for(int i=1;i<len;i++)
        {
            if(s[i]=='0')
            {
                ans = ans-dp[i+1][0]-1;
                ans%=mod;
            }
        }
        cout<<(ans+mod)%mod<<"\n";
    }
    return 0;
}

另外再补充一些简单动态规划模板吧。

最长公共子序列：
对于两个序列，找到他们最长公共子序列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

#define maxn 1111
string s1,s2;
int dp[maxn][maxn]={0};
int main()
{
    while(cin>>s1>>s2)
    {
        int l1 = s1.length();
        int l2 = s2.length();

        memset(dp,0,sizeof(dp));

        for(int i=0;i<l1;i++)
        {
            for(int j=0;j<l2;j++)
            {
                if(s1[i]==s2[j])
                {
                    dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1]);
                }
                else
                {
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        cout<<dp[l1][l2]<<endl;
    }
    return 0;
}

最长上升子序列：
对于一个序列，找到最长上升的子序列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstring>
using namespace std;
int a[1000];
int dp[1000];
int BinarySearch(int x, int len)//二分查找dp[]里面第一个大于等于x的数
{
    int left=1, right=len, mid;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(x==dp[mid])
            return mid;
        else if(x>dp[mid])
            left=mid+1;
        else if(x<dp[mid])
            right=mid-1;
    }
    return left;
}
int main()
{
    int N;
    while(cin>>N)
    {
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=N; i++)
        {
            cin>>a[i];
        }
        dp[1]=a[1];
        int len=1;//当前已经求出来的最长序列长度
        int j;//dp[]的下标
        for(int i=2; i<=N; i++)
        {
            //if(a[i]<dp[1])
               // j=1;
            if(a[i]>dp[len])//如果a[i]>dp[len]   len +1
                j=++len;
            else//反之， 更新j
                j=BinarySearch(a[i], len);
            dp[j]=a[i];//把a[i]更新入dp[]数组
 
        }
        cout<<len<<endl;
    }
    return 0;
}

01背包：
有一个容量为V的背包，有很多体积不等和价值不等物品，问最多能装多少价值的物品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<string.h>
using namespace std;

int dp[1001];
int vo[1001];
int va[1001];

int main()
{
    int n,all;
    int t;
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));

        cin>>n>>all;
        for(int i=1;i<=n;i++)
            cin>>va[i];
        for(int i=1;i<=n;i++)
            cin>>vo[i];
        for(int i=1;i<=n;i++)
        {
            for(int j=all;j>=0;j--)
            {
                if(j-vo[i]>=0)
                dp[j]=max(dp[j],dp[j-vo[i]]+va[i]);
            }
        }
        cout<<dp[all]<<endl;
    }
    return 0;
}

五 其他

  • 1 重定向输入输出

    1
    2
    freopen("a.in","r",stdin);//从a.in这个文件读取
    freopen("a.out","w",stdout);//输出到a.out这个文件

  • 2 输入挂，输出挂
    用了输入挂输出挂就别用普通的scanf和printf，容易出错。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    inline char nc(){
        static char buf[100000],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
    }
    template<class T>
    inline void read(T &sum){
        char ch=nc();sum=0;
        while(!(ch>='0'&&ch<='9'))ch=nc();
        while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    }

    template<class T>
    inline void print(T x){
        if(x>9)print(x/10);putchar(x%10+'0');
    }

    读入一个整数int a 就是 read(a);
    输出一个整数int a 就是 print(a);

结语：

2018.12.5更新：
今天把四个主要内容补充完，其中很多代码都是直接手写的，没有检验过正确性，如果有错误，请指出。
部分模板来自网络，部分 原题来自exam。
希望能够帮到那些初学者，以及被eric折磨得死去活来 的无辜群众们。

因为写这个面向的是小朋友嘛，所以作为一个学长，希望你们能够好好学习编程，切身去感受一下算法的魅力，有兴趣的话可以加一下eric带的 那个实验室，
叫什么名字来着？湘潭大学ACM集训队。

赏

谢谢打赏

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

iOS Developer, ACMer, ...