CF1594F Ideal Farm (思維+數學)

連結

題意：

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

分析：

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

轉化一下就是字首和內插補點沒有等于k的

構造時，我們肯定想要字首和越小越好，那麼就可以使得前（k-1）個數都為1，那麼和為(k-1),在第k個數我們必須選一個大于k的一個數還要最小話，肯定就是k+1。然後後面照樣(k-1)個1+1個(k+1).

1 2 3 ... k-1 k k+1 k+2

1 1 1 ...1 k+1 1 1 1 ... k+1

然後我們考慮特殊情況，如果n的數量小于k的數量。就是說前面n個都放1可能還有數必須要放，因為總和為s，上面那種多出來的直接放進大于(k)的數中就好了。 那麼就要看看s是否等于k，如果等于，那麼肯定能構成，不等則不能。

///苟利國家生死以，豈因禍福避趨之。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX = 2e5 + 7;

ll n, s, k;
int main()
{

    ll t = 1;
    cin >> t;
    while(t--)
    {
        cin >> s >> n >> k;
        if(n < k)
        {
            if(s == k)
            {
                puts("YES");
            }
            else puts("NO");
        }
        else
        {
            ll m = n / k * k * 2 + n % k;
            if(m <= s) puts("NO");
            else puts("YES");
        }
    }
    return 0;
}