這道題比賽的時(shí)候想到了正確解法，但是依然沒敢做，怕超時(shí)，其實(shí)就是道簡單并查集+組合計(jì)算。

?

題解：

　　1.首先要考慮的就是關(guān)系的傳遞，這就說明了我們可以把都不認(rèn)識(shí)的人，分成幾個(gè)集合。

　　2.剩下就是集合的合并，由于我們需要計(jì)算組合數(shù)，所以需要把集合人數(shù)也記錄一下。

　　3.需要解釋的估計(jì)就是這一條了?ans -= a * b * (pre - a * (n - a) - b * (n - b) + a * b); 建議先看代碼

　　　目前ans的值為a和b未合并的情況下的值，但是目前a和b已經(jīng)合并了，那么我們就需要減去a和b所貢獻(xiàn)的組合數(shù)

　　　那么a和b貢獻(xiàn)的組合數(shù)就是? ?： 從a中取1人，再從b中取1人，再從剩下的集合中挑取2人

　　　代碼就是? a*b*（剩下集合中挑取兩個(gè)的組合數(shù)）

　　　代碼中說過pre是? ?”取2個(gè)不同的人的取法”

　　　那么剩下集合中挑取兩個(gè)的組合數(shù)就是 ：pre - a * (n - a) - b * (n - b) + a * b?

　　　為什么要加上 a*b呢，因?yàn)?(n-a)中包括了b，(n-b)中包括了a，其實(shí)我們減去了兩次 a*b,所以需要加回來一次。

?

　　

#include <bits/stdc++.h>using namespace std; typedef double dou; typedef long long ll; typedef pair<int, int> pii; typedef map<int, int> mii;#define pai acos(-1.0) #define M 100005 #define inf 0x3f3f3f3f #define mod 1000000007 #define IN inline #define left k<<1 #define right k<<1|1 #define lson L, mid, left #define rson mid + 1, R, right #define W(a) while(a) #define lowbit(a) a&(-a) #define ms(a,b) memset(a,b,sizeof(a)) #define Abs(a) (a ^ (a >> 31)) - (a >> 31) #define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)ll n, m; ll ans, pre, a, b, fa, fb; ll boss[M], num[M];int find(int k) {if (boss[k] == k)return k;else {boss[k] = find(boss[k]);return boss[k];} }int main() {false_stdio;cin >> n >> m;pre = n * (n - 1) / 2;//這個(gè)是在n個(gè)人中取2個(gè)不同的人的取法ans = n / 2 * (n - 1) / 3 * (n - 2) / 4 * (n - 3);//初始的最大值為C(4)(n)for (int i = 1; i <= n; i++) {//一開始都不認(rèn)識(shí)，所以每個(gè)集合都是自己，人數(shù)也只有1num[i] = 1;boss[i] = i;}for (int i = 1; i <= m; i++) {cout << ans << endl;cin >> a >> b;fa = find(a), fb = find(b);//查找根節(jié)點(diǎn)if (fa == fb || ans == 0)continue;//如果根節(jié)點(diǎn)相同，也就是一個(gè)集合的，或者答案為0不能再減少了，那么就不用計(jì)算了 a = num[fa], b = num[fb];//a為fa所在集合的人數(shù)，b為fb所在集合的人數(shù)//看不懂下面這條的可以回去看解釋3了ans -= a * b * (pre - a * (n - a) - b * (n - b) + a * b);pre -= a * b;//減去a和b的組合數(shù) boss[fb] = fa;num[fa] += num[fb];}cout << ans << endl;return 0; }

?

　　　

　　

轉(zhuǎn)載于:https://www.cnblogs.com/caibingxu/p/11366348.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。