链接: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;
}