Week12必做题
- 必做题1
-
- 必做题2
- 题目描述
- 输入格式
- 输出格式
- 输入样例
- 输出样例
- 思路
- 注意
- 代码
- 必做题3
-
必做题1
题目描述
给出n个数，zjm想找出出现至少(n+1)/2次的数， 现在需要你帮忙找出这个数是多少？
输入格式
本题包含多组数据：
每组数据包含两行。
第一行一个数字N(1<=N<=999999) ，保证N为奇数。
第二行为N个用空格隔开的整数。
数据以EOF结束。
输出格式
对于每一组数据，你需要输出你找到的唯一的数。
输入样例
5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1
输出样例
3
5
1
代码
#include <iostream>
#include <map>
using namespace std;
int main(int argc, char** argv) {
int n;
while(scanf("%d",&n)!=EOF)
{
map<int,int>mp;
for(int i=0;i<n;i++)
{
int now;
scanf("%d",&now);
if(mp.find(now)!=mp.end())
{
mp[now]++;
}
else
{
mp[now]=1;
}
}
for(auto it=mp.begin();it!=mp.end();it++)
{
if(it->second>=(n+1)/2)
{
printf("%d\n",it->first);
break;
}
}
}
return 0;
}
必做题2
题目描述
zjm被困在一个三维的空间中,现在要寻找最短路径逃生！
空间由立方体单位构成。
zjm每次向上下前后左右移动一个单位需要一分钟，且zjm不能对角线移动。
空间的四周封闭。zjm的目标是走到空间的出口。
是否存在逃出生天的可能性？如果存在，则需要多少时间？
输入格式
输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为L，R和C（皆不超过30）。
L表示空间的高度，R和C分别表示每层空间的行与列的大小。
随后L层，每层R行，每行C个字符。
每个字符表示空间的一个单元。’#‘表示不可通过单元，’.'表示空白单元。
zjm的起始位置在’S’，出口为’E’。每层空间后都有一个空行。
L，R和C均为0时输入结束。
输出格式
每个空间对应一行输出。
如果可以逃生，则输出如下
Escaped in x minute(s).
x为最短脱离时间。
如果无法逃生，则输出如下
Trapped!
输入样例
3 4 5
S...
.###.
.##..
###.#
#####
#####
##.##
##…
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
输出样例
Escaped in 11 minute(s).
Trapped!
思路
从起点开始在迷宫中进行BFS，因为是三维空间，所以每个点BFS时有六个方向，每当搜索到一个新的位置，将这一位置置为起点到该点的步数，直到遇到终点停止搜索。若搜索结束仍未到达终点，则终点不可达。
注意
这里需要注意的是使用scanf依次读入字符时行末换行的处理，开始想使用getchar()来在行末读取空行，但程序提交时出现运行时错误。
可在scanf中的%c前加空格，或者使用cin来解决。
代码
#include <iostream>
#include<stdio.h>
#include <queue>
using namespace std;
const int size=50;
int mp[size][size][size];
struct Node{
int x,y,z;
Node(int _x,int _y,int _z)
{
x=_x;y=_y;z=_z;
}
};
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
int main(int argc, char** argv) {
int l,r,c;
while(scanf("%d%d%d",&l,&r,&c)&&(l!=0||r!=0||c!=0))
{
int sx,sy,sz,tx,ty,tz;
char temp;
for(int i=1;i<=l;i++)
{
for(int j=1;j<=r;j++)
{
for(int k=1;k<=c;k++)
{
scanf(" %c",&temp);
if(temp=='S')
{
sz=i;sy=j;sx=k;
mp[i][j][k]=0;
}
else if(temp=='E')
{
tz=i,ty=j;tx=k;
mp[i][j][k]=-1;
}
else if(temp=='.')
mp[i][j][k]=-1;
else
mp[i][j][k]=-2;
}
}
}
queue<Node> q;
q.push({sx,sy,sz});
while(!q.empty())
{
Node now=q.front();
q.pop();
if(now.x==tx&&now.y==ty&&now.z==tz)
break;
int step=mp[now.z][now.y][now.x];
for(int i=0;i<6;i++)
{
if(now.z+dz[i]>=1&&now.z+dz[i]<=l
&&now.y+dy[i]>=1&&now.y+dy[i]<=r
&&now.x+dx[i]>=1&&now.x+dx[i]<=c
&&mp[now.z+dz[i]][now.y+dy[i]][now.x+dx[i]]==-1)
{
mp[now.z+dz[i]][now.y+dy[i]][now.x+dx[i]]=step+1;
q.push({now.x+dx[i],now.y+dy[i],now.z+dz[i]});
}
}
}
if(mp[tz][ty][tx]!=-1)
printf("Escaped in %d minute(s).\n",mp[tz][ty][tx]);
else
printf("Trapped!\n");
}
return 0;
}
必做题3
题目描述
东东每个学期都会去寝室接受扫楼的任务，并清点每个寝室的人数。
每个寝室里面有ai个人(1<=i<=n)。从第i到第j个宿舍一共有sum(i,j)=a[i]+…+a[j]个人
这让宿管阿姨非常开心，并且让东东扫楼m次，每一次数第i到第j个宿舍sum(i,j)
问题是要找到sum(i1, j1) + … + sum(im,jm)的最大值。且ix <= iy <=jx和ix <= jy <=jx的情况是不被允许的。也就是说m段都不能相交。
注：1 ≤ i ≤ n ≤ 1e6 , -32768 ≤ ai ≤ 32767 人数可以为负数。。。。(1<=n<=1000000)
输入格式
输入m，输入n。后面跟着输入n个ai
输出格式
输出最大和
输入样例
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
输出样例
6
8
思路
这里采用动态规划的思想。
设状态dp[i][j]为将前j个元素取i个子串的最大子串和，其中必取第j个元素a[j]（若不取第j个元素，这一情况在d[i][k]，k<j中必然已经讨论过了）。
所以状态转移方程dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][k]+a[j]),其中i-1=<k<j，max参数前者为将a[j]并入dp[i][j-1]的最后一个子串，后者为a[j]独自为一串。
但这样dp数组的空间复杂度太高，从转移方程可以看出，计算dp[i][j]只需要知道dp[i][j-1]，以及dp[i-1][k]（i-1=<k<=j）中的最大值即可
所以我们可以将dp数组第一维去掉，使用另一个一维数组fmax来记录将从j个元素中取i-1段中的最大值(即前一个状态中仅考虑前j个元素的最大值)，dp数组仅记录当前状态，即从前j个元素中取i段时的最大子串和。
所以转移方程变为，dp[j]=max(dp[j-1]+a[j],fmax[j-1]+a[j])。
最终答案即为dp数组中的最大值。
代码
#include <iostream>
#include<string.h>
using namespace std;
const int inf=1e9;
const int size=1e6+10;
int a[size];
int dp[size];
int fmax[size];
int main(int argc, char** argv) {
int m,n;
while(scanf("%d%d",&m,&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int ans;
dp[0]=0;
memset(fmax,0,sizeof(fmax));
for(int i=1;i<=m;i++)
{
ans=-inf;
for(int j=i;j<=n;j++)
{
dp[j]=max(dp[j-1]+a[j],fmax[j-1]+a[j]);
fmax[j-1]=ans;
ans=max(ans,dp[j]);
}
}
printf("%d\n",ans);
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
