散列相关问题
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 行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出；每段文字是不超过 105 个字符的串。可用的字符包括字母 [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（≤104），是参赛者人数。随后 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,224) 内。所有同行数字间用空格或 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 (≤104) 是成对的不相容物品的对数；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;
}