P1912 [NOI2009] 诗人小G

· · 题解

介绍一种简单无脑的做法。

摘自我的博客

首先你需要会李超线段树。

注意到李超线段树中有一个函数 Ans（看模板）是用来计算函数在一个点的取值。

我们如果将我们要求的函数（非直线）的解析式带入，就解决了问题。

把 |s_i-s_j-1-len|^p 看成函数，套李超线段树。

问题在这个函数的值会非常大，但我们又需要比大小，所以只能请出 long double 来解决。

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

typedef __int128 ll;
typedef long double ld;
typedef pair<ll,ll> pll;
#define fi first
#define se second 
const ll N=3e6+3,INF=(ll)1e18;
ll n,Len,P,rt,sum[N],sta[N];
pll f[N];
string str[N];
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
void write(ll X)
{
    if(X<0){putchar('-');X=~(X-1);}int s[20],o=0;
    while(X){s[++o]=X%10;X/=10;}
    if(!o)s[++o]=0;while(o)putchar(s[o--]+'0');
    putchar('\n');
}
struct LCT
{
    ll tot=0;
    struct Tree{ll lc,rc,id;}tr[N];
    ll Abs(ll x){return x>=0?x:-x;}
    ld Ksm(ld x,ll y){ld s=1;for(ll i=1;i<=y;i<<=1,x=x*x)if(y&i)s=s*x;return s;}
    ld Ans(ll id,ll x){return f[id].fi+Ksm(Abs(x-sum[id]-1-Len),P);}
    ll Res(ll id,ll x){return min((ld)INF+1,Ans(id,x));}
    #define ls (tr[p].lc)
    #define rs (tr[p].rc)
    #define mi ((l+r)>>1)
    void Upd(ll &p,ll l,ll r,ll u)
    {
        if(!p){p=++tot;tr[p].id=u;return;}
        ll &v=tr[p].id;
        if(Ans(u,mi)<Ans(v,mi))swap(u,v);
        if(Ans(u,l)<Ans(v,l))Upd(ls,l,mi,u);
        if(Ans(u,r)<Ans(v,r))Upd(rs,mi+1,r,u);
    }
    pll Ask(ll p,ll l,ll r,ll d)
    {
        if(!p)return {INF+1,0};
        pll ans={Res(tr[p].id,d),tr[p].id};
        if(l==r)return ans;
        return min(ans,d<=mi?Ask(ls,l,mi,d):Ask(rs,mi+1,r,d));
    }
    void Clear()
    {
        for(int i=1;i<=tot;i++)tr[i].lc=tr[i].rc=tr[i].id=0;
        tot=rt=0;
    }
}T;
void Solve()
{
    n=read();Len=read();P=read();T.Clear();
    for(int i=1;i<=n;i++)cin>>str[i],sum[i]=sum[i-1]+str[i].size();
    for(int i=1;i<=n;i++)sum[i]+=i;
    T.Upd(rt,0,sum[n],0);
    for(int i=1;i<=n;i++)f[i]=T.Ask(rt,0,sum[n],sum[i]),T.Upd(rt,0,sum[n],i);
    if(f[n].fi>INF)cout<<"Too hard to arrange"<<endl;
    else
    {
        write(f[n].fi);ll top=0,x=n;
        while(x)sta[++top]=x,x=f[x].se;
        sta[++top]=0;
        for(int i=top;i>1;i--)
        {
            for(int j=sta[i]+1;j<sta[i-1];j++)cout<<str[j]<<" ";
            cout<<str[sta[i-1]]<<endl;
        }
    }
    cout<<"--------------------"<<endl;
}
int main()
{
    ll T;T=read();
    while(T--)Solve();
}