Problem - E - Codeforces

题意：

给定两个整数N和K，是否存在一个排列使得，对于这个排列，每个长度为K的区间内奇数个数奇偶性是一样的

思路：

构造题，先从最特殊的情况开始考虑

当K=1时，显然不可能满足

当K=2时一定满足，显然奇偶交替摆放即可

推广得，K是偶数时，都是合法的

然后，我们猜一个结论，去猜该怎么特殊化

根据之前的特殊情况猜：区间内奇数和偶数的个数相同

然后就可能猜对了，确实是这样子构造的

Code：

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=3e3+10;
const int mxe=5e5+10;int N,K;void solve(){cin>>N>>K;int tot_odd=(N+1)/2;int tot_even=N/2;int b=N/K;int c=N%K;int k_odd=(K+1)/2;int k_even=K/2;int r_odd=tot_odd-b*k_odd;int r_even=tot_even-b*k_even;if(r_even>=0&&r_odd>=0&&r_even+r_odd==c){if(r_even<=k_even&&r_odd<=k_odd) cout<<"Yes"<<'\n';else cout<<"No"<<'\n';return;}cout<<"No"<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}