Codeforces 1210 D Konrad and Company Evaluation —— 暴力

本文主要是介绍Codeforces 1210 D Konrad and Company Evaluation —— 暴力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有n个人，第i个人的工资一开始是i，现在有一些人相互讨厌，然后如果第x个人和第y个人相互讨厌，并且x的工资比y高，那么x就会向y炫耀。
x,y,z这三个人的组合是危险的，当x会向y炫耀，y会向z炫耀。
每次修改一个人的工资为大于所有人，并且询问你此时有多少种三人组合是危险的

题解：

那么这道题就有一个很暴力的做法，我们通过样例解释可以发现，其实就是一张有向图，然后答案是每个点的入度*出度。之后的话就是修改每个点的入边为出边。如果每次输入暴力修改每个点的入边为出边的话，乍一看是$O(n^2)$的，但是仔细思考可以发现，每一条边只连接了2个人，并且它会翻转当且仅当修改的是被指向的那个人。
也就是说，如果修改一个人的值会翻转n条边，那么只有在接下来修改n个人的值才能将所有边翻转回来。
所以我断定暴力修改的时间复杂度是O(n)的，然后用vector维护每条边的反边，在删除的时候是O(log)的，所以总的时间复杂度是$O(nlogn)$的。如果用map维护的话，时间复杂度是$O(n\ast q\ast logn)$

最终时间复杂度：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
vector<int>mp[N];
int in[N],out[N];
int main()
{int n,m,x,y;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);if(x>y)swap(x,y);mp[x].push_back(y),in[x]++,out[y]++;}ll ans=0;for(int i=1;i<=n;i++)ans+=1ll*in[i]*out[i];printf("%lld\n",ans);int q;scanf("%d",&q);while(q--){scanf("%d",&x);ans-=1ll*in[x]*out[x];for(auto i:mp[x]){mp[i].push_back(x);ans+=1ll*(in[i]+1)*(out[i]-1)-1ll*in[i]*out[i];in[x]--,out[x]++,in[i]++,out[i]--;}mp[x].clear();printf("%lld\n",ans);}return 0;
}

这篇关于Codeforces 1210 D Konrad and Company Evaluation —— 暴力的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---