CF1475C - 题解

原题链接

  • CodeForces
  • 洛谷

题意理解

  • 数据组数 TT
  • 男孩 aa 个,女孩 bb 个,舞伴 kk

思路

存储数据

vector<pair<int, int>> dancePair;

计算答案

方法一

期望得分:20

暴力枚举每一对舞伴 (boyigirli)(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(n2)O(n^{2}),难道 n2n^{2} 过百万已经不灵验了?(好吧题目中的是两百万)

方法二

期望得分:100

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

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

(k1)(aryBoy[boychoose]1)(aryGirl[girlchoose]1)=karyBoy[boychoose]aryGirl[girlchoose]+1(k - 1) - (aryBoy[boy_{choose}] - 1) - (aryGirl[girl_{choose}] - 1) \\ = k - aryBoy[boy_{choose}] - aryGirl[girl_{choose}] + 1

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

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;