題目鏈接：https://ac.nowcoder.com/acm/contest/889/E

題意：n個人，m次操作，每次合并兩個人，求合并后找出4個人，且兩兩不在一個集合的方案數。

思路：最開始有C[n][4]種方案，每次合并我們計算出減少了多少方案數即可。減少的為本次合并的兩個集合的大小的乘積，再乘以從剩余集合中選出兩個不在一個集合的方案數，這可以通過算出任意兩個人的方案數，減去，在同一個集合的兩個人的方案數得到。集合的大小通過并查集操作維護，并用前綴和思想記錄此時選出在同一個集合的兩個人的方案數sum。預處理得到組合數，只用預處理到C(n,4)即可?？倧碗s度為O(mlogn)。

AC代碼：

#include<cstdio> #include<algorithm> #include<map> using namespace std;typedef long long LL; const int maxn=1e5+5; int n,m,root[maxn],siz[maxn]; LL ans,sum,C[maxn][5];void init(){C[1][0]=1,C[1][1]=1;C[2][0]=1,C[2][1]=2,C[2][2]=1;C[3][0]=1,C[3][1]=3,C[3][2]=3,C[3][3]=1;for(int i=4;i<maxn;++i){C[i][0]=1;for(int j=1;j<=4;++j)C[i][j]=C[i-1][j-1]+C[i-1][j];} }int getr(int k){if(root[k]==k) return k;else return root[k]=getr(root[k]); }int main(){init();scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)root[i]=i,siz[i]=1;ans=C[n][4];printf("%lld\n",ans);while(m--){int x,y;scanf("%d%d",&x,&y);int xr=getr(x),yr=getr(y);if(xr==yr){printf("%lld\n",ans);continue;}LL tx=0,ty=0;if(siz[xr]>=2) tx=C[siz[xr]][2];if(siz[yr]>=2) ty=C[siz[yr]][2];sum-=tx+ty;ans-=1LL*siz[xr]*siz[yr]*(C[n-siz[xr]-siz[yr]][2]-sum);printf("%lld\n",ans);root[yr]=xr;siz[xr]+=siz[yr];sum+=C[siz[xr]][2];}return 0; }

?

轉載于:https://www.cnblogs.com/FrankChen831X/p/11362450.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第九场）-E All men are brothers的全部內容，希望文章能夠幫你解決所遇到的問題。

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