PAT乙级题目合集(76~95)
2019-02-13 本文已影响0人
恰似一碗咸鱼粥
1076
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
int main()
{
int N;
int password[100];
int cnt=0;
cin>>N;
for(int i=0;i<N;++i){
string input;
for(int j=1;j<=4;++j){
cin>>input;
if(input[2]=='T')password[cnt++]=input[0]-'A'+1;
}
}
for(int i=0;i<cnt;++i){
printf("%d",password[i]);
}
return 0;
}
1077
要去掉一个最大值和最小值，可以先把数组排序，然后输出的时候跳过第一项和最后一项。
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main()
{
int N,M;
scanf("%d %d",&N,&M);
for(int i=0;i<N;++i){
float G1=0,G2=0;
int sum=0,cnt=0;
int input[100];
scanf("%f",&G1);
for(int j=1;j<N;++j){
float temp;
scanf("%f",&temp);
if(temp>=0&&temp<=M)input[cnt++]=temp;
}
sort(input,input+cnt);
for(int i=1;i<cnt-1;++i)G2+=input[i];
sum=(G1+G2/(cnt-2))/2+0.5;
printf("%d\n",sum);
}
return 0;
}
1078
当重复的字母数量大于10时要单独处理，由于不超过一千，所以只需判断10~99与100~999。
#include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
#define intToChar(x) (x+'0')
#define charToInt(x) (x-'0')
using namespace std;
int main()
{
char tool;
string str1,str2;
scanf("%c",&tool);
getchar();
getline(cin,str1);
int head=0,last=0;
if(tool=='C'){
while(last!=str1.size()){
if(str1[head]==str1[last]&&head<str1.size()){
head++;
}
else if(head-last>1){
if(head-last<10)
str2+=intToChar(head-last);
else if(head-last>=10&&head-last<100){
str2+=intToChar((head-last)/10);
str2+=intToChar((head-last)%10);
}else if(head-last>=100){
str2+=intToChar((head-last)/100);
str2+=intToChar((head-last)%100/10);
str2+=intToChar((head-last)%10);
}
str2+=str1[last];
last=head;
}else{
str2+=str1[last++];
}
}
}else if(tool=='D'){
int num=0;
bool flag=false;
for(int i=0;i<str1.size();++i){
if(str1[i]>='0'&&str1[i]<='9'){
num*=10;
num+=charToInt(str1[i]);
flag=true;
}else if(flag){
for(int j=0;j<num;++j)str2+=str1[i];
num=0;
flag=false;
}else{
str2+=str1[i];
}
}
}
cout<<str2<<endl;
return 0;
}
1079
大整数加减要注意进位问题
#include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
#define charToNum(x) (x-'0')
using namespace std;
bool isOK(string x){
for(int i=0;i<x.size()/2;++i){
if(x[i]!=x[x.size()-i-1])
return true;
}
return false;
}
int main()
{
string number;
int cnt=0;
cin>>number;
while(isOK(number)){
if(++cnt>10){
printf("Not found in 10 iterations.\n");
return 0;
}
string copy=number,sum;
int index=0;
reverse(copy.begin(),copy.end());
for(int i=0;i<number.size();++i){
int temp=charToNum(copy[i])+charToNum(number[i]);
if(temp%10+index>=10){
sum+=((temp%10+index)%10+'0');
index=temp/10+1;
}else{
sum+=(temp%10+index+'0');
index=temp/10;
}
}
if(index!=0)
sum+=(index+'0');
reverse(sum.begin(),sum.end());
cout<<number<<" + "<<copy<<" = "<<sum<<endl;
number=sum;
}
cout<<number<<" is a palindromic number."<<endl;
return 0;
}
1080
硬核模拟，不管tmd时间复杂度，勇敢往下写就是了
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <stdio.h>
using namespace std;
struct stu{
int hw=-1;
int m=-1;
int f;
int all;
string id;
};
bool compare(stu a,stu b){
return a.all!=b.all?a.all>b.all:a.id<b.id;
}
int main()
{
int P,M,N,hw,m,f;
map<string,stu> lecture;
set<string> id;
string temp;
vector<stu> pass;
scanf("%d %d %d",&P,&M,&N);
for(int i=0;i<P;++i){
cin>>temp>>hw;
id.insert(temp);
lecture[temp].hw=hw;
}
for(int i=0;i<M;++i){
cin>>temp>>m;
id.insert(temp);
lecture[temp].m=m;
}
for(int i=0;i<N;++i){
cin>>temp>>f;
id.insert(temp);
lecture[temp].f=f;
}
for(auto i=id.begin();i!=id.end();i++){
if(lecture[*i].hw<200||lecture[*i].hw>900)continue;
if(lecture[*i].f>=lecture[*i].m)lecture[*i].all=lecture[*i].f;
else {
lecture[*i].all=lecture[*i].f*0.6+lecture[*i].m*0.4+0.5;
}
if(lecture[*i].all>=60){
lecture[*i].id=*i;
pass.push_back(lecture[*i]);
}
}
sort(pass.begin(),pass.end(),compare);
for(int i=0;i<pass.size();++i){
cout<<pass[i].id<<" "<<pass[i].hw<<" "<<pass[i].m<<" "<<pass[i].f<<" "<<pass[i].all<<endl;
}
return 0;
}
1081
输入可能有空格
#include <iostream>
#include <string>
using namespace std;
int main() {
int N;
string input;
cin>>N;
getchar();
for(int i=0;i<N;++i){
getline(cin,input);
if(input.size()<6){
cout<<"Your password is tai duan le."<<endl;
continue;
}
bool flag1=false,flag2=false,flag3=false;
for(int j=0;j<input.size();++j){
if((input[j]>='a'&&input[j]<='z')||(input[j]>='A'&&input[j]<='Z')){
flag1=true;
}else if(input[j]>='0'&&input[j]<='9'){
flag2=true;
}else if(input[j]=='.')continue;
else{
cout<<"Your password is tai luan le."<<endl;
flag3=true;
break;
}
}
if(!flag2&&flag1&&!flag3){
cout<<"Your password needs shu zi."<<endl;
}
if(!flag1&&flag2&&!flag3){
cout<<"Your password needs zi mu."<<endl;
}
if(flag1&&flag2&&!flag3){
cout<<"Your password is wan mei."<<endl;
}
}
return 0;
}
1082
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
int main() {
int N,min=20000,max=0,id_min,id_max;
cin>>N;
for(int i=0;i<N;++i){
int id,x,y;
scanf("%d %d %d",&id,&x,&y);
int d=x*x+y*y;
if(d<min){
min=d;
id_min=id;
}
if(d>max){
max=d;
id_max=id;
}
}
printf("%04d %04d\n",id_min,id_max);
return 0;
}
1083
map真好用.jpg
#include <iostream>
#include <map>
#include <stdio.h>
#include <math.h>
using namespace std;
map<int,int> cnt;
int main() {
int N,input;
scanf("%d",&N);
for(int i=1;i<=N;++i){
scanf("%d",&input);
cnt[abs(i-input)]++;
}
map<int,int>::iterator i=cnt.end();
i--;
for(;i!=cnt.begin();i--){
if(i->second>1)
printf("%d %d\n",i->first,i->second);
}
if(i->second>1)
printf("%d %d\n",i->first,i->second);
return 0;
}
1084
读懂题就好做了
#include <iostream>
#include <stdio.h>
#include <string>
#define charToInt(x) (x+'0')
using namespace std;
int main() {
int cnt;
string ques,ans;
cin>>ques>>cnt;
for(int i=0;i<cnt-1;++i){
int cnt=1;
for(int j=0;j<ques.size();++j){
if(j<ques.size()-1&&ques[j]==ques[j+1]){
cnt++;
}else{
ans+=ques[j];
ans+=charToInt(cnt);
cnt=1;
}
}
ques=ans;
ans="";
}
cout<<ques<<endl;
return 0;
}
1085
map不能排序哭哭，所以只能把它们放到vector里再排一次
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define toLower(x) (x-'A'+'a')
using namespace std;
struct schools{
double sum=0;
int people=0;
};
map<string,schools> cnt;
bool compare(pair<string,schools> a,pair<string,schools> b){
return a.second.sum!=b.second.sum?a.second.sum>b.second.sum:(a.second.people!=b.second.people?a.second.people<b.second.people:a.first<b.first);
}
int main() {
int N,grade;
string id,school;
vector<pair<string,schools> > save;
cin>>N;
for(int i=0;i<N;++i){
cin>>id>>grade>>school;
for(int j=0;j<school.size();++j){
if(school[j]>='A'&&school[j]<='Z')
school[j]=toLower(school[j]);
}
if(id[0]=='B'){
cnt[school].sum+=(grade/1.5);
}else if(id[0]=='A'){
cnt[school].sum+=grade;
}else{
cnt[school].sum+=(grade*1.5);
}
cnt[school].people++;
}
for(map<string,schools>::iterator i=cnt.begin();i!=cnt.end();i++){
i->second.sum=(int)i->second.sum;
save.push_back(make_pair(i->first,i->second));
}
sort(save.begin(),save.end(),compare);
cout<<save.size()<<endl;
int rank=0,temp=-1,add=0;
for(vector<pair<string,schools> >::iterator i=save.begin();i!=save.end();i++){
if(temp!=i->second.sum){
rank+=(add+1);
temp=i->second.sum;
add=0;
}else{
add++;
}
cout<<rank<<" "<<i->first<<" "<<i->second.sum<<" "<<i->second.people<<endl;
}
return 0;
}
1086
#include <iostream>
using namespace std;
int main() {
int a,b;
bool flag=false;
cin>>a>>b;
int sum=a*b;
while(sum!=0){
if(flag==true||sum%10!=0){
cout<<sum%10;
flag=true;
}
sum/=10;
}
return 0;
}
1087
只要一个数是2或者3或者5的倍数，cnt就自增1
#include <iostream>
using namespace std;
int main() {
int k,cnt=1;
cin>>k;
for(int i=1;i<=k;++i){
if(i%2==0||i%3==0||i%5==0)
cnt++;
}
cout<<cnt<<endl;
return 0;
}
1088
丙有可能是存在小数
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int main() {
int a=-1,b=-1,x,y,me;
cin>>me>>x>>y;
for(int i=1;i<=9;++i)
for(int j=0;j<=9;++j){
if(x*(10*j+i)==y*abs(9*i-9*j)){
a=i;
b=j;
}
}
if((a==-1&&b==-1))
cout<<"No Solution"<<endl;
else{
cout<<10*a+b<<" ";
me>10*a+b?cout<<"Gai"<<" ":(me==10*a+b?cout<<"Ping"<<" ":cout<<"Cong"<<" ");
me>10*b+a?cout<<"Gai"<<" ":(me==10*b+a?cout<<"Ping"<<" ":cout<<"Cong"<<" ");
me>((double)(10*b+a))/y?cout<<"Gai":(me==((double)(10*b+a))/y?cout<<"Ping":cout<<"Cong");
}
return 0;
}
1089
这是抄柳神的代码。。。
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
using namespace std;
int main() {
int N;
cin>>N;
vector<int> save(N+1);
for(int i=1;i<=N;++i){
cin>>save[i];
}
for(int i=1;i<N;++i){
for(int j=i+1;j<=N;++j){
vector<int> lie,a(N+1,1);
a[i]=-1;
a[j]=-1;
for(int k=1;k<=N;++k){
if(save[k]*a[abs(save[k])]<0)lie.push_back(k);//判断是否说谎
}
if(lie.size()==2&&a[lie[0]]+a[lie[1]]==0){
cout<<i<<" "<<j<<endl;
return 0;
}
}
}
cout<<"No Solution"<<endl;
return 0;
}
1090
之前的映射都是一对一，这次是一对多
#include <string.h>
using namespace std;
int main() {
int N,M,a,b;
map<int,vector<int> > mapper;
scanf("%d %d",&N,&M);
for(int i=0;i<N;++i){
scanf("%d %d",&a,&b);
mapper[a].push_back(b);
mapper[b].push_back(a);
}
for(int i=0;i<M;++i){
int cnt,search[1000];
scanf("%d",&cnt);
for(int j=0;j<cnt;++j){
scanf("%d",&search[j]);
}
bool find=false;
for(int j=0;j<cnt-1;++j){
for(int k=0;k<mapper[search[j]].size();++k){
int object=mapper[search[j]][k];
for(int m=j+1;m<cnt;m++){
if(object==search[m]){
printf("No\n");
find=true;
break;
}
}
if(find)break;
}
if(find)break;
}
if(!find)
printf("Yes\n");
}
return 0;
}
1091
#include <iostream>
using namespace std;
int main() {
int M,K;
cin>>M;
for(int i=0;i<M;++i){
cin>>K;
bool flag=false;
for(int j=1;j<10;++j){
if(K<10&&(K*K*j-K)%10==0){
cout<<j<<" "<<K*K*j<<endl;
flag=true;
break;
}
else if(K<100&&(K*K*j-K)%100==0){
cout<<j<<" "<<K*K*j<<endl;
flag=true;
break;
}
else if(K<1000&&(K*K*j-K)%1000==0){
cout<<j<<" "<<K*K*j<<endl;
flag=true;
break;
}
}
if(!flag){
cout<<"No"<<endl;
}
}
return 0;
}
1092
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N,M;
cin>>N>>M;
vector<int> mooncake(N,0);
int Max=0;
for(int i=0;i<M;++i){
int num;
for(int j=0;j<N;++j){
cin>>num;
mooncake[j]+=num;
Max=max(Max,mooncake[j]);
}
}
bool flag=true;
cout<<Max<<endl;
for(int i=0;i<N;++i){
if(mooncake[i]==Max){
if(flag){
cout<<i+1;
flag=false;
}else{
cout<<" "<<i+1;
}
}
}
return 0;
}
1093
两个getline之间不用加getchar，cin后加getline需要加getchar
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;
int main() {
bool ascii[128];
memset(ascii,0,sizeof(ascii));
string a,b;
getline(cin,a);
getline(cin,b);
for(int i=0;i<a.size();++i){
if(!ascii[a[i]]){
ascii[a[i]]=true;
cout<<a[i];
}
}
for(int i=0;i<b.size();++i){
if(!ascii[b[i]]){
ascii[b[i]]=true;
cout<<b[i];
}
}
return 0;
}
1094
setw()与setfill()函数可以实现类似printf的功能，setw设置输出的宽度，setfill设置补足的字符，它们的头文件是<iomanip>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <iomanip>
#define charToNum(x) (x-'0')
using namespace std;
bool isPrime(int x){
if(x==1)
return false;
for(int i=2;i*i<=x;++i){
if(x%i==0){
return false;
}
}
return true;
}
int main() {
string str;
int len,str_len;
cin>>str_len>>len;
cin>>str;
int cnt=0;
for(int i=0;i<=str_len-len;i++){
int num=0;
for(int j=i;j<i+len;++j){
num+=charToNum(str[j]);
if(j!=i+len-1)num*=10;
}
if(isPrime(num)){
cout<<setw(len)<<setfill('0')<<num;
return 0;
}
}
cout<<"404";
return 0;
}
1095
我发现最近有好几道直接hash映射无法解决的题，一般这种题涉及map的排序，解决方法是先用map保存输入，然后导入vector后再进行排序。
另外unordered_map好像比map高效一点(柳神说的
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
struct person{
string id;
int grade;
}exam[10000];
struct classroom{
int num=0;
int sum=0;
};
struct date{
string classroom;
int num;
};
unordered_map<string,classroom> type2;
bool compare(person a,person b){
return a.grade!=b.grade?a.grade>b.grade:a.id<b.id;
}
bool comparee(date a,date b){
return a.num!=b.num?a.num>b.num:a.classroom<b.classroom;
}
int main() {
int N,M;
scanf("%d %d",&N,&M);
for(int i=0;i<N;++i){
cin>>exam[i].id>>exam[i].grade;
type2[exam[i].id.substr(1,3)].num++;
type2[exam[i].id.substr(1,3)].sum+=exam[i].grade;
}
sort(exam,exam+N,compare);
int type;
for(int j=0;j<M;++j){
cin>>type;
if(type==1){
char test;
bool flag=false;
cin>>test;
printf("Case %d: 1 %c\n",j+1,test);
for(int i=0;i<N;++i){
if(exam[i].id[0]==test){
printf("%s %d\n",exam[i].id.c_str(),exam[i].grade);
flag=true;
}
}
if(!flag){
printf("NA\n");
}
}
else if(type==2){
string pos;
cin>>pos;
printf("Case %d: 2 %s\n",j+1,pos.c_str());
if(type2[pos].num!=0){
printf("%d %d\n",type2[pos].num,type2[pos].sum);
}else{
printf("NA\n");
}
}else if(type==3){
string day;
unordered_map<string,int> m;
vector<date> save;
cin>>day;
printf("Case %d: 3 %s\n",j+1,day.c_str());
for(int i=0;i<N;++i){
if(exam[i].id.substr(4,6)==day)m[exam[i].id.substr(1,3)]++;
}
for(auto i:m){
save.push_back({i.first,i.second});
}
sort(save.begin(),save.end(),comparee);
for(int i=0;i<save.size();++i){
printf("%s %d\n",save[i].classroom.c_str(),save[i].num);
}
if(save.size()==0)
printf("NA\n");
}
}
return 0;
}
