CodeForces 1475C - 做题记录

原题链接

• CodeForces
• 洛谷

题意理解

• 数据组数 $T$
• 男孩 $a$ 个，女孩 $b$ 个，舞伴 $k$ 对

思路

存储数据

vector<pair<int, int>> dancePair;

计算答案

方法一

期望得分：20

暴力枚举每一对舞伴 $(boy_{i} - girl_{i})$

register unsigned long long ans = 0;
 for (register int i = 0; i < k - 1; ++i) {
   for (register int j = i + 1; j < k; ++j) {
     if ((dancePair[i].first != dancePair[j].first) and (dancePair[i].second != dancePair[j].second)) {
       ++ans;
     }
   }
 }
 cout << ans << endl;

结果第四个点 TLE 了，一看时间复杂度 $O(n^{2})$，难道 $n^{2}$ 过百万已经不灵验了？（好吧题目中的是两百万）

方法二

期望得分：100

仔细研究发现，我们可以枚举每一对舞伴，并将所有 $k$ 对舞伴中除了与他们有相同的组成以外的加入答案中即可。

详细版： 共 $k$ 对舞伴，除去本身后有 $k - 1$ 对舞伴，在剩下的 $k - 1$ 对舞伴中，与选择的舞伴中男生相同的有 $aryBoy[boy_{choose}] - 1$ 对，与女生相同的有 $aryGirl[girl_{choose}] - 1$ 对，则每次枚举需要增加的数量为

$$(k - 1) - (aryBoy[boy_{choose}] - 1) - (aryGirl[girl_{choose}] - 1) \newline = k - aryBoy[boy_{choose}] - aryGirl[girl_{choose}] + 1$$

此时我们对每一对男生女生都重复计算了两次，则最后答案需要除以 $2$。

int aryBoy[MAX_K], aryGirl[MAX_K];
for (register int i = 0, tmp; i < k; ++i) {
    cin >> tmp;
    ++aryBoy[tmp];
  }
  for (register int i = 0, tmp; i < k; ++i) {
    cin >> tmp;
    ++aryGirl[tmp];
  }

register unsigned long long ans = 0;
  for (register int i = 0; i < k; ++i) {
    ans += k - aryBoy[dancePair[i].first] - aryGirl[dancePair[i].second] + 1;
  }
  ans /= 2;
  cout << ans << endl;