BZOJ4419: [Shoi2013]发微博-白红宇

BZOJ4419: [Shoi2013]发微博

阅读量：5304 次

发布时间：2019-06-14

本文共 1076 字，大约阅读时间需要 3 分钟。

【传送门：】

简要题意：

　　有n个人，m种操作

　　1.！x表示x发了一条朋友圈，所有x的朋友都可以看到

　　2.+ x y表示x和y成为了朋友

　　3.- x y表示x和y解除了朋友关系

　　注意，x和y是朋友，y和z是朋友，x和z不一定是朋友

　　最后求出每个人能看到多少条信息

题解：

　　用set来保存每个人的交际关系

　　对于x和y，y对x的贡献为：x和y为朋友时y发的消息数=x和y解除好友时y发的消息数-x和y刚刚成为朋友时y发的消息数

　　只要处理每个人发出的信息和收到的信息就可以了

参考代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;set
           
             S[210000];set
            
              :: iterator it;int s[210000],ans[210000];int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) S[i].clear(); char st[2]; memset(s,0,sizeof(s)); for(int i=1;i<=m;i++) { scanf("%s",st+1); if(st[1]=='!') { int x;scanf("%d",&x); s[x]++; } else if(st[1]=='+') { int x,y;scanf("%d%d",&x,&y); ans[x]-=s[y];ans[y]-=s[x]; S[x].insert(y);S[y].insert(x); } else { int x,y;scanf("%d%d",&x,&y); ans[x]+=s[y];ans[y]+=s[x]; S[x].erase(y);S[y].erase(x); } } for(int i=1;i<=n;i++) { for(it=S[i].begin();it!=S[i].end();it++) { ans[i]+=s[*it]; } } for(int i=1;i