CF1594F-Ideal Farm【構造】

正題

題目連結:https://www.luogu.com.cn/problem/CF1594F

題目大意

給出\(n,s,k\)，求是否所有的長度為\(n\)且和為\(s\)的正整數序列都有一段和為\(k\)的區間。

\(1\leq T\leq 10^5,1\leq n,s,k\leq 10^{18}\)

解題思路

可以考慮構造一個序列使得沒有和為\(k\)的區間。

要求使得沒有兩個字首和內插補點為\(k\)，構造時顯然前面的越小越好，因為如果前面的增大給後面的減小那麼還不如直接讓前面的減小，當我們在字首和中填入\(1\sim k-1\)之後我們下一個由于\((0\sim k-1)+k\)都給封鎖住了是以我們隻能填\(2k\)，然後可以繼續往後填\(2k\sim 3k-1\)，發現每隔\(k\)個就要加\(k+1\)。

也就是我們構造的序列是形如：\(1,1,1,1,...k+1,1,1,1,...k+1,1,1,1\)形式的，計算出前\(n\)個的最小和就好了。

然後交上去發現WA了，後來想了想當\(n<k\)時由于沒有填上關鍵格是以需要特殊考慮，如果\(s=k\)時顯然是無解的，否則\(n<k\)時填\(n-1\)個\(1\)然後填\(s-n+1\)即可。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll T,s,n,k;
signed main()
{
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&s,&n,&k);
		if(n<k){
			if(s==k)puts("YES");
			else puts("NO");
			continue;
		}
		ll w=n/k*2ll*k+n%k;
		if(s<w)puts("YES");
		else puts("NO");
	}
	return 0;
}