PAT乙级考前总结(四)

散列相关问题

1029 旧键盘 (20 分)

旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字,请你列出肯定坏掉的那些键。

输入格式:

输入在 2 行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过 80 个字符的串,由字母 A-Z(包括大、小写)、数字 0-9、以及下划线 _(代表空格)组成。题目保证 2 个字符串均非空。

输出格式:

按照发现顺序,在一行中输出坏掉的键。其中英文字母只输出大写,每个坏键只输出一次。题目保证至少有 1 个坏键。

#include <cstdio>

#include <vector>

#include <map>

using namespace std;

map<char,int> m;

int main()

{

vector <char> keys;//存坏键

char a[111],b[111];

scanf("%s %s",a,b);

int i=0,j=0;

while(a[i]!='\0')//two pointers

{

if(a[i]==b[j])//没坏

{

i++;j++;

}else//坏了

{

if(m[a[i]]==0)//之前没遇到

{

if(a[i]>='a'&&a[i]<='z')//如果是小写记录下并将对应大写设为已坏

{

keys.push_back(a[i]-32);

m[a[i]-32]=1;

}else keys.push_back(a[i]);//其余的直接记录

if(a[i]>='A'&&a[i]<='Z') m[a[i]+32]=1;//大写字母也要将对应小写设置

m[a[i]]=1; //统一设置为已坏

}

i++;//只移动输入的字符串的指针

}

}

vector <char>::iterator p=keys.begin();

int r=keys.size();

for(i=0;i<r;i++) printf("%c",p[i]);

return 0;

}

1033 旧键盘打字 (20 分)

旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键,打出的结果文字会是怎样?

输入格式:

输入在 2 行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出;每段文字是不超过 10​5​​ 个字符的串。可用的字符包括字母 [a-z, A-Z]、数字 0-9、以及下划线 _(代表空格)、,、.、-、+(代表上档键)。题目保证第 2 行输入的文字串非空。

注意:如果上档键坏掉了,那么大写的英文字母无法被打出。

#include <stdio.h>

#include <string.h>

int a[256];

char b[100010];

int main()

{

memset(a,1,sizeof(a));//初始化

gets(b);

int l=strlen(b);

for(int i=0;i<l;i++)

{

if(b[i]>='A'&&b[i]<='Z') b[i]=b[i]-'A'+'a';//化为小写

a[b[i]]=0;//置0

}

gets(b);

l=strlen(b);

for(int i=0;i<l;i++)

{

if(b[i]>='A'&&b[i]<='Z')

{

int low=b[i]-'A'+'a';

if(a[low]&&a['+'])  printf("%c",b[i]);

}else if(a[b[i]]) printf("%c",b[i]);

}

printf("\n");

return 0;

}

1038 统计同成绩学生 (20 分)
1039 到底买不买 (20 分)

大致的思路的差不多,建立表存入信息再根据输入判断或更新

1042 字符统计 (20 分)
1043 输出PATest (20 分)

这两题都是统计特定字符

#include <cstdio>

int s[6]={0};

char ss[6]={'P','A','T','e','s','t'};//按顺序存个数

using namespace std;

int main()

{

char c;

c=getchar();

while(c!='\n')

{

switch (c)//记录

{

case 'P': s[0]++;break;

case 'A': s[1]++;break;

case 'T': s[2]++;break;

case 'e': s[3]++;break;

case 's': s[4]++;break;

case 't': s[5]++;break;

}

c=getchar();

}

while(true)

{

int flag=0;

for(int i=0;i<6;i++)//按顺序输出

{

if(s[i])

{

printf("%c",ss[i]);s[i]--;

}else flag++;

}

if(flag==6) break;

}

return 0;

}

1047 编程团体赛 (20 分)
1059 C语言竞赛 (20 分)

C 语言竞赛是浙江大学计算机学院主持的一个欢乐的竞赛。既然竞赛主旨是为了好玩,颁奖规则也就制定得很滑稽:

  • 0、冠军将赢得一份“神秘大奖”(比如很巨大的一本学生研究论文集……)。
  • 1、排名为素数的学生将赢得最好的奖品 —— 小黄人玩偶!
  • 2、其他人将得到巧克力。

给定比赛的最终排名以及一系列参赛者的 ID,你要给出这些参赛者应该获得的奖品。

输入格式:

输入第一行给出一个正整数 N(≤10​4​​),是参赛者人数。随后 N 行给出最终排名,每行按排名顺序给出一位参赛者的 ID(4 位数字组成)。接下来给出一个正整数 K 以及 K 个需要查询的 ID。

输出格式:

对每个要查询的 ID,在一行中输出 ID: 奖品,其中奖品或者是 Mystery Award(神秘大奖)、或者是 Minion(小黄人)、或者是Chocolate(巧克力)。如果所查 ID 根本不在排名里,打印 Are you kidding?(耍我呢?)。如果该 ID 已经查过了(即奖品已经领过了),打印 ID: Checked(不能多吃多占)。

#include <stdio.h>

#include <math.h>

using namespace std;

int id[10000]={0};

bool su(int k)//判断素数

{

if(k==2) return true;

for(int i=2;i<=(int)sqrt(k)+1;i++)

{

if(k%i==0) return false;

}

return true;

}

void judge(int i)//判断得奖

{

if(id[i]==0)//不存在

{

printf("%04d: Are you kidding?\n",i);return;

}

if(id[i]<0) printf("%04d: Checked\n",i);//已经出现过

else if(id[i]==1)//第一

{

printf("%04d: Mystery Award\n",i);

}else if(su(id[i]))//小黄人

{

printf("%04d: Minion\n",i);

}else//巧克力

{

printf("%04d: Chocolate\n",i);

}

id[i]=-1;//记为已查

}

int main()

{

int x,n,k;

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&x);

id[x]=i;

}

scanf("%d",&k);

while(k--)

{

scanf("%d",&x);

judge(x);

}

return 0;

}

1065 单身狗 (25 分)

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

输入格式:

输入第一行给出一个正整数 N(≤ 50 000),是已知夫妻/伴侣的对数;随后 N 行,每行给出一对夫妻/伴侣——为方便起见,每人对应一个 ID 号,为 5 位数字(从 00000 到 99999),ID 间以空格分隔;之后给出一个正整数 M(≤ 10 000),为参加派对的总人数;随后一行给出这 M 位客人的 ID,以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式:

首先第一行输出落单客人的总人数;随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔,行的首尾不得有多余空格。

#include <stdio.h>

#include <set>

using namespace std;

int cp[100000]={-1},vistor[10010]={-1};//初始化

int main()

{

int n,m,id1,id2;

set<int> single;//存入单身狗

scanf("%d",&n);

for(int i=0;i<n;i++)

{

scanf("%d %d",&id1,&id2);

cp[id1]=id2;//每一对互相映射

cp[id2]=id1;

}

scanf("%d",&m);

for(int i=0;i<m;i++)

{

scanf("%d",&vistor[i]);

if(cp[vistor[i]]==-1) single.insert(vistor[i]);//绝对单身直接记录

else cp[vistor[i]]+=100000;//有对象但不知道对象来没来,所以做标记

}

for(int i=0;i<m;i++)

{

if(cp[vistor[i]]>=100000)//有对象的

{

if(cp[cp[vistor[i]]-100000]>=100000)//根据映射,检验其对象是否来了

{

cp[vistor[i]]-=100000;

cp[cp[vistor[i]]]-=100000;

}

else single.insert(vistor[i]);//没来的话就算单身(?黑人问号脸?)

}

}

printf("%d\n",single.size());

for(set<int>::iterator it=single.begin();it!=single.end();it++)

{

if(it==single.begin()) printf("%05d",*it);

else printf(" %05d",*it);

}

return 0;

}

1068 万绿丛中一点红 (20 分)

对于计算机而言,颜色不过是像素点对应的一个 24 位的数值。现给定一幅分辨率为 M×N 的画,要求你找出万绿丛中的一点红,即有独一无二颜色的那个像素点,并且该点的颜色与其周围 8 个相邻像素的颜色差充分大。

输入格式:

输入第一行给出三个正整数,分别是 M 和 N(≤ 1000),即图像的分辨率;以及 TOL,是所求像素点与相邻点的颜色差阈值,色差超过 TOL 的点才被考虑。随后 N 行,每行给出 M 个像素的颜色值,范围在 [0,2​24​​) 内。所有同行数字间用空格或 TAB 分开。

输出格式:

在一行中按照 (x, y): color 的格式输出所求像素点的位置以及颜色值,其中位置 x 和 y 分别是该像素在图像矩阵中的列、行编号(从 1 开始编号)。如果这样的点不唯一,则输出 Not Unique;如果这样的点不存在,则输出 Not Exist。

#include <iostream>

#include <map>

#include <algorithm>

using namespace std;

int color[1010][1010]={0};

int m,n,tol;

struct sp

{

int co;

int x,y;

}ans;

map<int,int> num;

bool judge(int i,int j)

{

for(int y=max(1,i-1);y<=min(i+1,n);y++)

{

for(int x=max(1,j-1);x<=min(m,j+1);x++)

{

if(x!=j&&i!=y)

{

if(color[i][j]-color[y][x]<=tol&&color[i][j]-color[y][x]>=-tol) return false;

}

}

}

return true;

}

int main()

{

cin>>m>>n>>tol;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++)

{

cin>>color[i][j];num[color[i][j]]++;

}

}

int count=0;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++)

{

if(judge(i,j))

{

if(num[color[i][j]]==1)

{

ans.co=color[i][j];ans.x=j;ans.y=i;

count++;

}

}

}

}

if(count>1) cout<<"Not Unique";

else if(count==0) cout<<"Not Exist";

else cout<<'('<<ans.x<<", "<<ans.y<<"): "<<ans.co;

return 0;

}

第三个点老是不过,实在不知道哪里有问题了。。

1072 开学寄语 (20 分)1082 射击比赛 (20 分)1083 是否存在相等的差 (20 分)
记录并统计,一般的方法
1090 危险品装箱 (25 分)

集装箱运输货物时,我们必须特别小心,不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱,否则很容易造成爆炸。

本题给定一张不相容物品的清单,需要你检查每一张集装箱货品清单,判断它们是否能装在同一只箱子里。

输入格式:

输入第一行给出两个正整数:N (≤10​4​​) 是成对的不相容物品的对数;M (≤100) 是集装箱货品清单的单数。

随后数据分两大块给出。第一块有 N 行,每行给出一对不相容的物品。第二块有 M 行,每行给出一箱货物的清单,格式如下:

K G[1] G[2] ... G[K]

其中 K (≤1000) 是物品件数,G[i] 是物品的编号。简单起见,每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。

输出格式:

对每箱货物清单,判断是否可以安全运输。如果没有不相容物品,则在一行中输出 Yes,否则输出 No。

和单身狗那一题不一样,这里可能存在多对一的情况,如果直接储存会使得数据覆盖。我先是用字符串存的map,虽然不错,但是判断时是遍历所有的情况,果然超时了。参考了大神方法,于是为了解决一对多的问题,映射到vector,原本想到用数组,但是太大。然后判断时可以直接跳过不存在于不相容列表的物品,再一一比较,虽然有多重循环,却没有超时。

#include <iostream>

#include <map>

#include <vector>

using namespace std;

int n,m,k;

map<string,vector<string> > cp;

string temp[10010];

bool judge()

{

for(int i=0;i<k;i++)

{

if(cp[temp[i]].size()>0)

{

for(int j=i+1;j<k;j++)

{

for(int l=0;l<cp[temp[i]].size();l++)

{

if(temp[j]==cp[temp[i]][l]) return false;

}

}

}

}

return true;

}

int main()

{

cin>>n>>m;

string a,b;

for(int i=0;i<n;i++)

{

cin>>a>>b;

cp[a].push_back(b);

cp[b].push_back(a);

}

for(int i=0;i<m;i++)

{

cin>>k;

for(int j=0;j<k;j++) cin>>temp[j];

if(judge()) cout<<"Yes"<<endl;

else cout<<"No"<<endl;

}

return 0;

}

上一篇:Luogu P1494 [国家集训队]小Z的袜子


下一篇:JQ 复制节点