「CF420B」Online Meeting
Nearly each project of the F company has a whole team of developers working on it. They often are in different rooms of the office in different cities and even countries. To keep in touch and track the results of the project, the F company conducts shared online meetings in a Spyke chat.
One day the director of the F company got hold of the records of a part of an online meeting of one successful team. The director watched the record and wanted to talk to the team leader. But how can he tell who the leader is? The director logically supposed that the leader is the person who is present at any conversation during a chat meeting. In other words, if at some moment of time at least one person is present on the meeting, then the leader is present on the meeting.
You are the assistant director. Given the ‘user logged on’/’user logged off’ messages of the meeting in the chronological order, help the director determine who can be the leader. Note that the director has the record of only a continuous part of the meeting (probably, it’s not the whole meeting).
The first line contains integers n and m (1 ≤ n, m ≤ 105) — the number of team participants and the number of messages. Each of the next m lines contains a message in the format:
- ‘+ id‘: the record means that the person with number id (1 ≤ id ≤ n) has logged on to the meeting.
- ‘– id‘: the record means that the person with number id (1 ≤ id ≤ n) has logged off from the meeting.
Assume that all the people of the team are numbered from 1 to n and the messages are given in the chronological order. It is guaranteed that the given sequence is the correct record of a continuous part of the meeting. It is guaranteed that no two log on/log off events occurred simultaneously.
In the first line print integer k (0 ≤ k ≤ n) — how many people can be leaders. In the next line, print k integers in the increasing order — the numbers of the people who can be leaders.
If the data is such that no member of the team can be a leader, print a single number 0.
1 2 3 4 5 |
5 4 + 1 + 2 - 2 - 1 |
1 2 |
4 1 3 4 5 |
1 2 3 |
3 2 + 1 - 2 |
1 2 |
1 3 |
1 2 3 4 5 |
2 4 + 1 - 1 + 2 - 2 |
1 |
1 2 3 4 5 6 7 |
5 6 + 1 - 1 - 3 + 3 + 4 - 4 |
1 2 |
3 2 3 5 |
1 2 3 4 5 |
2 4 + 1 - 2 + 2 - 1 |
1 |
题解
给你会场的进出记录(部分),问有多少人满足:
当有人在场内的时候总是在场内
首先倒序处理出一开始在场内的人
顺序模拟,一个人如果离开的时候场内有人或者有人进入,则他不满足
顺便求出最后在场内的人
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,tot,ans,last; int x[100001]; char ch[100001][2]; bool a[100001],b[100001],del[100001]; int main() { memset(b,1,sizeof(b)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%s",ch[i]); scanf("%d",&x[i]); } for(int i=m;i>0;i--) { if(ch[i][0]=='-') a[x[i]]=1; else a[x[i]]=0; } for(int i=1;i<=n;i++) if(a[i])tot++; for(int i=1;i<=m;i++) { if(ch[i][0]=='-') { tot--; if(tot>0)del[x[i]]=1; last=x[i]; if(i!=m&&!tot)b[x[i]]=0; } else { if(tot>0||((x[i]!=last)&&last))del[x[i]]=1; tot++; b[x[i]]=1; } } for(int i=1;i<=n;i++) if(!del[i]&&b[i]) ans++; printf("%d\n",ans); for(int i=1;i<=n;i++) if(!del[i]&&b[i]) printf("%d ",i); return 0; } |
分类目录
热门文章
- 10817小鱼系列简单题参考代码
- 9069NOIP2011铺地毯
- 8832「BZOJ1972」[SDOI2010] 猪国杀
- 83592017ACM萧山训练第4场(CTUO 2015)
- 8192「CF718X」Codeforces Round #373 (Div. 1)
- 8180NOIP2001数的计算
- 8122「BZOJ1033」[ZJOI2008] 杀蚂蚁antbuster
- 7907NOIP2005陶陶摘苹果
- 7644NOIP2011选择客栈
- 7170「BZOJ2304」[APIO2011] 寻路path
- 6790NOIP2011统计单词数
- 6719「CF538X」Codeforces Round #300
- 6559「BZOJ1647」[Usaco2007 Open] Fliptile 翻格子游戏
- 6504NOIP2004津津的储蓄计划
- 6294「codechef」January Challenge 2015
- 6232NOIP2009潜伏者
- 6180NOIP2013表达式求值
- 61032017ACM萧山训练第1场(NEERC 2016)
- 6013NOIP2010三国游戏
- 5990「topcoder」Kodifica - Pratice Round 1
- 5796NOIP2009分数线划定
- 5788魔兽世界之一:备战 / 魔兽世界之二:装备
- 57702016 CCPC Changchun Onsite
- 5729NOIP1999回文数
- 5720NOIP2004花生采摘
- 5715NOIP2007统计数字
- 5661「CODEVS1384」黑色星期五
- 5617NOIP2006明明的随机数
- 5611NOIP2003乒乓球
- 5517NOIP2012Vigenère密码
- 5512NOIP2004不高兴的津津
- 5478NOIP2010数字统计
- 5393Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
- 5303「CF551X」Codeforces Round #307 (Div. 2)
近期评论
- 匿名发表在《留言板》
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《留言板》