链接:https://www.nowcoder.com/acm/contest/204/J
来源:牛客网
题目描述
某个 QQ 群里一共有 n 个人,他们的编号是 1…n,其中有一些人本质上是复读机。
小 A 发现,如果一个人的本质是复读机,那么他每次发的消息一定跟群里的上一条消息一样,特别地第一个发消息的人一定不是复读机。
现在小 A 搞到了一份聊天记录,他想请你找出所有可能是复读机的群友
输入描述:
第一行两个正整数 n,m,表示群里的人数和聊天记录的总条数
接下来 m 行按时间顺序给出聊天记录,每行有一个正整数 x 和一个小写字母字符串 S,表示群友 x 发了消息 S
输出描述:
输出一行,将所有可能是复读机的群友的编号按照从小到大排序后输出,每两个编号之间隔一个空格
示例1
输入
复制
3 5
1 gugugu
2 gugugu
1 gugu
3 tingzhifudu
2 tingzhifudu
输出
复制
2
备注:
1≤ n≤ 103
1≤ m≤ 103
1≤ |S|≤ 100
水题卡了很久…
两个点没看清楚,首先只要出现一次没有复读,那这个人肯定不是复读机,所以我们就只要排除掉这些,其他都是有可能是复读机的
代码:
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int n,m;
const int N=1e3+50;
int vis[N];
set<int> ans;
vector<int> res;
int main(void){
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
string pre="";
string now="";
int preId=0;
int nowId=0;
cin >> preId >> pre;
m--;
while(m--){
cin >> nowId >> now;
if(now==pre){
if(vis[nowId]!=-1){
vis[nowId]=1;
}
}
else{
vis[nowId]=-1;
}
pre=now;
preId=nowId;
}
for(int i=1;i<N;i++){
if(vis[i]==1){
res.push_back(i);
}
}
int l=res.size();
if(l==0){
//printf("\n");
return 0;
}
for(int i=0;i<l-1;i++){
printf("%d ",res[i]);
}
printf("%d\n",res[l-1]);
return 0;
}