【构造】CF851div2 C. Matching Numbers

àì夳堔傛蜴生んèń 2024-03-22 11:02 82阅读 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 条评论，82人围观）

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

相关阅读

相关 CF723div2 vp

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

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

相关【构造】CF1758 C

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

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

相关【差分】CF862div2 C

[Problem - C - Codeforces][] 题意： ![0f5f6ec576ec4ff191478dc5d04be692.png][] ![c8f8ba05

川长思鸟来/ 2024年03月22日 17:26/ 0 赞/ 56 阅读

相关【数论+构造】CF752div1 B

[Problem - 1603B - Codeforces][] 题意：给定两个数x,y，让你构造一个n使得n%x=y%n 其中1<=n<=2e18 思路：因为是

向右看齐/ 2024年03月22日 13:57/ 0 赞/ 93 阅读

相关【构造排列】CF869div2 B

[Problem - 1818B - Codeforces][] 题意： ![db00d9d113894bbc8977f4c8a2ddbe63.png][] 思路：对

谁借莪１个温暖的怀抱￠/ 2024年03月22日 11:52/ 0 赞/ 73 阅读

相关 CF869div2 C. Almost Increasing Subsequence

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

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

相关【构造】CF851div2 C. Matching Numbers

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

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

相关 C. Standard Free2play——cf1238c（div2）（贪心）

题目链接：https://codeforces.com/problemset/problem/1238/C 思路：每一个凸出层有两个状态，一个状态是经过该层，一个

阳光穿透心脏的1/2处/ 2023年06月06日 03:54/ 0 赞/ 10 阅读

相关 CF#692 div2

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

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

相关 CF572_Div2_F

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

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