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

本文主要是介绍【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
输入样例: 5 5

思路:

我用的方法比较笨拙,代码量也比较大,调试也花费了很长时间,但是代码运行速度有保证,耗时约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;
}

这篇关于【13年12月CCF计算机软件能力认证】:出现次数最多的数、ISBN号码、最大的矩形、有趣的数、I‘m stuck!的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131634

相关文章

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

nudepy,一个有趣的 Python 库!

更多资料获取 📚 个人网站:ipengtao.com 大家好,今天为大家分享一个有趣的 Python 库 - nudepy。 Github地址:https://github.com/hhatto/nude.py 在图像处理和计算机视觉应用中,检测图像中的不适当内容(例如裸露图像)是一个重要的任务。nudepy 是一个基于 Python 的库,专门用于检测图像中的不适当内容。该

poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

题意: 给一个n*n(50 * 50) 的数字迷宫,从左上点开始走,走到右下点。 每次只能往右移一格,或者往下移一格。 每个格子,第一次到达时可以获得格子对应的数字作为奖励,再次到达则没有奖励。 问走k次这个迷宫,最大能获得多少奖励。 解析: 拆点,拿样例来说明: 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫,走两次最大能获得多少奖励。 将每个点拆成两个