【13年12月CCF计算机软件能力认证】：出现次数最多的数、ISBN号码、最大的矩形、有趣的数、I‘m stuck!

题目	概括
出现次数最多的数	暴力枚举，非常简单
ISBN号码	直接模拟，非常简单
最大的矩形	用到双指针（优化枚举），非常简单
有趣的数	用到了数学知识排列组合，有一定思维难度
I’m stuck!	我用到了两个dfs来解决，解法比较暴力代码量大，但是速度也比较快

1、出现次数最多的数

给定 n 个正整数，找出它们中出现次数最多的数。

如果这样的数有多个，请输出其中最小的一个。

输入格式
输入的第一行只有一个正整数 n ，表示数字的个数。

输入的第二行有 n 个整数 s1,s2,…,sn 。

相邻的数用空格分隔。

输出格式
输出这 n 个次数中出现次数最多的数。

如果这样的数有多个，输出其中最小的一个。

数据范围
1≤n≤1000 , 1≤si≤10000
输入样例：
6
10 1 10 20 30 20
输出样例：
10

思路：

非常简单的题，暴力枚举即可

代码：

#include<bits/stdc++.h>using namespace std;int n;const int N=1e5+3;int v[N];int main()
{cin>>n;int minv=1e5;for(int i=1;i<=n;i++){int x;cin>>x;v[x]++;}int time=0;for(int i=1;i<=N;i++){if(v[i]!=0 && v[i]>time){minv=i;time=v[i];}else if(v[i]!=0 && v[i]==time && i<minv){minv=i;time=v[i];}}cout<<minv;return 0;
}

2、ISBN号码

每一本正式出版的图书都有一个 ISBN 号码与之对应。

ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 -
是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4 就是一个标准的ISBN码。

ISBN 码的首位数字表示书籍的出版语言，例如 0 代表英语；第一个分隔符 - 之后的三位数字代表出版社，例如 670
代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以 1 加上次位数字乘以 2 ……以此类推，用所得的结果 mod11 ，所得的余数即为识别码，如果余数为 10
，则识别码为大写字母 X 。

例如 ISBN 号码 0-670-82162-4 中的识别码 4 是这样得到的：对 067082162 这 9
个数字，从左至右，分别乘以 1,2,…,9 ，再求和，即 0×1+6×2+……+2×9=158 ，然后取 158mod11 的结果 4
作为识别码。

编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出 Right；如果错误，则输出是正确的 ISBN 号码。

输入格式
输入只有一行，是一个字符序列，表示一本书的 ISBN 号码（保证输入符合 ISBN 号码的格式要求）。

输出格式
输出一行，假如输入的 ISBN 号码的识别码正确，那么输出 Right，否则，按照规定的格式，输出正确的 ISBN
号码（包括分隔符 -）。

输入样例1：
0-670-82162-4
输出样例1： Right
输入样例2：
0-670-82162-0
输出样例2：
0-670-82162-4

思路：

非常简单的题目，顺着思路模拟即可

代码：

#include<bits/stdc++.h>using namespace std;int v[11];
char value;int a,b,c;typedef long long LL;LL k;int main()
{scanf("%d-%d-%d-%c",&a,&b,&c,&value);;v[1]=a;for(int i=4;i>=2;i--){v[i]=b%10;b/=10;}
// 	cout<<c<<endl;for(int i=9;i>=5;i--){v[i]=c%10;c/=10;}
// 	for(int i=1;i<=9;i++)
// 	{
// 		cout<<v[i]<<" ";
// 	}
// 	cout<<endl;for(int i=1;i<=9;i++){k+=v[i]*i;}k=k%11;
// 	cout<<k<<endl;if(k==10){if(value=='X')cout<<"Right";else{printf("%d-%d%d%d-%d%d%d%d%d-X",v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9]);}}else {if(k==(value-'0'))cout<<"Right";else{printf("%d-%d%d%d-%d%d%d%d%d-%d",v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9],k);
// 			cout<<endl<<v[8]<<endl;}}return 0;
}

3、最大的矩形

在横轴上放了 n 个相邻的矩形，每个矩形的宽度是 1 ，而第 i （1≤i≤n ）个矩形的高度是 hi 。

这 n 个矩形构成了一个直方图。

例如，下图中六个矩形的高度就分别是 3,1,6,5,2,3 。

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。

对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是 10 。

输入格式
第一行包含一个整数 n ，即矩形的数量。

第二行包含 n 个整数 h1,h2,…,hn ，相邻的数之间由空格分隔。hi 是第 i 个矩形的高度。

输出格式
输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

数据范围
1≤n≤1000 , 1≤hi≤10000

经实测 hi 在官网的实际范围是 1≤hi≤40000，这与其给出的题面描述不符，属于官网出题人的失误，也因此卡住了一些同学的代码，望大家加以注意。

输入样例：
6 3 1 6 5 2 3
输出样例：
10

思路：

这让我想起了接雨水那一题，都是双指针枚举，这里我没有选择双指针我直接枚举左端点再枚举区间长度（算出右端点，也近似于双指针了，事实上双指针就是对暴力枚举的优化），在枚举每一个区间的时候找出区间中最低的高度，最后这样就可以枚举出每一个区间的最大矩形面积，输出最大矩形面积即可

代码：

#include<bits/stdc++.h>using namespace std;int n;
int h[1010]; 
int maxv=-1;int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}int l=1;for(int i=l;i<=n;i++)//枚举左端点 {for(int j=1;j+i-1<=n;j++)//枚举区间长度 {int minh=5e4;int r=j+i-1;//得出右端点 for(int k=i;k<=r;k++)//枚举这个区间最矮的高度{if(h[k]<minh)minh=h[k];}//计算最大面积int s=j*minh; //cout<<s<<" "<<j<<" "<<minh<<endl;if(s>maxv)maxv=s;}}cout<<maxv;return 0;
}

4、有趣的数

我们把一个数称为有趣的，当且仅当：

它的数字只包含 0,1,2,3 ，且这四个数字都出现过至少一次。所有的 0 都出现在所有的 1 之前，而所有的 2 都出现在所有的
3 之前。最高位数字不为 0 。因此，符合我们定义的最小的有趣的数是 2013 。

除此以外，4 位的有趣的数还有两个：2031 和 2301 。

请计算恰好有 n 位的有趣的数的个数。

由于答案可能非常大，只需要输出答案除以 1e9+7 的余数。

输入格式
输入只有一行，包括恰好一个正整数 n 。

输出格式
输出只有一行，包括恰好 n 位的整数中有趣的数的个数除以 1e9+7 的余数。

数据范围
4≤n≤1000
输入样例：
4
输出样例：
3

思路：

运用了排列组合的数学知识，第一个位置不可能放0或者1（最高位不能是0但是0必须在1之前，所以第一位也不可能是1），假设有n个位置，所以我们就从剩下的n-1个位置挑i个位置放0或1，这i个0或1则有i-1种放置方法，然后剩下的n-i个位置中的2或者3则有n-i-1种放置方法，这三条是乘法关系，得到公式：

C[n-1][i]*(i-1)%mod*(n-i-1)

最后注意数字过大，记得开long long 和运用题目中的mod

代码：

#include<bits/stdc++.h>using namespace std;const int mod=1e9+7,N=1010;
int n; typedef long long LL;
LL C[N][N];
int main()
{//假设01选k个： //先选k个01填充（C n-1 k，这n-1是因为第一位不能是0或者1），其中01序列中的组合数量是（k-1） 种//剩下的23组合同理 有（n-k-1）  种类//相乘 //依次把每个k的取值都叠加（从2到n-2） cin>>n;//预处理出所有组合数 for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){if(!j)C[i][j]=1;else {C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}}}LL res=0;for(int i=2;i<=n-2;i++){res=(res+(LL)C[n-1][i]*(i-1)%mod*(n-i-1))%mod;}cout<<res;return 0;
}

5、I’m stuck!

给定一个 R 行 C 列的地图，地图的每一个方格可能是 #, +, -, |, ., S, T 七个字符中的一个，分别表示如下意思：

#: 任何时候玩家都不能移动到此方格；
+: 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格；
-: 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非 # 方格移动一格；
|: 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非 # 方格移动一格；
.:当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为 #，则玩家不能再移动；
S:玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格；
T: 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非#方格移动一格。
此外，玩家不能移动出地图。

请找出满足下面两个性质的方格个数：

玩家可以从初始位置移动到此方格；
玩家不可以从此方格移动到目标位置。
输入格式
输入的第一行包括两个整数 R 和 C，分别表示地图的行和列数。

接下来的 R 行每行都包含 C 个字符。它们表示地图的格子。地图上恰好有一个 S 和一个 T。

输出格式
如果玩家在初始位置就已经不能到达终点了，就输出 I’m stuck!。

否则的话，输出满足性质的方格的个数。

数据范围 1≤R,C≤50

思路：

我用的方法比较笨拙，代码量也比较大，调试也花费了很长时间，但是代码运行速度有保证，耗时约200ms，下面讲解我的思路：

任务目标：
1、确定原点能到达的所有位置（来检测条件1：玩家可以从初始位置移动到此方格；）,为此，写一个dfs函数，从原点出发，结合一个st数组，把能到达的格子都标记上true，以便后续用；
2、确定能到达T的点的位置，为此再写一个dfs函数，对于每个点都dfs一下，结合另一个st数组，如果能到达就把这个点记录为true，最后对于每一个点都结合两个数组进行判断，输出结果；
3、需要注意的是，在程序开始的时候先从原点出发，用写的第二个函数来判断一下起点是否能到达终点，若不能到达终点则直接输出 I’m stuck! 并且return 0退出程序即可

代码：

#include<bits/stdc++.h> using namespace std;const int N=53;int r,c,cnt;char g[N][N];int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};int mark[N][N];struct id
{int x;int y;
};id target;
id start;bool sts[N][N],stt[N][N];void dfss(int x,int y)
{if(g[x][y]=='#' || mark[x][y]){return ;}mark[x][y]=1;if(g[x][y]=='S'){//cout<<'S'<<endl;sts[x][y]=1;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')dfss(nx,ny);}}else if(g[x][y]=='+'){//cout<<'+'<<endl;sts[x][y]=1;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')dfss(nx,ny);}}else if(g[x][y]=='-'){//cout<<'-'<<endl;sts[x][y]=1;for(int i=0;i<2;i++){int nx=x;int ny=y+dx[i];if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')dfss(nx,ny);}}else if(g[x][y]=='|'){//cout<<'|'<<endl;sts[x][y]=1;for(int i=2;i<4;i++){int nx=x+dy[i];int ny=y;if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')dfss(nx,ny);}}else if(g[x][y]=='.'){//cout<<'.'<<endl;sts[x][y]=1;int nx=x+1;int ny=y;if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')dfss(nx,ny);}else if(g[x][y]=='T'){//cout<<'T'<<endl;sts[x][y]=1;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')dfss(nx,ny);}}
}bool dfs1(int x,int y)
{if(g[x][y]=='#' || mark[x][y]){return false;}mark[x][y]=1;if(g[x][y]=='S'){//cout<<'S'<<endl;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')if(dfs1(nx,ny))return true;}}else if(g[x][y]=='+'){//cout<<'+'<<endl;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')if(dfs1(nx,ny))return true;}}else if(g[x][y]=='-'){//cout<<'-'<<endl;for(int i=0;i<2;i++){int nx=x;int ny=y+dx[i];if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')if(dfs1(nx,ny))return true;}}else if(g[x][y]=='|'){//cout<<'|'<<endl;for(int i=2;i<4;i++){int nx=x+dy[i];int ny=y;if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')if(dfs1(nx,ny))return true;}}else if(g[x][y]=='.'){//cout<<'.'<<endl;int nx=x+1;int ny=y;if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')if(dfs1(nx,ny))return true;}else if(g[x][y]=='T'){return true;//cout<<'T'<<endl;
// 		for(int i=0;i<4;i++)
// 		{
// 			int nx=x+dx[i];
// 			int ny=y+dy[i];
// 			if(!mark[nx][ny] && nx>0 && ny>0 && nx<=r && ny<=c && g[nx][ny]!='#')dfs1(nx,ny);
// 		}}return false;
}int main()
{scanf("%d%d",&r,&c);for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>g[i][j];if(g[i][j]=='T')target.x=i,target.y=j;if(g[i][j]=='S')start.x=i,start.y=j;//	cout<<start.x<<" "<<start.y<<endl;}}if(dfs1(start.x,start.y))stt[start.x][start.y]=1;
// 	cout<<st[1]<<endl;if(!stt[start.x][start.y]){printf("I'm stuck!");return 0;}//cout<<r<<" "<<c<<endl;
// 	for(int i=1;i<=r;i++)
// 	{
// 	    for(int j=1;j<=c;j++)
// 	    {
// 	        cout<<g[i][j];
// 	    }
// 	    cout<<endl;
// 	}
//	//cout<<"----------------------------------------"<<endl;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){mark[i][j]=0;}}//清空状态数组dfss(start.x,start.y);//cout<<"----------------------------------------"<<endl;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){mark[i][j]=0;}}for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){mark[i][j]=0;}}//清空状态数组if(dfs1(i,j))stt[i][j]=1;//cout<<"i,j: "<<i<<" "<<j<<" st0: "<<sts[i][j]<<" st1: "<<stt[i][j]<<endl;if(sts[i][j] && !stt[i][j])cnt++;}}printf("%d",cnt);return 0;
}