题解：P11277 世界沉睡童话

· · 题解

人类智慧，一堆地方不会证，欢迎证明或 hack。

首先注意到：n 至 2n-1 中没有任何两个有倍数关系。

考虑这么一种构造：若干个 1，其它数全部为 n 至 2n-1。设 1 的个数为 x_0，n,n+1,\cdots,2n-1 的个数分别是 x_1,x_2,\cdots,x_n。

则有：

\begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle \frac{x_0(x_0-1)}{2}+\sum_{i=1}^n(x_0x_i+\frac{x_i(x_i-1)}{2})=k \end{cases}

一通整理： :::info[过程]{open}

\begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle x_0(x_0-1)+\sum_{i=1}^n(2x_0x_i+x_i(x_i-1))=2k \end{cases} \begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle x_0(x_0-1)+\sum_{i=1}^n(2x_0x_i+x_i^2-x_i)=2k \end{cases} \begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle x_0(x_0-1)+(2x_0-1)\sum_{i=1}^nx_i+\sum_{i=1}^nx_i^2=2k \end{cases} \begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle x_0(x_0-1)+(2x_0-1)(n-x_0)+\sum_{i=1}^nx_i^2=2k \end{cases} \begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle x_0^2-x_0+2nx_0-2x_0^2-n+x_0+\sum_{i=1}^nx_i^2=2k \end{cases} \begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle \sum_{i=1}^nx_i^2=2k+n-2nx_0+x_0^2 \end{cases}

::: 得出这么个结论：

\begin{cases} \displaystyle x_0+\sum_{i=1}^nx_i=n \\ \displaystyle \sum_{i=1}^nx_i^2=2k+n-2nx_0+x_0^2 \end{cases}

考虑枚举 x_0，一个个判断方程是否有解即可。

这里我用的是贪心解法。考虑先放 n-x_0 个 1，那么第二个方程左边一定是少了的。

接下来把后面的 1 合并到第一个数上去，容易发现第一次合并会加 2，第二次会加 4，以此类推。重复直到继续合并的话第二个方程左边就会超过右边。

接下来，忽略第一个数，从第二个数开始合并即可。

合并到最后，如果第二个方程左右相等则已经找到解了，否则无解。

正确性似乎不会严谨证明，但是好像比较显然？

先不管了。最人类智慧的还在后面呢。

这样直接做是过不了的，会 TLE 9 个点。考虑优化。

我们会发现，似乎 x_0 越大，求解越快，因为 n-x_0 和第二个方程的右边都会变小。所以充分发扬人类智慧：倒序枚举 x_0。

竟然过了！时间竟然还和正解不相上下！

做完了。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define vct basic_string
#define ms(x,v) memset(x,v,sizeof(x))
const int N=5e5+10,mod=998244353;
int c,x[N];
bool find(int n,int s)
{
    c=0;
    if(s<n) return 0;
    int t=n,us=0;
    while(us!=n)
    {
        x[++c]=1;
        us++;
        int sp=2;
        while(t+sp<=s&&us!=n) t+=sp,sp+=2,x[c]++,us++;
    }
    return t==s;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    int s=2*k+n;
    for(x[0]=n;x[0]>=0;x[0]--) if(find(n-x[0],s-x[0]*(2*n-x[0])))
    {
        for(int i=1;i<=x[0];i++) cout<<1<<' ';
        for(int i=1;i<=c;i++) for(int j=1;j<=x[i];j++) cout<<n+i-1<<' ';
        return 0;
    }
    return 0;
}

:::