CodeForcs 1169B Good Triple

￡神魔★判官ぃ 2022-01-09 15:13 180阅读 0赞

CodeForcs 1169B Good Triple

题目链接：[http://codeforces.com/problemset/problem/1169/B][http_codeforces.com_problemset_problem_1169_B]

题目描述：给你m对不超过n的数字，找出一对x，y，满足在这m对数中至少有一个数字等于x或者y。

思路：假设第一对为（a，b），若x，y存在，则其中之一一定是a，b中的一个数，那么如果存在（c，d），使得与a，b都不相同，那么x，y中的另一个数必在c，d中，所以x，y可能是（a，c），（a，d），（b，c），（b，d），如果不存在（c，d），则x，y就是（a，b），要对m对数进行扫描，则只要满足以下五中情况任意之一即可：（a，b），（a，c），（a，d），（b，c），（b，d）。时间复杂度O(5m)。

#include <iostream> #include <cstdio> using namespace std; const int maxn = 300005; pair<int, int> pa[maxn]; int n, m; bool check(int a, int b) { for (int i = 0; i < m; i++) { if (a != pa[i].first && a != pa[i].second && b != pa[i].first && b != pa[i].second) return false; } return true; } int main() { while (cin >> n >> m) { if (m == 1) { cin >> pa[0].first >> pa[0].second; cout << "YES" << endl; continue; } cin >> pa[0].first >> pa[0].second; int a = pa[0].first, b = pa[0].second, c, d; for (int i = 1; i < m; i++) { scanf("%d%d", &pa[i].first, &pa[i].second); if (a != pa[i].first && a != pa[i].second && b != pa[i].first && b != pa[i].second) { c = pa[i].first; d = pa[i].second; } } bool flag = check(a, b) || check(a, c) || check(a, d) || check(b, c) || check(b, d); if (flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }

转载于:https://www.cnblogs.com/youpeng/p/10954770.html

[http_codeforces.com_problemset_problem_1169_B]: http://codeforces.com/problemset/problem/1169/B

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #720 (Div. 2) B. Nastia and a Good Array

[Problem - B - Codeforces][] 题意：给定一个序列，一次操作可以选i,j,x,y使a\[i\]=x,a\[j\]=y，其中满足min(a\[i\

╰半橙微兮°/ 2024年03月29日 15:51/ 0 赞/ 79 阅读

相关 @codeforces - 1214G@ Feeling Good

目录 @description@ @solution@ @accepted code@ @details@ --------------------

绝地灬酷狼/ 2023年06月01日 14:56/ 0 赞/ 26 阅读

相关 Codeforces Good Bye 2013 ABCDE

继续总结做过的练习赛。链接：http://codeforces.com/contest/379 A New Year Candles 题意：初始有a根蜡烛,每根蜡烛照明

我会带着你远行/ 2022年08月24日 14:15/ 0 赞/ 80 阅读

相关 CodeForces 672B Different is Good

CodeForces 672B Different is Good time limit per test:2 seconds memory limit per te

你的名字/ 2022年08月22日 12:21/ 0 赞/ 32 阅读

相关 codeforce 246B——Good Sequences

第一次的尝试的思路是，用dp进行进行搜索，不过在第21组TLE，这也很正常。因为为复杂度是O(n^2),而n的最大值为为10^5. 第二次尝试把所给的数进行素性拆分、定

矫情吗；*/ 2022年08月11日 04:58/ 0 赞/ 194 阅读

相关 Codeforces Good Bye 2017 Div.2 908A,B

A. New Year and Counting Cards Problem Statement [http://codeforces.com/contest/90

我会带着你远行/ 2022年05月31日 10:09/ 0 赞/ 188 阅读

相关 Codeforces 115B

题目地址：[http://codeforces.com/problemset/problem/115/B][http_codeforces.com_problemset_pro

曾经终败给现在/ 2022年05月06日 10:54/ 0 赞/ 205 阅读

相关 CodeForces - 1101B

题目： B. Accordion time limit per test 3 seconds memory limit per test 256 megabytes

水深无声/ 2022年01月12日 10:59/ 0 赞/ 225 阅读

相关 CodeForcs 1169B Good Triple

CodeForcs 1169B Good Triple 题目链接：[http://codeforces.com/problemset/problem/1169/B][http

￡神魔★判官ぃ/ 2022年01月09日 15:13/ 0 赞/ 181 阅读

相关 CodeForcs 1169B Good Triple

CodeForcs 1169B Good Triple 题目链接：[http://codeforces.com/problemset/problem/1169/B][http

梦里梦外;/ 2022年01月08日 00:17/ 0 赞/ 165 阅读