ZJNUOJ要关所以临时把题目搬过来复习🚗🚗:
高级数据结构
1.畅通工程——中高级
Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
输入包含多组数据，对于每组测试数据
第一行包含两个正整数N和M(0 <=N <=1000,0 < M < 5000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以1～N编号。
接下来是M行道路信息。每一行有2个整数A,B(0 < A,B <= N ),表示可以在城镇A和城镇B之间存在一条双向道路。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
Sample Output
1
0
2
998
#include<bits/stdc++.h>
using namespace std;
#define NUM 1010
int sset[NUM];
int r;
int findx(int x)
{
r=x;
while(sset[r]!=r)
r=sset[r];
return r;
}
void merge(int x,int y){
int fx,fy;
fx=findx(x);
fy=findx(y);
if(fx!=fy)
sset[fx] = fy;
}
int main()
{
int n,m;
int x,y,cnt;
while(cin>>n&&n!=0)
{
cnt=0;
for(int i=1;i<=n;i++)
sset[i]=i;
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
merge(x,y);
}
for(int i=1;i<=n;i++)
if(sset[i]==i)cnt++;
cout<<cnt-1<<endl;
}
return 0;
}
2.How Many Tables
Description
今天是Ignatius’的生日，他邀请了很多朋友，现在是晚餐时间，Ignatius’想要知道他至少需要准备多少张桌子。注意，不是所有的朋友都互相认识，并且所有人都不想跟陌生人呆在一起。
一个重要的条件是如果我告诉你A认识B，并且B认识C，那意味着A，B，C互相认识，因此他们可以用一张桌。
例如：如果A认识B, B 认识C，D认识E，因此A,B,C可以用一张桌子，D，E只能用另一张桌子，因此Ignatius’至少需要2张桌子。
Input
输入以T(1<=T<=25)开头，表示测试数据组数。然后接下来有T组测试数据，每组测试数据有两个整数N和M(1<=N,M<=1000)。N表示朋友的数量，编号从1到N。接下来有M行，每行有两个整数A和B(A!=B)，那代表A和B互相认识，两组测试数据之间有一个空行。
Output
对于每组测试数据，输出 Ignatius 至少需要多少桌子，不要输出任何空格。
Sample Input
2
5 3
1 2
2 3
4 5
5 1
2 5
Sample Output
2
4
#include<bits/stdc++.h>
using namespace std;
int n,m,r;
int f[1001];
int findx(int x)
{
r=x;
while(f[r]!=r)
r=f[r];
return r;
}
void merge(int x,int y){
int fx,fy;
fx=findx(x);
fy=findx(y);
if(fx!=fy)
f[fx] = fy;
}
int main()
{
int T,x,y,cnt;
cin>>T;
while(T--)
{
cnt=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=m;i++)
{
cin>>x>>y;
merge(x,y);
}
for(int i=1;i<=n;i++)
{
if(f[i]==i)
cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
3.More is better
Description
王先生需要一些男生来帮他完成一个项目。因为这个项目有些复杂，越多人来越好。当然，有一些要求的。王先生选了一个足够大的房间来容纳这些男生。没有被选中的男生就必须马上离开房间。一开始有100000个男生编号从1到100000，在王先生选择完后，在房间里的男生必须满足他们中的任何两个人必须是朋友（直接的或间接的），或者只有一个男生。给出所有的朋友关系，你要选出最好的方式。
Input
第一行输入包含一个整数n (0 ≤ n ≤ 100 000) -朋友关系的数量。接下来n行包含一对数字A和B，由一个空格隔开，表示A和B是直接的朋友 (A ≠ B, 1 ≤ A, B ≤ 10000000)
Output
输出一行，包含一个整数，表示王先生能持有的最大数量的男生。
Sample Input
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
Sample Output
4
2
Hint
A和B是朋友（直接或间接），B和C是朋友（直接或间接），然后A和C是朋友（非直接），在第一个样例里{1,2,5,6} 是结果。在第二个样例里{1,2},{3,4},{5,6},{7,8}是四种结果
#include<bits/stdc++.h>
using namespace std;
int f[100010],num[100010];
int minum;
int findx(int x)
{
int r=x;
while(f[r]!=r)
r=f[r];
int i=x,j;
while(i!=r)j=f[i],f[i]=r,i=j;
return r;
}
void init(){
for(int i=1;i<=100000;++i)f[i]=i,num[i]=1;
}
void merge(int x,int y){
int fx,fy;
fx=findx(x);
fy=findx(y);
if(fx!=fy)
f[fx]=fy,
num[fy]+=num[fx];
if(minum<num[fy])minum=num[fy];
}
int main()
{
int n,x,y;
while(cin>>n){
minum=1;
init();
while(n--){
cin>>x>>y;
merge(x,y);
}
cout<<minum<<endl;
}
return 0;
}
分治算法
1.网线主管
Description
仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。
为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。
该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。
你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。
Input
第一行包含两个整数N和K，以单个空格隔开。N（1 ≤ N ≤ 10000）是库存中的网线数，K（1 ≤ K ≤ 10000）是需要的网线数量。
接下来N行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少1m，至多100km。输入中的所有长度都精确到厘米，即保留到小数点后两位。
Output
网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。
若无法得到长度至少为1cm的指定数量的网线，则必须输出“0.00”（不包含引号）。
Sample Input
4 11
8.02
7.43
4.57
5.39
Sample Output
2.00
Source
一本通1242
#include<bits/stdc++.h>
#define N 10010
using namespace std;
int n,k,a[N];
bool check(int len)
{
int num=0;
for(int i=0;i<n;i++)num+=a[i]/len;
return num>=k;
}
int bisearch(int left ,int right)
{
int mid=(left+right)/2;
while(left+1<right){
mid=(left+right)/2;
if(check(mid))left=mid;
else right=mid;
}
return left;
}
int main(){
double x;
cin>>n>>k;
int left=0,right=-1,mid;
for(int i=0;i<n;i++){
cin>>x;
a[i]=(x+0.001)*100;
if(a[i]>right)right=a[i];
}
double ans=bisearch(0,right+1);
cout<<fixed<<setprecision(2)<<ans/100.0<<endl;
return 0;
}
2.循环比赛日程表
Description
设有N个选手进行循环比赛，其中N=2^M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。
Input
输入：M。
Output
输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。
Sample Input
3
Sample Output
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
Source
一本通1325
#include<bits/stdc++.h>
using namespace std;
int a[100][100]={1};
int main(){
int n,m,half=1;
cin>>m;
n=1<<m;
for(int k=1;k<=m;k++){
for(int i=0;i<half;i++){
for(int j=0;j<half;j++){
a[i][j+half]=a[i][j]+half;
a[i+half][j]=a[i][j+half];
a[i+half][j+half]=a[i][j];
}
}
half*=2;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
3.河中跳房子
Description
每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。
在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。
农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。
请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？
Input
第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。
接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。
Output
一个整数，最长可能的最短跳跃距离。
Sample Input
25 5 2
2
11
14
17
21
Sample Output
4
Source
一本通1247
#include<bits/stdc++.h>
using namespace std;
#define N 50010
int l,n,m,a[N];
int fun(int mm)
{
int d=0,cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]-d<mm)cnt++;
else d=a[i];
}
if(l-d<mm) cnt++;
return cnt;
}
int main()
{
cin>>l>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int left=1,right=l;
while(left<right-1)
{
int mid=(left+right)/2;
if(fun(mid)<=m) left=mid;
else right=mid;
}
cout<<left<<endl;
return 0;
}
贪心算法
1.接水问题
Description
学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。
现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j同学第x秒结束时完成接水，则k同学第x+1 秒立刻开始接水。 若当前接水人数n’不足m，则只有n’个龙头供水，其它m-n’个龙头关闭。
现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
Input
第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。
第2 行n个整数 w1、w2、……、wn，每两个整数之间用一个空格隔开，wi表示 i 号同学的接水量。
1 <= n, m, wi <= 100
Output
输出只有一行，1个整数，表示接水所需的总时间。
Sample Input
5 3
4 4 1 2 1
Sample Output
4
Source
一本通1233
#include<bits/stdc++.h>
using namespace std;
#define N 10010
int a[N];
int main()
{
int i,t;
int n,m;
cin>>n>>m;
for(i=0;i<m;i++)cin>>a[i];
for(i=1;i<=n-m;i++)
{
sort(a,a+m);
cin>>t;
a[0]+=t;
}
sort(a,a+m);
cout<<a[m-1];
return 0;
}
2.均分纸牌
Description
有n堆纸牌，编号分别为 1，2，…, n。每堆上有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为1的堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 n 的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 n=4，4堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6
移动3次可达到目的：
从 ③ 取4张牌放到④（9 8 13 10）->从③取3张牌放到 ②（9 11 10 10）-> 从②取1张牌放到①（10 10 10 10）。
Input
n（n 堆纸牌，1 ≤ n ≤ 100）
a1 a2 … an （n 堆纸牌，每堆纸牌初始数，l≤ ai ≤10000）。
Output
所有堆均达到相等时的最少移动次数。
Sample Input
4
9 8 17 6
Sample Output
3
Source
一本通1320
#include<bits/stdc++.h>
using namespace std;
#define MAX 10010
int a[MAX],s[MAX];
int main(){
int n,ans=0;;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int aver=s[n]/n;
for(int i=1;i<=n;i++){
if(s[i]!=aver*i){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
3.删数问题
Description
输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。
输出新的正整数。（n不超过240位）
输入数据均不需判错。
Input
n
s
Output
最后剩下的最小数。
Sample Input
175438
4
Sample Output
13
Source
一本通1321
#include<bits/stdc++.h>
using namespace std;
int main(){
char N[250];
int s,i,j,len,k,f=0;
scanf("%s",N);
scanf("%d",&s);
len=strlen(N);
for(i=0;i<s;i++){
for(j=0;j<len-1;j++){
if(N[j]>N[j+1]){
for(k=j;k<len-1;k++)
N[k]=N[k+1];
break;
}
}
len--;
}
for(i=0;i<len;i++){
if(N[i]!='0')f=1;
if(f==1)printf("%c",N[i]);
}
cout<<endl;
return 0;
}
4.拦截导弹问题
Description
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
Input
n颗依次飞来的高度（1≤n≤1000）。
Output
要拦截所有导弹最小配备的系统数k。
Sample Input
389 207 155 300 299 170 158 65
Sample Output
2
Source
一本通1322
#include<bits/stdc++.h>
using namespace std;
#define N 1010
int main(){
int a, b[N], k=1;
cin>>a;
b[1]=a;
while(cin>>a){
int tmin=30001, m=1;
for(int j=1;j<=k;j++)
if(b[j]>=a)
if(tmin>b[j])
tmin=b[j], m=j;
if(tmin!=30001) b[m]=a;
else{
k++;
b[k]=a;
}
}
cout<<k<<endl;
return 0;
}
5.整数区间
Description
请编程完成以下任务：
1.从文件中读取闭区间的个数及它们的描述；
2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。
Input
首行包括区间的数目n,1≤n≤10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0≤a≤b≤10000,它们是某一个区间的开始值和结束值。
Output
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。
Sample Input
4
3 6
2 4
0 2
4 7
Sample Output
2
Source
一本通1324
#include<bits/stdc++.h>
using namespace std;
struct node
{int x,y;
}a[10005];
bool cmp(node a,node b){
return a.y<b.y;
}
int main()
{
int i,j,x,sum=0,n;
scanf("%d",&n);
for(i=0;i<n;i++)cin>>a[i].x>>a[i].y;
sort(a,a+n,cmp);
x=-1;
for(i=0;i<n;i++)
{
if(x>=a[i].x)
continue;
sum++;
x=a[i].y;
}
cout<<sum<<endl;
return 0;
}
深度优先搜索（回溯法）
1.组合的输出
Description
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
Input
一行两个自然数n、r(1<n<21，1≤r≤n)。
Output
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
Sample Input
5 3
Sample Output
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Source
一本通1317
#include<bits/stdc++.h>
using namespace std;
#define N 30
int n, m;
int a[N];
void dfs(int u, int start)
{
int i;
if(u>m) {
for(i=1;i<=m;i++)
cout<<" "<<a[i];
cout<<endl ;
return;
}
for(i=start;i<=n;i++) {
a[u]=i;
dfs(u+1,i+1);
}
}
int main()
{
cin>>n>>m;
dfs(1,1);
return 0;
}
2.马走日
Description
马在中国象棋以日字形规则移动。
请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
Input
第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m < 10, n < 10)。
Output
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。
Sample Input
1
5 4 0 0
Sample Output
32
Source
一本通1219
#include <bits/stdc++.h>
using namespace std;
#define N 15
int n,m;
char maps[N][N];
int b[N][N];
int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{2,1},{2,-1},{1,2},{1,-2}};
int cnt;
void dfs(int x,int y,int step)
{
int i,x1,y1;
if(step==n*m)
{
cnt++;
return;
}
for(i=0;i<8;i++)
{
x1=x+dir[i][0];
y1=y+dir[i][1];
if(x1>=0 && y1>=0 && x1<n && y1<m && !b[x1][y1])
{
b[x1][y1]=1;
dfs(x1,y1,step+1);
b[x1][y1]=0;
}
}
}
int main()
{
int t,x,y;
cin>>t;
while(t--)
{
cnt=0;
memset(b,0,sizeof(b));
cin>>n>>m>>x>>y;
b[x][y]=1;
dfs(x,y,1);
cout<<cnt<<endl;
}
return 0;
}
3.装载问题
Description
有 n 个集装箱要装上载重为 c 的船，集装箱 i 重量为 wi。
要求确定在不超过轮船载重量的前提下，将尽可能重的集装箱装上轮船。
Input
第 1 行有 2 个整数 c 和 n。c 是轮船的最大载重量（1 ≤ c ≤ 30000），n 是集装箱的个数（n ≤ 20）。
第 2 行有 n 个整数 w1, w2, …, wn (1 ≤ wi ≤ 30000)，分别表示 n 个集装箱的量。
Output
对于每个测试用例，输出两行：第 1 行是能够装载到轮船的集装箱最大总重量，第 2 行是选择的集装箱的编号，按字典序升序输出。
如果有多种最优方案，输出总体字典序最小的方案。
Sample Input
34 3
21 10 5
Sample Output
31
1 2
#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
int n,c,w[MAX],x[MAX];
int r,cw;
int bestw,bestx[MAX];
void fun(int t)
{
if(t>n)
{
if(cw>bestw){
for(int i=1;i<=n;i++)
bestx[i]=x[i];
bestw=cw;
}
return;
}
r -= w[t];
if(cw+w[t]<=c)
{
x[t]=1;
cw += w[t];
fun(t+1);
cw=cw-w[t];
}
if(cw+r>bestw) {
x[t]=0;
fun(t+1);
}
r += w[t];
}
int main()
{
cin>>c>>n;
r=0;
for(int i=1;i<=n;i++){
cin>>w[i];
r += w[i];
}
cw=0,bestw=0;
fun(1);
cout<<bestw<<endl;
for(int i=1;i<=n;i++)
if(bestx[i]) cout<<i<<" ";
cout<<endl;
}
广度优先搜索（分支限界法）
1.细胞
Description
一矩形阵列由数字0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。如:
阵列
4 10
0234500067
1034560500
2045600671
0000000089
有4个细胞。
Input
第一行为矩阵的行n和列m;
下面为一个n×m的矩阵。
Output
细胞个数。
Sample Input
4 10
0234500067
1034560500
2045600671
0000000089
Sample Output
4
Source
一本通1329
#include<iostream>
using namespace std;
#define MAX 10010
int front,rear,n,m;
int q[MAX][3],ans=0;
int mx=0;
int dr[4]={1,-1,0,0},dc[4]={0,0,1,-1};
char a[MAX][MAX];
void bfs(){
int i,j;
while(front<rear)
{
front++;
for(i=0;i<4;i++)
{
int nn=q[front][0]+dr[i];
int mm=q[front][1]+dc[i];
if(a[nn][mm]!='0' && nn>=1 && nn<=n && mm>=1 && mm<=m)
{
rear++;
q[rear][0]=nn; q[rear][1]=mm;
a[nn][mm]='0';
}
}
}
}
int main(){
cin>>n>>m;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>a[i][j];
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]!='0')
{
ans++;
front=0;
rear=1;
q[1][0]=i;q[1][1]=j;
a[i][j]='0';
bfs();
if(rear>mx)mx=rear;
}
}
}
cout<<ans<<endl;
return 0;
}
2.走迷宫
Description
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
Input
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1≤ R，C ≤ 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用‘.’表示，有障碍物的格子用‘#’表示。
迷宫左上角和右下角都是‘.’。
Output
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
Sample Input
5 5
…###
#…
#.#.#
#.#.#
#.#…
Sample Output
9
Source
一本通1252
#include<bits/stdc++.h>
using namespace std;
#define N 110
struct point
{
int x,y;
int step;
};
char a[N][N];
int vis[N][N];
int m,n;
int startx,starty;
int decx,decy;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void bfs()
{
queue <point> r;
point start;
start.x=startx;
start.y=starty;
start.step=1;
r.push(start);
vis[startx][starty]=1;
while(!r.empty())
{
int x=r.front().x;
int y=r.front().y;
if(x==decx && y==decy)
{
cout << r.front().step;
}
for(int i=0;i<4;i++)
{
int nx,ny;
nx=x+dx[i];
ny=y+dy[i];
if(a[nx][ny]=='.' && vis[nx][ny]==0)
{
point temp;
temp.x=nx;
temp.y=ny;
temp.step=r.front().step+1;
r.push(temp);
vis[nx][ny]=1;
}
}
r.pop();
}
}
int main()
{
cin >>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
startx=1;
starty=1;
decx=n;
decy=m;
bfs();
return 0;
}
3.抓住那头牛
Description
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
Input
两个整数，N和K。
Output
一个整数，农夫抓到牛所要花费的最小分钟数。
Sample Input
5 17
Sample Output
4
Source
一本通1253
#include<bits/stdc++.h>
using namespace std;
#define MAX 100010
int n,k,que[MAX][2],t,i;
int a[MAX]={0};
int head,tail;
int main()
{
cin>>n>>k;
if(n==k)
{
cout<<0<<endl;
return 0;
}
head=0;
tail=1;
que[1][0]=n;
que[1][1]=0;
a[n]=1;
int temp;
while(head<tail)
{
head++;
temp=que[head][0];
for(i=1;i<=3;i++)
{
if(i==1) t=temp+1;
if(i==2) t=temp-1;
if(i==3) t=temp*2;
if(t>=0&&t<=100000&&a[t]==0)
{
tail++;
que[tail][0]=t;
a[t]=1;
que[tail][1]=que[head][1]+1;
if(t==k)
{
cout<<que[tail][1]<<endl;
return 0;
}
}
}
}
return 0;
}
4.TSP问题
Description
有一个旅行商人要拜访n个城市，城市间有m条无向路，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次（除了起始城市能经过两次），而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
Input
第一行两个整数n,m。 接下来m行，每行三个整数a,b,c。代表a，b之间有一条长为c的路。（n,m<=20）
Output
一个整数，路径长度。
Sample Input
2 1
1 2 1
Sample Output
2
Hint
可能会有重边
#include<bits/stdc++.h>
using namespace std;
int n,m,dist,ans;
int a[30][30];
int x[30],bestx[30];
void Back(int t)
{
if(t==n)
{
if(a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&(dist+a[x[n-1]][x[n]]+a[x[n]][1]<ans||ans==0))
{
for(int i=1;i<=n;i++)
bestx[i]=x[i];
ans=dist+a[x[n-1]][x[n]]+a[x[n]][1];
}
return;
}
else
{
for(int i=t;i<=n;i++)
{
if(a[x[t-1]][x[i]]!=0&&(dist+a[x[t-1]][x[i]]<ans||ans==0))
{
swap(x[t],x[i]);
dist+=a[x[t-1]][x[t]];
Back(t+1);
dist-=a[x[t-1]][x[t]];
swap(x[t],x[i]);
}
}
}
}
int main(void)
{
int ax,bx,cx,min=0;
cin>>n>>m;
for(int i=0;i<30;i++)
for(int j=1;j<30;j++)
a[i][j]=0;
ans=0;
for(int i=1;i<=n;i++)
x[i]=i;
for(int i=1;i<=m;i++)
{
cin>>ax>>bx>>cx;
if(a[ax][bx]==0)
{
a[ax][bx]=cx;
a[bx][ax]=cx;
}
else
if(cx<a[ax][bx])
{
a[ax][bx]=cx;
a[bx][ax]=cx;
}
}
Back(2);
cout<<ans<<endl;
return 0;
}
线性动态规划
1.最长公共子序列
Description
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1,x2,…,xm>，则另一序列Z＝<z1，z2，…，zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k有：
例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X＝<A,B,C,B,D,A,B>和Y＝<B,D,C,A,B,A>，则序列<B,C,A>是X和Y的一个公共子序列,序列 <B,C,B,A>也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列．因为X和Y没有长度大于4的公共子序列。
给定两个序列X＝<x1，x2，…，xm>和Y=<y_1,y_2…．y_n>．要求找出X和Y的一个最长公共子序列。
Input
共有两行。每行为一个由大写字母构成的长度不超过1000的字符串，表示序列X和Y。
Output
第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出文件仅有一行输出一个整数0。
Sample Input
ABCBDAB
BDCABA
Sample Output
4
Source
一本通1265
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int dp[N][N];
int main()
{
string x, y;
cin >> x >> y;
int lx = x.length(), ly = y.length();
for(int i = 1; i <= lx; ++i)
for(int j = 1; j <= ly; ++j)
{
if(x[i-1] == y[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
cout << dp[lx][ly] << endl;
return 0;
}
背包问题
1.完全背包问题
Description
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
Input
第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2…N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
Output
仅一行，一个数，表示最大总价值。
Sample Input
10 4
2 1
3 3
4 5
7 9
Sample Output
max=12
Source
一本通1268
#include<bits/stdc++.h>
using namespace std;
int fun(int n,int m,int *w,int *c){
int f[205][205];
int i,j;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j];
if(j>=w[i])f[i][j]=max(f[i-1][j],f[i][j-w[i]]+c[i]);
}
}
return f[n][m];
}
int main(){
int n,m;
int w[100],c[100];
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i];
}
cout<<"max="<<fun(n,m,w,c)<<endl;
}
2.混合背包
Description
一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是
W
1
，
W
2
，
.
.
.
,
W
n
W_1，W_2，...,W_n
W1?，W2?，...,Wn?，它们的价值分别为
C
1
,
C
2
,
.
.
.
,
C
n
C_1,C_2,...,C_n
C1?,C2?,...,Cn?。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
Input
第一行：二个整数，M(背包容量，M≤200)，N(物品数量，N≤30)；
第2…N+1行：每行三个整数Wi,Ci,Pi，前两个整数分别表示每个物品的重量，价值，第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数(Pi)。
Output
仅一行，一个数，表示最大总价值。
Sample Input
10 3
2 1 0
3 3 1
4 5 4
Sample Output
11
Source
一本通1270
#include<bits/stdc++.h>
using namespace std;
#define NUM 205
int c[NUM],p[NUM],w[NUM],dp[NUM];
int main(){
int n,m;
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i]>>p[i];
}
for(int i=1;i<=n;i++){
if(p[i]==0)
{
for(int j=w[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
else
{
for(int j=m;j>=w[i];j--){
for(int k=1;k<=p[i];k++){
if(j>=k*w[i])dp[j]=max(dp[j],dp[j-w[i]*k]+c[i]*k);
}
}
}
}
cout<<dp[m]<<endl;
return 0;
}
3.分组背包
Description
一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，…,Wn，它们的价值分别为C1,C2,…,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
Input
第一行：三个整数，V(背包容量，V≤200)，N(物品数量，N≤30)和T(最大组号，T≤10)；
第2…N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。
Output
仅一行，一个数，表示最大总价值。
Sample Input
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
Sample Output
20
Source
一本通1272
#include<bits/stdc++.h>
using namespace std;
#define NUM 1010
int a[NUM][NUM],c[NUM],f[NUM],w[NUM];
int main()
{
int v,n,t,p;
cin>>v>>n>>t;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>c[i]>>p;
a[p][++a[p][0]]=i;
}
for(int i=1;i<=t;i++)
{
for(int j=v;j>=0;j--)
{
for(int k=1;k<=a[i][0];k++)
{
if(w[a[i][k]]<=j)
{
f[j]=max(f[j],f[j-w[a[i][k]]]+c[a[i][k]]);
}
}
}
}
cout<<f[v]<<endl;
return 0;
}
区间动态规划与树形DP
1.出租游艇
Description
长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n所需的最少租金。
Input
第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的第1到第n-1 行，第i行表示第i站到第i+1站,第i+2站, … , 第n站的租金。
Output
输出从游艇出租站1到游艇出租站n所需的最少租金。
Sample Input
3
5 15
7
Sample Output
12
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define MAX 205
int n;
int r[MAX][MAX];
int dp(){
for(int len=2;len<n;len++){
for(int i=1;i<=n-len;i++){
int j=i+len;
for(int k=i+1;k<=j;k++){
r[i][j]=min(r[i][k]+r[k][j],r[i][j]);
}
}
}
return r[1][n];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)
cin>>r[i][j];
}
cout<<dp()<<endl;
return 0;
}
2.乘法难题
Description
乘法难题是用一些牌来玩的，在每张牌上都有一个正整数。玩家从一行牌中取出一张牌，得分的数量等于所取牌上的数字与左右两张牌上的数字的乘积。不允许取出第一张和最后一张牌。经过最后一步后，只剩下两张牌。玩牌的目标是把得分的总数降到最低。例如，若一行牌包含数字10、1、50、20、5，则若玩家先拿出一张1，然后拿出 20 和50的牌,得分便是：
10×1×50+50×20×5+10×50×5=500+5000+2500=8000。
若他按相反的顺序拿牌，即50、20、1，则得分是：
1×50×20+1×20×5+10×1×5 = 1000 + 100 + 50 = 1150。
Input
第1行包含牌的数量n (3≤n≤100)，第2行包含1~100的n个整数，表示牌上的数字。
Output
单行输出玩牌的最小分数。
Sample Input
6
10 1 50 50 20 5
Sample Output
3650
#include<bits/stdc++.h>
using namespace std;
#define NUM 105
int m,n;
int dp[NUM][NUM],a[NUM];
int fun(int i,int j){
if(dp[i][j]) return dp[i][j];
if(j==i+1) return 0;
dp[i][j]=2e9;
for(int k=i+1;k<j;k++){
dp[i][j]=min(dp[i][j],fun(i,k)+fun(k,j)+a[i]*a[j]*a[k]);
}
return dp[i][j];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<fun(1,n)<<endl;
}
3.括号序列
Description
定义如下规则序列（字符串）：
1.空序列是规则序列；
2.如果S是规则序列，那(S)和[S]也是规则序列；
3.如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
(), [], (()), ([]), ()[], ()[()]
这几个不是规则序列：
(, [, ], )(, ([()
现在，给出一些有’(’ , ‘)’ , ‘[’ , ‘]‘组成的序列，请添加尽量少的括号，得到一个规则序列，并输出该序列的长度。
Input
输入一个有’(’ , ‘)’ , ‘[’ , ']'组成的序列
Output
输出规则后的字串长度
Sample Input
([(]
Sample Output
6
//([()])
#include<bits/stdc++.h>
using namespace std;
#define NUM 200
int main(){
string a;
cin>>a;
int l=a.length();
int dp[NUM][NUM];
for(int i=0;i<l;i++) dp[i][i]=1;
for(int len=2;len<=l;len++){
for(int s=0;s<=l-len;s++){
int e=s+len-1;
dp[s][e]=1e10;
if((a[s]=='('&&a[e]==')')||(a[s]=='['&&a[e]==']'))
dp[s][e]=min(dp[s][e],dp[s+1][e-1]);
if((a[s]=='('&&a[e]!=')')||(a[s]=='['&&a[e]!=']'))
dp[s][e]=min(dp[s][e],dp[s][e-1]+1);
if((a[e]==')'&&a[s]!='(')||(a[e]==']'&&a[s]!='['))
dp[s][e]=min(dp[s][e],dp[s+1][e]+1);
for(int k=s;k<e;k++){
dp[s][e]=min(dp[s][e],dp[s][k]+dp[k+1][e]);
}
}
}
cout<<dp[0][l-1]+l<<endl;
}
|