日常训练2025-1-14

C. MEX Cycle

rating：1500

https://codeforces.com/contest/2049/problem/C

思路

注意这是一道构造题。

用xy将环分成两段，为保证xy符合条件，要先给xy的权值设置成01，然后根据两段链的长度的奇偶有两种填数方案。偶数直接01填，奇数要先填一个2然后再随机填。

评述

代码写到红温

代码

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n, x, y;
	std::cin >> n >> x >> y;

	std::vector<int> v(n+1, -1);

	v[x%n] = 1, v[y%n] = 0;
	if ((y - x - 1) % 2 == 1){
		v[x+1] = 2;
		for (int i = y - 1; i > x + 1; i--){
			v[i] = v[(i+1)%n] ^ 1;
		}
	}else{
		for (int i = y - 1; i > x; i--){
			v[i] = v[(i+1)%n] ^ 1;
		}
	}

	if ((n - (y - x + 1)) % 2 == 0){
		for (int i = (y + 1) % n, j = 0; j < (n - (y-x+1)); j++, i++, i %= n){
			v[i] = v[(i+n-1)%n] ^ 1;
		}
	}else{
		v[(x+n-1)%n] = 2;
		for (int i = (y + 1) % n, j = 0; j < (n-(y-x+1))-1; j++, i++, i %= n){
			v[i] = v[(i+n-1)%n] ^ 1;
		}
	}

	for (int i = 1; i < n; i++){
		std::cout << v[i] << ' ';
	}
	std::cout << v[0] << ' ';
	std::cout << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	std::cin >> t;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}