目录
1.四个常见问题
2.c++STL的运用
18104 练习使用多case解题
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
多CASE的问题在般有3种情形：（1）有一个数字开始表明CASE数目；（2）以特殊标志表示结束；（3）要求处理到最后一行。 现要求你在程序一次运行中，依次处理上述3种情况。 有三批测试数据，第1批测试数据，开头会以一个数字告之该批CASE数量，每一个CASE是两个正整数； 第1批测试数据结束后，紧接着是第2批数据，每一个CASE同样是两个正整数，第2批测试数据以两个0结束； 第2批测试数据结束后，紧接着是第3批数据，每一个CASE也是两个正整数，第3批测试数据一直到数据输入结束； 要求，每一个CASE，输出两数的最小公倍数 第1批测试数据处理完毕时，输出“group 1 done” 第2批测试数据处理完毕时，输出“group 2 done” 第3批测试数据处理完毕时，输出“group 3 done”
输入格式
有三批测试数据，第1批测试数据，开头会以一个数字告之该批CASE数量，每一个CASE是两个正整数(最大2的31次方)； 第1批测试数据结束后，紧接着是第2批数据，每一个CASE同样是两个正整数，第2批测试数据以两个0结束； 第2批测试数据结束后，紧接着是第3批数据，每一个CASE也是两个正整数，第3批测试数据一直到数据输入结束；
输出格式
要求，每一个CASE，输出两数的最小公倍数 第1批测试数据处理完毕时，输出“group 1 done” 第2批测试数据处理完毕时，输出“group 2 done” 第3批测试数据处理完毕时，输出“group 3 done”
输入样例
2 6 10 5 12 8 16 12 18 8 4 0 0 4 5 4 6
输出样例
30 60 group 1 done 16 36 8 group 2 done 20 12 group 3 done
#include <iostream>
using namespace std;
long long gcd(long long x,long long y)
{
long long r=x%y;
while(r!=0)
{
x=y;
y=r;
r=x%y;
}
return y;
}
int main()
{
long long n,a,b,c;
cin>>n;
while(n--)
{
cin>>a>>b;
c=a*b/gcd(a,b);
cout<<c<<endl;
}
cout<<"group 1 done"<<endl;
while(cin>>a>>b)
{
if(a==0&&b==0) break;
c=a*b/gcd(a,b);
cout<<c<<endl;
}
cout<<"group 2 done"<<endl;
while(cin>>a>>b)
{
c=a*b/gcd(a,b);
cout<<c<<endl;
}
cout<<"group 3 done"<<endl;
return 0;
}
19116 丑数
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
“丑数”是指除了质因子2,3，5，不含其它质因子的正整数，例如由小到大前10个“丑数”为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ... 现要求编写一个程序，输出指定第几位的“丑数”。
输入格式
第一行为正整数T（T<=10000）, 表示case的数目。 此后T行，每行一个正整数 n (n <= 100000000).
输出格式
每一个n，输出第n个“丑数”
输入样例
3 1 2 9
输出样例
1 2 10
#include <iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
using namespace std;
long long ugly(long long x)
{
priority_queue<long long ,vector<long long>,greater<long long>>pq;
set<long long>s;
s.insert(1);
pq.push(1);
long long cur=1;
while(1)
{
if(cur==x) return pq.top();
long long y=pq.top();
pq.pop();
if(s.find(y*2)==s.end())
{
pq.push(y*2);
s.insert(y*2);
}
if(s.find(y*3)==s.end())
{
pq.push(y*3);
s.insert(y*3);
}
if(s.find(y*5)==s.end())
{
pq.push(y*5);
s.insert(y*5);
}
cur++;
}
}
int main()
{
long long T,n;
cin>>T;
while(T--)
{
cin>>n;
long long h=ugly(n);
cout<<h<<endl;
}
return 0;
}
18440 走迷宫
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
Description
有一个N*M(N,M<=10)的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，人在迷宫中可以尝试上下左右四个方向移动。 另外，在迷宫中如果从左边走出迷宫会回到迷宫最右边一格（只要该格不是墙），行不变，同样，从右边走出迷宫会 回到迷宫最左边一格，向上走出迷宫会回到迷宫最下边一格，向下走出迷宫会回到迷宫最上边一格。 现在给定一个迷宫，以及起点和终点，问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。
输入格式
该程序为多CASE，第1行为CASE的数量 每一个CASE，第1行为两个数N（行）和M（列） 然后N行每行M个数，之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)
输出格式
如题
输入样例
2 4 3 011 010 110 110 0 0 3 2 2 2 01 10 0 0 1 1
输出样例
4 die
提示
第一个case，可以从（1，0）走到（1，2）
#include<iostream>
#include<cstring>
using namespace std;
char mapp[13][13];
int mm[13][13];
int xnext[4]={0,1,0,-1};//右下左上
int ynext[4]={1,0,-1,0};
int xsta,ysta,xend,yend;
int n,m;
bool flag=false;
void find_way(int x0,int y0)
{
if(x0==xend&&y0==yend)
{
flag=true;
return;
}
for(int i=0;i<4;i++)
{
int x1=(x0+xnext[i]+n)%n;
int y1=(y0+ynext[i]+m)%m;
if(mapp[x1][y1]=='0')
{
if(mm[x1][y1]==-1)
{
mm[x1][y1]=mm[x0][y0]+1;
mapp[x1][y1]='1';
find_way(x1,y1);
mapp[x1][y1]='0';
}
}
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
memset(mm,-1,sizeof(mm));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mapp[i][j];
}
}
cin>>xsta>>ysta>>xend>>yend;
mm[xsta][ysta]=0;
flag=false;
find_way(xsta,ysta);
if(flag) cout<<mm[xend][yend]<<endl;
else cout<<"die"<<endl;
}
}
18276 走迷宫2
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
Description
有一个N*M的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，另外，在迷宫中 有一些传送门，走到传送门的入口即会自动被传送到传送门的出口（一次传送算1步）。人在迷宫中可以尝试 上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口，以及起点和终点， 问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。
输入格式
该程序为多CASE，第1行为CASE的数量 每一个CASE，第1行为两个数N（行）和M（列） 然后N行每行M个数 之后是一个数W，为传送门的数量 之后每行一个传送门的入口坐标c1(行),r1(列)和出口坐标c2,r2 之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列) 注：传送门出入口和起点坐标和终点坐标不会出现在墙的位置 所有数字不超过100
输出格式
如题
输入样例
2 4 3 011 011 110 110 1 1 0 2 2 0 0 3 2 2 2 01 10 0 0 0 1 1
输出样例
3 die
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m,w,c1,r1,c2,r2,sc,sr,ec,er;
char g[N][N];
int d[N][N];
PII door[N][N];
void bfs(){
memset(d,-1,sizeof(d));
d[sc][sr]=0;
queue<PII>q;
q.push({sc,sr});
while(!q.empty()){
PII t=q.front();
q.pop();
if(door[t.x][t.y].x!=-1&&door[t.x][t.y].y!=-1){
d[door[t.x][t.y].x][door[t.x][t.y].y]=d[t.x][t.y]+1;
q.push({door[t.x][t.y].x,door[t.x][t.y].y});
continue;
}
int dir[4][2]={0,1,0,-1,1,0,-1,0};
for(int i=0;i<4;++i){
int x=t.x+dir[i][0],y=t.y+dir[i][1];
if(x>=0&&x<n&&y>=0&&y<n&&g[x][y]!='1'&&d[x][y]==-1){
d[x][y]=d[t.x][t.y]+1;
q.push({x,y});
}
}
}
}
int main(){
int kcase;
cin>>kcase;
while(kcase--){
cin>>n>>m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
door[i][j].x=door[i][j].y=-1;
}
}
for(int i=0;i<n;++i){
cin>>g[i];
getchar();
}
cin>>w;
for(int i=0;i<w;++i){
cin>>c1>>r1>>c2>>r2;
door[c1][r1].x=c2;
door[c1][r1].y=r2;
}
cin>>sc>>sr>>ec>>er;
bfs();
if(d[ec][er]==-1){
cout<<"die"<<endl;
}else{
cout<<d[ec][er]<<endl;
}
}
return 0;
}
18105 银行的叫号顺序
时间限制:8000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
Description
银行的叫号过程是一个优先队列的典型应用，假设，银行有4类客户，分别用优先级1，2，3，4表示，级别越高 则更优先得到服务，例如，当前有三个人排队，两个1级客户，一个3级客户，则银行叫号时，3级客户将先得到服务 ，即使另两个1级有客户比他先到。当多个同级的客户将获得服务时，由先到的客户先得到服务。 假设，银行只有一个服务窗口，一次只能服务一个客户，假设该窗口每5分钟服务一个客户，即叫号的时刻分别 为0分钟、5分钟、10分钟、.....如果在叫号的时侯，没有客户，银行职员会去喝杯咖啡或上个洗手间，5分钟后 再继续叫号。 银行给出一系列客户到来的记录，每条记录包括“客户到来的时”，“客户等级”，“客户姓名”（由一个单词构成），请输 出银行服务的客户的顺序。
输入格式
第一数字是客户的数量n（n<=100000） 此后，每一行是一个客户来访信息，包括3个数字，到来的时刻（分钟整点,最大10的8次方）、等级、姓名（最多20个字母） （已经按到来时刻排序）
输出格式
按服务的先后顺序输出客户的姓名
输入样例
4 0 1 John 3 1 Smith 3 1 Tom 4 2 Flod
输出样例
John Flod Smith Tom
#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
typedef pair<int,string>PIS;
priority_queue<PIS>q;
int main()
{
int n;
int ret=99999;
int lev,time ,realtime=0;
string name;
cin>>n;
while(n--)
{
cin>>time>>lev>>name;
while(1)
{
if(time<=realtime)
{
q.push({lev*100000+ret,name});
ret--;
break;
}
if(!q.empty())
{
cout<<q.top().second<<endl;
q.pop();
}
realtime+=5;
}
}
while(!q.empty())
{
cout<<q.top().second<<endl;
q.pop();
}
}18216 银行服务
时间限制:8000MS 代码长度限制:10KB
提交次数:100 通过次数:8
题型: 编程题 语言: G++;GCC;VC
Description
银行通过叫号来决定服务用户的顺序，假设，银行有4类客户，分别用优先级1，2，3，4表示，级别越高 则更优先得到服务，例如，当前有三个人排队，两个1级客户，一个3级客户，则银行叫号时，3级客户将先得到服务 ，即使另两个1级的客户比他先到。当多个同级的客户将获得服务时，由先到的客户先得到服务。 假设，银行只有一个服务窗口，一次只能服务一个客户，假设该窗口每5分钟服务一个客户，即叫号的时刻分别 为0分钟、5分钟、10分钟、.....如果在叫号的时侯，没有客户，银行职员会去喝杯咖啡或上个洗手间，5分钟后 再继续叫号。 有一种情况，银行工作到一定时间是要下班的，所以到一定时间，如果后面还有客户，将不再提供服务。 银行给
出一系列客户到来的记录，每条记录包括“客户到来的时间”，“客户等级”，“客户姓名”（由一个单词构成），请输 出该银行这一轮服务的客户的顺序。
输入格式
第一行两个数字，第一数字是客户的数量n（n<=100000），第二个数字是银行关门的时间，到这个时间，即关门，该点及之后， 不再叫号，但之前已经叫号的客户会继续服务到完结。 此后，每一行是一个客户来访信息，包括3个数字，到来的时刻（分钟整点,最大10的8次方）、等级、姓名（最多20个字母） （已经按到来时刻排序，注意：同一时刻可能会同时到来多个客户，这时若为同等级的，数据出现得早的稍早得到服务）
输出格式
按服务的先后顺序输出客户的姓名
输入样例
4 12 0 1 John 3 1 Smith 3 1 Tom 4 2 Flod
输出样例
John Flod Smith
#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
typedef pair<int,string>PIS;
priority_queue<PIS>q;
int main()
{
int n,t0;
int ret=99999;
int lev,time ,realtime=0;
string name;
cin>>n>>t0;
while(n--)
{
cin>>time>>lev>>name;
while(1)
{
if(time<=realtime)
{
q.push({lev*100000+ret,name});
ret--;
break;
}
if(!q.empty())
{
cout<<q.top().second<<endl;
q.pop();
}
realtime+=5;
}
}
while(!q.empty())
{
if(realtime>=t0) break;
cout<<q.top().second<<endl;
q.pop();
realtime+=5;
}
}18118 勇者斗恶龙
时间限制:800MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
Description
有n个头的恶龙，你希望雇一些骑士把它杀死（即砍掉所有头）。村里有ｍ个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙 一个直径不超过x的头，且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头，且需要支付的金币最少？注意，一个骑士只 能砍一个头（且不能被雇佣两次）
输入格式
多组数据，每组数据的第一行为正整数n和m(1<=n,m<=200000)；以下n行每行为一个整数，即恶龙每个头的直径；以下m行每行为 一个整数，即每个骑士的能力。输入结束标志ｎ＝ｍ＝0;
输出格式
输出格式：每组数据，输出最少花费，无解输出"Loowater is doomed!"
输入样例
2 3 5 4 7 8 4 2 1 5 5 10 0 0
输出样例
11 Loowater is doomed!
#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int maxn =200001;
int A[maxn],B[maxn];
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0) break;
for(int i=0;i<n;i++) cin>>A[i];
for (int i=0;i<m;i++) cin>>B[i];
sort(A,A+n);
sort(B,B+m);
int cur=0,cost=0;
for(int i=0;i<m;i++)
{
if(B[i]>=A[cur])
{
cost=cost+B[i];
cur++;
if(cur==n) break;
}
}
if(cur<n)
{
cout<<"Loowater is doomed!"<<endl;
}
else cout<<cost<<endl;
}
return 0;
}
18107 校赛排名
时间限制:4000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
Description
校赛结束了，每一个参赛选手由3个数据项构成（通过题数，用时分钟数，姓名），排名按照通过题数排序 通过题数多的排前，同题数的，罚时少的排前。如果题数相同，罚时也相同，而按数据读取的先后排。 给你N个参赛选手的数据，按排序先后，输出姓名
输入格式
第一个数为N，（N<=500000） 此后，每行一个参赛选手的数据，通过题数，用时分钟数，姓名，前两者为整型数，姓名为字符串（不多于20个字符）
输出格式
姓名排名
输入样例
4 3 5 Jon 5 100 Smith 3 5 Tom 6 95 Hel
输出样例
Hel Smith Jon Tom
提示
由于有500000个数据，输入和输出务必使用scanf和printf
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct Student
{
int cnt;
long long time;
char name[21];
} student[500000];
bool cmp(Student a,Student b)
{
if(a.cnt!=b.cnt) return a.cnt>b.cnt;
if(a.time!=b.time) return a.time<b.time;
return false;
}
int main()
{
long long n;
cin>>n;
for(int i=0; i<n; i++)
{
scanf("%d%d%s",&student[i].cnt,&student[i].time,&student[i].name);
}
stable_sort(student,student+n,cmp);
for(int i=0; i<n; i++)
{
printf("%s\n",student[i].name);
}
return 0;
}