P6608 题解

听取MLE声一片 · 2023-09-08 14:04:39 · 题解

神秘做法。

令 m=n+k，考虑给定 m 的值来判断是否合法并构造。

考虑处理每个位置操作了多少次。对于第一个位置，为了最后能清零，操作后面的一次后必然操作第一个位置，也就是操作 a_1=\lceil \frac{m}{2}\rceil 次。

对于第二个位置，第一个位置是没有影响的，所以只剩下 m-a_1 次操作。同样为了清零，后面操作两次后必然要操作第二个位置，次数也就是 a_2=\lceil \frac{m-a_1}{3}\rceil。

以此类推，第 i 个位置的操作次数就是 a_i=\lceil \frac{m-sum_i}{i+1}\rceil，其中 sum_i 表示前 i 项的前缀和。

注意如果到最后 m 次操作次数还没有给完，那先分配给最后一个位置。

然后就是如何通过操作次数来反推原序列 b_i。

考虑从后往前扫，设第 i 个位置的后面操作了 x 次，那么原序列 b_i=i\times a_i-x，如果每个 b_i 都符合限制，那么这个方案合法。

最后就是如何确定出 m 的值。

打表发现，合法的 \frac{\sqrt k}{n} 的值随着 k 增加逐渐趋近一个常数。取 1.7724566，则有近似值 n=1.7724566\sqrt k，上下取一个小的偏移量暴力跑一下就行了。

#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<ctime>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=2e6+10;
int n,m,k,a[N],b[N];
int check(){
    m=n+k;
    for(int i=1;i<=n;i++){
        int x=(m+i)/(i+1);
        a[i]=x;
        m-=x;
    }
    a[n]+=m;
    int sum=0;
    for(int i=n;i>=1;i--){
        b[i]=i*a[i]-sum;
        sum+=a[i];
        if(b[i]>i||b[i]<0)
            return 0;
    }
    //while(n>1&&b[n]==0)n--;
    cout<<n<<'\n';
    for(int i=1;i<=n;i++)
        cout<<b[i]<<' ';
    return 1;
}
signed main()
{
//  freopen("seq.in","r",stdin);
//  freopen("seq.out","w",stdout);
    k=read();
    int x=sqrt(k)*1.7724566;
    for(int i=max(x-10,3ll);i<=x+100;i++){
        n=i;
        if(check())
            return 0;
    }
    puts("Daydream!");
    return 0;
}