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

Problem - E - Codeforces

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

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

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

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

$$（\lfloor \frac{n}{k}\rfloor +1）\ast x+（\lfloor \frac{n}{k}\rfloor ）\ast y=（\lfloor \frac{n}{2}\rfloor ）$$

带入扩欧得到通解：

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

$$y=y_0\ast \frac{c}{gcd(a,b)}-\frac{k\ast a}{gcd(a,b)}$$

根据已有的 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(){IOScin >> 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((double)(cnta - x * c) / (double) b);int k1_min = ceil((double)(0 - x * c) / (double) b);int k2_max = floor((double)(y * c) / (double) a);int k2_min = ceil((double)(y * c - cntb) / (double) 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);