codeforces竞赛1169题解
【摘要】
A. Circle Metro
题目大意:
两个人乘坐不同方向的环形地铁,求两人是否会在某一站点相遇。
解题思路:
模拟即可
AC代码:
版本一(下标模拟)
#include<bits...
A. Circle Metro
题目大意:
两个人乘坐不同方向的环形地铁,求两人是否会在某一站点相遇。
解题思路:
模拟即可
AC代码:
- 版本一(下标模拟)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
int a, x, b, y;
cin >> a >> x >> b >> y;
int i = a, j = b;
bool flag = false;
while(true){
if(i == j){
flag = true;
break;
}
if(i == x)break;
if(j == y)break;
i++;
if(i > n)i = 1;
j--;
if(j < 1)j = n;
}
if(flag){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
return 0;
}
- 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
- 版本二(队列模拟)
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
template<typename T>
inline void oo(string str, T val) { cerr << str << val << endl; }
template<typename T>
inline T read() {
T x;
cin >> x;
return x;
}
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
int main() {
int n(read<int>());
int a(read<int>()), x(read<int>()), b(read<int>()), y(read<int>());
queue<int> P, Q;
for (int i = 1; i <= n * n; i++)Q.push(i % n + 1);
for (int i = n * n; i >= 1; i--)P.push(i % n + 1);
while (Q.front() != a)Q.pop();
while (P.front() != b)P.pop();
bool flag = false;
while (Q.front() != x and P.front() != y) {
Q.pop();
P.pop();
if (Q.front() == P.front()) {
flag = true;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
return 0;
}
- 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
B. Pairs
题目大意:
给出n个点,m条边,每条边有两个定点。是否可以找出两个点x,y,使得所有的边要么与x相连,要么与y相连。
解题思路:
将点边集合看成图,找出图中两个度数最大的点,删掉这两个点及其相关的边后,检测图中是否就没有边了。操作步骤如下:
- 将所有的边以pair点对的形式放到set集合里面去(可以去重).
- 然后统计每个点的度数,用map存放每个点和它的度数值。
- 然后找出最大的度数的点,将这个点的所有连边从set中移除,并且与这个点相邻的点的度数减一。
- 重新找度数最大的点,重复步骤2,3
- 判断存放边的集合set是否为空,如果为空,则输出YES,否则输出NO。
备注:
set的迭代器删除的时候,要写成 S.erase(edge++)
,而不能写成 S.erase(edge);edge++;
因为执行完删除操作后,迭代器已失效,此处是个坑,得留心
AC代码:
#include<bits/stdc++.h>
using namespace std;
int main() {
// ifstream cin("input.txt");
int n, m;
cin >> n >> m;
set<pair<int, int> >S;
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
S.insert({a, b});
}
map<int, int>M;
for(auto i : S) {
M[i.first]++;
M[i.second]++;
}
for(int i = 0; i < 2; i++) {
if(S.size() == 0)break;
int u = 1, MAX = 0;
for(auto i : M){
if(i.second > MAX){
u = i.first;
MAX = i.second;
}
}
for(auto edge = S.begin(); edge != S.end();) {
if(edge->first == u || edge->second == u) {
M[edge->first]--;
M[edge->second]--;
S.erase(edge++);
}else{
edge++;
}
}
}
if(S.size() == 0) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
- 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
- 42
- 43
文章来源: blog.csdn.net,作者:爱玲姐姐,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/jal517486222/article/details/90646973
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)