CF1594F. Ideal Farm

​

題解

考慮到如果 $s<k$ ，說明可以，如果 $s=k$ ，說明不行，現在考慮 $s>k$ 。

假設第 $i$ 個分了 $a_i$ 個，我們不妨做個字首和為 $p_i$ ，那也就是說如果不是理想的，說明對于 $[0,n]$ 不存在兩個數 $i,j$ 滿足 $p_i-p_j=k$ 。于是我們設 $q_i=p_i+k$ 。

是以我們發現 $p_i$ 和 $q_i$ 兩個數列裡的數各不相同。

于是我們現在有 $1$ 到 $s+k$ 除去 $k$ 這些數，要選出 $2n$ 個數，滿足可以比對為 $n$ 組，每組兩個數相差為 $k$ 。

是以我們考慮對 $k$ 取模後餘數相同的數最多能夠分成幾組即可。

效率 $O(T)$ 。

代碼

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int T;LL n,k,s;
void work(){
    scanf("%lld%lld%lld",&s,&n,&k);
    if (s==k){puts("YES");return;}
    if (s<k){puts("NO");return;}
    LL v=s%k;
    LL w=s+k;
    LL u=(s-v)/k+1;
    if (u&1) w-=k-v-1;
    else w-=v+1;
    if (w>=n+n+1) puts("NO");
    else puts("YES");
}
int main(){
    for (scanf("%d",&T);T--;work());
    return 0;
}