CF-1169B Pairs 题解

题目大意

给定你m对整数对(x[i],y[i]),请问是否存在x和y,使得n对中每一对中至少有一个数是x和y之中的一个。

解题思路

(我是真的蠢啊。。。

每一对都要是x,y中的一个,那么x就只有两种情况,第一对其中的任意一个。

这个需要只需要枚举y两次即可。

(就是这个卡了我好久。。

只要x加上y减去y和x一起出现的次数加起来等于m即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <map>
#include <functional>
using namespace std;

const int N = 3e5 + 5;
int cnt[N];
map<pair<int,int>, int> M;

int main() {
int n, m;
cin >> n >> m;
int a, b;
cin >> a >> b;
cnt[a]++;
cnt[b]++;
M[make_pair(a, b)]++;
M[make_pair(b, a)]++;
for (int i = 1; i < m; i++) {
int x, y;
cin >> x >> y;
cnt[x]++;
cnt[y]++;
M[make_pair(x,y)]++;
M[make_pair(y,x)]++;
}
for (int i = 1; i <= n; i++) {
if (i != a&& cnt[i] + cnt[a] - M[make_pair(i, a)] == m) {
cout << "YES" << endl;
return 0;
}
}
for (int i = 1; i <= n; i++) {
if (i!=b&&cnt[i] + cnt[b] - M[make_pair(i, b)] == m) {
cout << "YES" << endl;
return 0;
}
}
cout << "NO"<< endl;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信