CodeForces 1475C - 做题记录

原题链接

  • CodeForces
  • 洛谷

题意理解

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

思路

存储数据

1
vector<pair<int, int>> dancePair;

计算答案

方法一

期望得分:20

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

1
2
3
4
5
6
7
8
9
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) \newline = k - aryBoy[boy_{choose}] - aryGirl[girl_{choose}] + 1

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
bmyjacks 爱发电 爱发电
bmyjacks Patreon Patreon