[ABC068D] Decrease (Contestant ver.)

· · 题解

思路：

设答案的序列为 a，长度为 n。因为这个答案序列 a 不要求顺序，怎么排顺序都行；为方便讲解，设序列是一个从大到小的有序序列。

因为每次 a_1 是这个序列里最大的数，因此它要减去 n，然后为了维持 a 的有序性，因此它要在序列 a 里面插入，但是与其在里面无法预测地插入，不如插入到最后，因此，我们需要构造一个不断循环的序列。

为方便描述，举出几个例子：

当输入 0 时，输出为：

50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

可以看到，输出结果就是从 0 \sim 49，这里仅作铺垫。

当输入 2 时，输出仅需改成为：

50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 49 50

即“1 \sim 47\ 49\ 50”。下面是验证。

操作一次的结果为：

50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 50

操作两次的结果为：

50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

这个过程实际上是一个循环。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;

signed main(){
    cin>>n;
    cout<<50<<endl;
    for(int i=0;i<50;i++) cout<<i+(n+i)/50<<" ";
    cout<<endl;
    return 0;
}