博客类网站怎么做,wordpress怎么做链接,中国查公司的网站,软件开发公司的成本有哪些H - Message Bomb Gym - 102798H
题意#xff1a;
有n个团队#xff0c;m个人#xff0c;s个操作 操作1#xff1a;学生x加入y团队 操作2#xff1a;学生x推出y团队 操作3#xff1a;学生x在团队y发送一个信号#xff0c;在团队y内的所有成员#xff08;除了x#x…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]加1ans[x]减1因为x不能接收自己的信号相当于团队先帮大家存信号然后再依次返还 所有操作结束后对于每个团队将该团队的信号量加到每个学生上等下你可能会想如果数据极端情况每个学生都加入到了所有团队这样的复杂度不就是O(n * m)铁超时但其实并不是因为操作熟练是由上线的s1000000,如果所有操作都执行全部同学加入y团队那么在一个团队内最多也就是1e6个人其他团队都为空也就是复杂度的上线其实是O(s),所以不会超时 签到题想这么复杂干什么
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn1e69;
unordered_setintvec[maxn];
int ans[maxn];
int v[maxn];//每组的分数
int main()
{int n,m,s;cinnms;for(int i1;is;i){int t,x,y;scanf(%d%d%d,t,x,y);if(t1){vec[y].insert(x);ans[x]-v[y];}else if(t2){vec[y].erase(x);ans[x]v[y];}else if(t3){ans[x]--;v[y];}}for(int i1;in;i){if(vec[i].size()0)continue;for(auto j:vec[i]){ans[j]v[i];}}for(int i1;im;i){printf(%d\n,ans[i]);}
}
