题解 CF1493A Anti-knapsack

qwq

珂能更好的阅读体验（？

Description

• 给定正整数 $n$ 和 $k$ ，满足 $n\ge k$。
• 要求在 $[1,n]$ 中选出最多的不同整数，使得从这些整数中随便取一些数加起来，所得到的和都不是 $k$。
• $T$ 组数据，$1\le T\le 100,1\le n,k\le 10^4$。

Solution

首先 $(k,n]$ 里面的数肯定可以选，毕竟这里面随便取一个数都已经超过 $k$ 了qwq。

然后 $k$ 自己肯定不能选，一元子集也是子集qwq

对于 $[1,k)$ 中的数：

一方面：

• 考虑把集合 $\{1,2,3,\cdots,k-1\}$ 划分成 $\{1,k-1\},\{2,k-2\},\{3,k-3\},\cdots,\{t,k-t\},\cdots$。
• 如果 $k$ 是偶数，那么会多出来一个单独的 $\dfrac{k-1}{2}$；
• 如果 $k$ 是奇数，那么刚好分完。
• 那么显而易见的一点是：对于划分出来的每一个二元子集，我们至多只能从这两个数中选一个。
• 否则，这个二元子集的和就是 $k$，与题意不符。
• 这表明我们取的数的个数至多就是这些二元子集的个数，也就是 $\left\lfloor\frac{k}{2}\right\rfloor$。

而另一方面：

• 考虑选取 $\left\lceil\frac{k}{2}\right\rceil$ 到 $k-1$ 中的所有整数。
• 此时，对于每一个一元子集，它的和都小于 $k$；
• 而每一个多元子集的和必定大于这些数中最小的两个数之和，即 $\left\lceil\frac{k}{2}\right\rceil+\left(\left\lceil\frac{k}{2}\right\rceil+1\right)$。
• 但是这个和已经严格 $>k$ 了，所以每一个多元子集的和也不可能是 $k$。
• 所以这个构造符合题意。

而这个构造一共选取了 $(k-1)-\left\lceil\frac{k}{2}\right\rceil+1=\left\lfloor\frac{k}{2}\right\rfloor$ 个数，上面已经证过至多选取 $\left\lfloor\frac{k}{2}\right\rfloor$ 个数，故这就是最优构造。

于是最多选取的数的个数就是：$n-k+\left\lfloor\frac{k}{2}\right\rfloor$。

Code：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>

#define int long long

using namespace std;

int t,n,k;

signed main(void){

    cin>>t;
    while(t--){
        
        cin>>n>>k;
        cout<<(n-k)+(int)k/2<<"\n";
        
        for(int i=k+1;i<=n;i++)cout<<i<<' ';
        for(int i=k-1;i*2>=k;i--)cout<<i<<' ';
        cout<<'\n';
    }

    return 0;
}