注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

Coder-Strike 2014 - Finals Online Meeting  

2014-04-23 14:05:46|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://codeforces.com/contest/421/problem/C
题意:
给出一次会议的部分连续记录,+ 表示第a个人进来,- 表示第a个人出去。问哪几个人有可能是leader,leader满足的条件是从头到尾必须都在。
题解:
抓住几条规律即可得出,详见代码及注释

int n,m,f[N];
vector<int>v; //记录加进来的人
set<int>S; //模拟过程
set<int>::iterator it;
struct Node{
char str[5];
int t;
}node[N]; //记录所有的log

void init()
{
v.clear();
S.clear();
for(int i=1;i<=n;i++) f[i]=1;
fr(m) scanf("%s %d",node[i].str,&node[i].t);
}

void solve()
{
int ans=n;
fr(m) {
if(node[i].str[0] == '+')
{
//如果是中途加进来的,并且和上一个log相对(上一个log表示t最后一个走,这个log表示t第一个进来),表示中间有休息,符合条件
if(S.empty() && i-1 >= 0 && node[i-1].str[0] == '-' && node[i-1].t == node[i].t)
{
S.insert(node[i].t);
v.push_back(node[i].t);
continue;
}
//如果不是第一个加进来的,或者是中途加进来的,肯定不是leader
if(v.size() != 0 || i > 0)
{
if(f[node[i].t] == 1)
ans--;
f[node[i].t]=0;
}
S.insert(node[i].t);
v.push_back(node[i].t);
}
else
{
it=S.find(node[i].t);
//如果没有找到t,则表示t在记录之前已经加进来,则之前所有加进来的都不符合条件
if(it == S.end())
{
for(int j=0;j<(int)v.size();j++)
{
if(f[v[j]] == 1)
{
ans--;
f[v[j]]=0;
}
}
S.insert(node[i].t);
}

//如果不是最后一个走的,则不符合条件
if(S.size() != 1)
{
if(f[node[i].t] == 1)
{
ans--;
f[node[i].t]=0;
}
}
else //如果是最后一个走的,但不是休息的时候,也不是最后一个log,则不符合条件
{
if(i+1 < m && (node[i+1].str[0] != '+' || node[i+1].t != node[i].t))
{
if(f[node[i].t] == 1)
{
ans--;
f[node[i].t]=0;
}
}
}
S.erase(node[i].t);
}
}
//输出所有符合条件的
pf(ans);
int flag=0;
for(int i=1;i<=n;i++)
{
if(!f[i])
continue;
if(flag) printf(" ");
printf("%d",i);
flag=1;
}
if(ans)
pfn;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
while(sf2(n,m)!=EOF)
{
init();
solve();
}
return 0;
}


  评论这张
 
阅读(27)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017