CF899C Dividing the numbers 题解
yzy041616
·
·
题解
题目传送门
Part.1 题目
将 {1,2, \dots n} 的集合任意划分为两个子集，每个子集都有一个和，使这两个和之差的绝对值最小。第一行输出这个最小的差，第二行先输出其中任意一个子集的元素个数，然后再输出这个子集里的所有元素，可以不考虑顺序。
例：若 n=7 则可以分成 \{3,4,7\} 和 \{1,2,5,6\}，\{3,4,7\} 的和是 14，\{1,2,5,6\} 的和也是 14。这两个和之差的绝对值为 0，是最小了。所以第一行输出这个差，0，第二行选一个子集，假设选到了 \{3,4,7\}，就要先输出它的元素个数，3，然后再输出 3 4 7。可以不考虑顺序，所以 3 7 4，4 3 7，4 7 3，7 3 4，7 4 3 都会算你对的。
Part.2 思路
这是一道数学题。如果 n 比较大的话，就先拿最大的四个数，这四个数是 n,n-1,n-2,n-3，因为 n+(n-3)=(n-1)+(n-2)，所以这四个数可以当作没有，两个子集元素个数也一样，n 个数的状态转化成 n-4 个数。
到最后，n 变成 n\%4，只剩下 4 种状态：
$2.$ $n=1$，有一个数是 $1$，只能分在一组里，所以差为 $1$。
$3.$ $n=2$，两个数分别是 $1,2$，可以分在两组里，但是差最小还是 $1$。
$4.$ $n=3$，三个数， $1,2,3$，第一组分 $3$，第二组分 $1,2$，差为 $0$。
第一行的输出搞定了。
对于第二行的子集元素个数，在一开始把 $n$ 变成 $n\%4$ 的时候，两个子集元素个数一直是相等的，到最后分类讨论的时候，元素个数相差也不超过 $1$，所以总是有一个子集元素个数为 $n/2$，最后输出元素的时候也要输出那个个数少的。
对于构造子集，因为一开始删数的时候总是 $n$ 和 $n-3$ 分在一组，所以每次都要输出 $n$ 和 $n-3$。
到了最后分类讨论，要记住输出元素少的那一组。$n=0$ 时没有元素。$n=1$ 时也没有元素。$n=2$ 时有一个元素是 $1$。$n=3$ 时有一个元素是 $3$。
## Part.3 代码
```cpp
#include<iostream>
using namespace std;
int diff[4]={0,1,1,0};
string start[4]={" "," "," 1 "," 3 "};
int main(){
int n;cin>>n;
cout<<diff[n%4]<<endl;
cout<<n/2<<start[n%4];
for(;n>3;n-=4)cout<<n<<" "<<n-3<<" ";//改成n-1和n-2也行
}
```