正題

題目鏈接:https://www.luogu.com.cn/problem/CF1594F

---

題目大意

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

$1\le T\le 10^5,1\le n,s,k\le 10^{18}$

---

解題思路

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

要求使得沒有兩個前綴和差值為$k$，構造時顯然前面的越小越好，因為如果前面的增大給后面的減小那么還不如直接讓前面的減小，當我們在前綴和中填入$1～k?1$之后我們下一個由于$(0～k?1)+k$都給封鎖住了所以我們只能填$2k$，然后可以繼續往后填$2k～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; }

總結

以上是生活随笔為你收集整理的CF1594F-Ideal Farm【构造】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。