【构造】CF851div2 C. Matching Numbers

àì夳堔傛蜴生んèń 2024-03-22 11:02 71阅读 0赞

[Problem - C - Codeforces][]

题意：

有1~2\*n的一个排列，进行数与数之间两两匹配，问如何组合可以使n个 数对 ai+bi排列起来是一个连续序列，如果无解输出No

![5315f5b71551480e9e7c275ee2f1564f.png][]

思路：

构造题，考虑将构造的条件特殊化

手推样例可知，它大概是1和2\*n匹配，然后3和2\*n-1匹配，....，这样的和就是+2-1，直到n和....匹配，然后考虑从2,4,6开始匹配，本质上就是找规律

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    int N;
    int vis[mxn];
    
    void solve(){
    	cin>>N;
    	if(N%2==0){
    		cout<<"NO"<<'\n';
    		return;
    	}
    	cout<<"YES"<<'\n';
    	for(int i=1;i<=N*2;i++) vis[i]=0;
    	int l=1,r=N*2;
    	while(l<=r&&l<=N){
    		cout<<l<<" "<<r<<'\n';
    		vis[l]=vis[r]=1;
    		l+=2,r--;
    	}
    	l=1;r=N*2;
    	while(l<=r&&l<=N*2&&r>=1){
    		while(vis[l]) l++;
    		while(vis[r]) r--;
    		if(l<=N*2&&r>=1){
    			cout<<l<<" "<<r<<'\n';
    			vis[l]=vis[r]=1; 
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }
    
    /*YES
    1 18
    3 17
    5 16
    7 15
    9 14
    11 13
    2 12
    4 10
    6 8*/

[Problem - C - Codeforces]: https://codeforces.com/contest/1788/problem/C
[5315f5b71551480e9e7c275ee2f1564f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/da63554d129742e9a043e51c4de6653c.png

发表评论取消回复

表情：

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

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

相关阅读

相关 CF723div2 vp

哈哈，我是弱智哈哈，我是弱智哈哈，我是弱智谢谢你xcpc，让我认识到我就是个什么都不会的dinner ![cafe464664a699c7748235ab1488

小鱼儿/ 2024年03月26日 15:51/ 0 赞/ 77 阅读

相关【单调栈】CF771div2 C-Inversion Graph

[Problem - C - Codeforces][] 题意： ![aa325c0ceb554a5fbaa6e1d1a8eb7d7e.png][] ![df307d82

痛定思痛。/ 2024年03月23日 13:56/ 0 赞/ 59 阅读

相关【构造】CF1758 C

[Problem - 1758C - Codeforces][] 题意： ![ca2189d9b46747f4bd23ecfa1ef0db02.png][] 思路： !

古城微笑少年丶/ 2024年03月22日 23:17/ 0 赞/ 69 阅读

相关【gcd】CF826div2 B

有人不会div2 B 没关系，精神稳定一分钟也很厉害了嘻嘻，嘻嘻.... [Problem - B - Codeforces][] ![2ad3819b26264c2

不念不忘少年蓝@/ 2024年03月22日 17:20/ 0 赞/ 50 阅读

相关【构造】CF634div3 D. Anti-Sudoku

[Problem - D - Codeforces][] 题意：给定一个数独，让你更改最多9格，使其变成anti-数独，即每一行，每一列，每一个3\3大格都存在一个数的出

待我称王封你为后i/ 2024年03月22日 14:20/ 0 赞/ 51 阅读

相关 CF869div2 C. Almost Increasing Subsequence

[Problem - C - Codeforces][] 题意： ![967e89b3f5584dafb5a3e8b721e277fc.png][] 思路：关注特殊点

落日映苍穹つ/ 2024年03月22日 11:33/ 0 赞/ 31 阅读

相关【构造】CF851div2 C. Matching Numbers

[Problem - C - Codeforces][] 题意：有1~2\n的一个排列，进行数与数之间两两匹配，问如何组合可以使n个数对 ai+bi排列起来是一个连续序

àì夳堔傛蜴生んèń/ 2024年03月22日 11:02/ 0 赞/ 72 阅读

相关【CF#581(Div.2)】A&B

date：2019.8.20 我第一次打CF的比赛，感觉题目非常新颖并且非常棒，但是由于翻译软件不太给力所以我对题意的理解也不是很透彻，最后我做出了前两道题，感觉还可以吧

骑猪看日落/ 2023年06月05日 08:54/ 0 赞/ 4 阅读

相关 CF#692 div2

A 从后往前找连续)最长长度判断是否大于n/2即可 B 一个数字只会出现1-9，而1-9的最小公倍数为7560 所以你最多自增7560个数后必能找到符合条件的数，所以暴力模拟

缺乏、安全感/ 2022年12月29日 06:47/ 0 赞/ 177 阅读

相关 CF572_Div2_F

题意 [http://codeforces.com/contest/1189/problem/F][http_codeforces.com_contest_1189_pr

╰半夏微凉°/ 2021年10月29日 13:32/ 0 赞/ 295 阅读