H - Message Bomb Gym - 102798H

題意：

有n個團隊，m個人，s個操作
操作1：學生x加入y團隊
操作2：學生x推出y團隊
操作3：學生x在團隊y發送一個信號，在團隊y內的所有成員（除了x）都收到一個信號
所有操作結束后，問每個學生收到多少信號？
1≤n≤100000,1≤m≤200000,1≤s≤1000000)

題解：

我的思路一開始直接跑偏，都跑到樹剖上，還好隊友把我拉了回來
不要被數據范圍所嚇倒
我們用set< int >s來存每個團隊有什么成員，v表示當前團隊的分數，ans為每個成員的分數，具體實現為：當x加入團隊y時，s[y]存入x，并且ans[x]減去v[y]，因為v表示這個團隊的信號數量，x剛加進去，之前的信號數量和他沒有關系，所以要減去v[y]，x推出團隊時，ans[x]+=v[y],就是將團隊的信號量加到個人上，x在團隊y發信號，就直接v[y]加1，ans[x]減1（因為x不能接收自己的信號），相當于團隊先幫大家存信號，然后再依次返還
所有操作結束后，對于每個團隊，將該團隊的信號量加到每個學生上，等下！！你可能會想，如果數據極端情況，每個學生都加入到了所有團隊，這樣的復雜度不就是O(n * m)，鐵超時，但其實并不是，因為操作熟練是由上線的，s<=1000000,如果所有操作都執行全部同學加入y團隊，那么在一個團隊內最多也就是1e6個人，其他團隊都為空，也就是復雜度的上線其實是O(s),所以不會超時
簽到題，想這么復雜干什么

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+9; unordered_set<int>vec[maxn]; int ans[maxn]; int v[maxn];//每組的分數 int main() {int n,m,s;cin>>n>>m>>s;for(int i=1;i<=s;i++){int t,x,y;scanf("%d%d%d",&t,&x,&y);if(t==1){vec[y].insert(x);ans[x]-=v[y];}else if(t==2){vec[y].erase(x);ans[x]+=v[y];}else if(t==3){ans[x]--;v[y]++;}}for(int i=1;i<=n;i++){if(vec[i].size()==0)continue;for(auto j:vec[i]){ans[j]+=v[i];}}for(int i=1;i<=m;i++){printf("%d\n",ans[i]);} }

總結

以上是生活随笔為你收集整理的H - Message Bomb Gym - 102798H的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。