题解 CF1594F Ideal Farm

· · 题解

或许更好的阅读体验（？

很神奇的贪心。我们要做的其实是尽量构造一个序列，使得其不存在一个和为 k 的连续子段。考虑插板法的思路，现在有 s 个球 s+1 个空隙，其中第 0,s 个空隙必须选，我们需要从 1\sim s-1 这些空隙里选出 n-1 个空隙，使得它们两两间的距离不为 k。

先转为最多能选多少个空隙，显然位置膜 k 不同余的空隙是相互独立的，把膜 k 同余的空隙抽出来组成 k 条数轴，我们要做的就是对每条数轴上的点赋值 0/1，要求 1 与 1 不能相邻，问最多有多少个 1。贪心，每条数轴肯定是 1010101 这样交替选，但由于第 0 个空隙和第 s 个空隙已经被钦定了，所以它们所在的数轴要进行一些调整，不过这些调整对于数量是不会有影响的：首先如果它们所在数轴的长度为奇数那么无影响；否则，如果 0 和 s 不在同一条数轴上（即 k\nmid s），那么只需要把 01 取反，在同一条数轴上（即 k\mid s ）只需要把最后的 10 改成 01，比如 1010 改成 1001 就没事了。只有一种情况是例外的：0,s 在同一条数轴上且这条数轴上只有 0,s 这两个点，这对应 k=s ，先判掉就行。

综上，我们把原问题等价转化为了若干条独立的数轴上选最多的不相邻的点（实际上就是链最大独立集），给出了最优决策并证明了其正确性。现在来计算答案：如果第 i 条数轴的长度 len_i 为偶数，那么贡献为 \lfloor\frac{len_i}{2}\rfloor，否则贡献为 \lfloor\frac{len_i}{2}\rfloor+1。有 s\%k+1 条数轴长度为 \lfloor\frac{s}{k}\rfloor+1，其余数轴长度为 \lfloor\frac{s}{k}\rfloor，对于 \lfloor\frac{s}{k}\rfloor 的奇偶性分类讨论一下就好了。

题外话：很多人的构造策略可能是先放 k-1 个 1 再放 1 个 k+1 交替进行。注意到最开始 1010101 交替选是等价于这个决策的，尽管有些情况下并不一定正确，但它所选出的 1 的数量一定是正确的（换句话说，一定有其他的决策与其答案相同且没有决策更优），所以根据这个判一下够不够放也是对的。

代码如下（码字不易，点个赞再走好不好QAQ）：

#include<bits/stdc++.h>
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
#define sml(x,y) x=min(x,y)
#define big(x,y) x=max(x,y)
#define mk make_pair
#define pb push_back
#define ll long long
#define db double
#define int ll
using namespace std;
inline void out(int *a,int l,int r){fo(i,l,r) printf("%d ",*(a+i));puts("");}
inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; }

signed main(){
    int T=read();
    while(T--){
        int s=read(),n=read(),k=read();//s/k:数轴长度 
        if(s==k) puts("Yes");
        else{ 
            int x;
            if(s/k&1) x=k*(s/k+1)/2; 
            else x=(s%k+1)*(s/k/2+1)+(k-s%k-1)*(s/k/2);
            puts(x>n?"No":"Yes");
        } 
        //else if(n/k*k*2+n%k<=s) puts("No");
        //else puts("Yes");
    } 
    return 0;
}
/*
5
1 1 1
1 1 2
100 50 200
56220 47258 14497
87077 86130 86130
-------------------------
Y
N
N
Y
Y
*/