2022 ICPC 济南 E Identical Parity (扩欧）-Toy模板网

这篇具有很好参考价值的文章主要介绍了2022 ICPC 济南 E Identical Parity (扩欧）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2022 ICPC 济南 E. Identical Parity (扩欧)

Problem - E - Codeforces

大意：给出一个 n 和一个 k ，问是否能构造一个长 n 的排列使得所有长 k 的连续子序列和的奇偶性相同。

思路：通过分析可知，任两个间隔 k - 1 的元素奇偶性必然相同，这样的话，问题就转化成了

$~\% ~k ~）个（\left \lfloor \frac{n}{k} \right \rfloor +1）和（k-n~\%~k）个（\left \lfloor \frac{n}{k} \right \rfloor）是否能组成（\left \lfloor \frac{n}{2} \right \rfloor）和（n - \left \lfloor \frac{n}{2} \right \rfloor）的问题$

很自然的就可以想到 01 背包去解决这个问题，但是显然 n 和 k 的范围太大了，无法使用 01 背包去解决这个问题。于是转化问题，考虑现有范围的 x 和 y 是否能满足以下式子。

$（\left \lfloor \frac{n}{k} \right \rfloor +1）*x~+~（\left \lfloor \frac{n}{k} \right \rfloor）*y = （\left \lfloor \frac{n}{2} \right \rfloor）$

带入扩欧得到通解：

$x=x_0*{c\over gcd(a,b)}+{k*b\over gcd(a,b)}$

$y=y_0*{c\over gcd(a,b)}-{k*a\over gcd(a,b)}$ 文章来源地址https://www.toymoban.com/news/detail-688807.html

根据已有的 x 的范围和 y 的范围分别求出两个 k 的范围，判断这两个区间是否相交即可。

易错点：是否可以通过 x 的范围求出对应 k 的范围然后带入求 y 的范围？显然是可以的，但是这样求出的 y 的范围区间是不连续的，也就不能判交。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int n , t , k;

int exgcd(int a , int b , int &x , int &y){
	
	if(b == 0){ x = 1; y = 0; return a;}
	int g = exgcd(b , a % b , y , x);
	y -= a / b * x;
	return g;
}



signed main(){

	IOS
	cin >> t;
	
	while(t --){
		cin >> n >> k;
		
		if(n % k == 0){
			int num = n / k , od , ev;
		    ev = n / 2;
		    od = n - ev;
			if(ev % num == 0 && od % num == 0){
				cout << "Yes" << "\n";
			}else{
				cout << "No" << "\n";
			}
		}else{
			int a = n / k , b = n / k + 1 , c = n / 2;
			int cntb = n % k , cnta = k - n % k;

			int x , y , gcds;
			gcds = exgcd(a , b , x , y);
			a /= gcds;b /= gcds;c /= gcds;
			
			int k1_max = floor(1.0L * (cnta - x * c) / (1.0L * b));
			int k1_min = ceil(1.0L * (0 - x * c) / (1.0L * b));
			int k2_max = floor(1.0L * (y * c) / (1.0L * a));
			int k2_min = ceil(1.0L * (y * c - cntb) / (1.0L * a));  
			
			if(k1_min > k1_max || k2_min > k2_max){
				cout << "No\n";
			}else{
				if(min(k2_max , k1_max) >= max(k1_min , k2_min)){
					cout << "Yes\n";
				}else{
					cout << "No\n";
				}
			}
		}
		
	}



	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);