神奇的题目 $QvQ$ ,卡了我好久。

哎,主要是细节要处理到位,否则就会 WA 声满片。

记录一下我壮观的提交记录:

太杯具了 $QvQ$

(扯谈扯不下去了…….)

进入正题吧。

路人甲:$bzoj$ 上居然没有这道题?
导演:赶紧走开,不管你的事

这题明显是 $DP$,我们可以很简单的得到 $DP$ 方程:

设 $f[i]$ 表示对前 $i$ 句诗排版后的最小不协调度,那么很显然,对于一个现在我们需要转移的 $i$,我们会找到一个最优的 $j$ ,使得第 $j+1$ 句到第 $i$ 句组成一个新的行。那么之前的行的总共的最小不协调度显然是 $f[j]$,现在我们就来计算一下 $f[i]$ 的最小不协调度。

显然,是下式 (其中 $sum$ 是句子长度的前缀和):

$$f[i]=f[j]+{|sum[i]-sum[j]-L-1|}^P$$

这就是状态转移方程,的确很好理解。但是…… 这样子做是 $O(N^2)$ 的复杂度,只能拿 $30$ 分。

而按照题目的数据范围,正解的复杂度因该是 $O(n log n)$ 左右。接下来考虑怎么优化。

打表观察发现,如果我们将每次用作转移 $i$ 的最优的 $j$ 存起来,输出时会发现,$j$ 是单调递增的。

证明的话的确不好证,可以看看 $lyd$ 的书。但是按照实际理解一下是可以的,我们将 $j$ 后面的一直到 $i$ 的句子组成了新的一行,那么如果 $j$ 不单调上升的话,新的一句将会变的很长很长很长,那么这时这句造成的不协调度将会以几何数的形式疯狂增长,那么唯一的方法就是将这句长句断句,这样子 $j$ 就会变大,可以感性理解一下 $QvQ$。

但是我们知道了 $j$ 是单调上升的这条性质有什么用呢?

很显然,每一次转移的时候不必往前找了,直接往后找。

我们维护一个队列,队列里的每一个元素有三个变量:$l,r,c$ ,其中 $l$ 和 $r$ 表示 $c$ 这个决策的适用范围,并且在这个范围中 $c$ 是最优的 $j$。

那么现在有了一个新的 $i$,考虑怎么维护这个队列。

我们可以先找到 $i$ 所在的范围的最优的 $j$,那么这时我们检查队头,如果队头的范围已经不包括 $i$ 了,那么直接弹出,因为既然队头的范围不包括 $i$ 了,那么这个队头对 $i+1$ 及后面的元素都不能产生贡献,故直接弹出。

弹出无用的队头后,转移的话就是 $O(1)$ 了:直接取队头转移不就好了吗?

那么现在考虑怎么将 $i$ 加入这个队列,或许这个 $i$ 也会对后面的元素产生贡献。

我们检查当前的队尾,怎么判断这个队尾是否比 $i$ 更优呢?现在队尾的范围是 $l,r$ ,如果 $i$ 更新 $l$ 比 $c$ 更新 $l$ 更优,显然 $i$ 会比当前 $l,r$ 范围类的所有的 $c$ 更优,故弹出队尾。

那么,假设现在我们碰到了一个队尾,其中 $i$ 更新 $r$ 更优, $c$ 更新 $l$ 更优,怎么办呢?也就是说这个元素的范围中分成两半,前一半 $c$ 更新更优,后一半 $i$ 更新更优,显然要拆成两个队列元素。那么我们怎么知道这个位置呢?二分!

那么这个时候我们可以得到答案了,只是输出怎么办呢?

很简单,每次转移的时候记录一下转移自哪里,这就是分行,然后输出即可。

最后就是精度问题。

题目要求,如果 $f[n]$ (即所有句子排版后的最小不协调度) 还是大于了 $1e18$ ,那么输出 “$Too \ hard\ to\ arrange$”,但是如果在 $DP$ 的过程中就炸了 $long \ long$,那就 $GG$ 了。所以我们使用 $long \ double$ ,精度更高,(不会 $int$ 的,这辈子也不会用 $int$ 的)。

Code:

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

typedef long long ll;
typedef long double ld;

const int NS=1e5+2;
const int inf=1e9+9;

int T,N,L,P;
int head,tail;
int last[NS],ans[NS],Next[NS];
struct Node{int c,l,r;}q[NS];
char s[NS][35];
ld sum[NS],f[NS];

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

void clear(){
    memset(last,0,sizeof(last));
    memset(sum,0,sizeof(sum));
    memset(q,0,sizeof(q));
    memset(s,0,sizeof(s));
    memset(f,0,sizeof(f));
}

ld pows(ld x,int y){//快速幂
    ld ans=1;
    for(;y;y>>=1,x*=x)if(y&1)ans*=x;
    return ans;
}

ld val(int j,int i){//转移函数
    return f[j]+pows(abs(sum[i]-sum[j]-L-1),P);
}

void half(int i){//二分过程
    int now=q[tail].c,ls=q[tail].l,rs=q[tail].r;//当前队尾范围
    int ret=q[tail].r+1;
    while(ls<=rs){
        int mid=(ls+rs)>>1;
        if(val(i,mid)<=val(now,mid))rs=mid-1,ret=mid;//i 更优
        else ls=mid+1;//c 更优
    }
    if(ret!=q[tail].l)q[tail].r=ret-1;//分成了两半
    else --tail;//整个元素都比不过 i
    if(ret<=N)q[++tail]=(Node){i,ret,N};//i 分了一个区间时,加入新元素
}

void output(){//值得拥有的鬼畜输出
    if(f[N]>1e18)puts("Too hard to arrange");//无解,放心判 1e18
    else{
        printf("%lld\n",(ll)(f[N]+0.5));//注意精度问题
        for(int i=N;i;i=last[i])Next[last[i]]=i;//输出
        int now=0;
        for(int i=1;i<=N;++i){
            now=Next[now];
            for(int j=i;j<now;++j)printf("%s ",s[j]);
            printf("%s\n",s[now]);
            i=now;
        }
    }
    puts("--------------------");//注意
    return;
}

int main(){
    IN(T);
    while(T--){
        clear();
        IN(N),IN(L),IN(P);
        for(int i=1;i<=N;++i){
            scanf("%s",s[i]);
            sum[i]=sum[i-1]+strlen(s[i])+1;//做前缀和
            /*因为输出是有空格的,所以加上一个 1*/
        }
        q[head=tail=1]=(Node){0,1,N};//初始元素
        for(int i=1;i<=N;++i){
            while(head<tail&&q[head].r<i)++head;//淘汰无用队头
            ++q[head].l;
            f[i]=val(q[head].c,i);//O(1) 转移
            last[i]=q[head].c;//记录 “转移自哪里”
            while(head<tail&&val(i,q[tail].l)<=val(q[tail].c,q[tail].l))tail--;//弹出劣质队尾
            half(i);//二分
        }
        output();//鬼畜输出
    }       
    return 0;//终于结束
}

最后,我有个问题。

这是写的什么文章啊 $QvQ$ ,让我们来猜测一下。


白日依山尽,黄河入海流,欲穷千里目,更上一层楼。

这是 小 $G$ 写的?作者明明不是小 $G$ 好不好。

$QvQ$ 有毒啊……

分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

2 条评论

quhengyi11 · 2019年2月25日 9:57 下午

qwq 问个文题无关的问题

luogu 的 material 化不是自从换了主页之后咕掉了喵

您的背景是怎么搞的 QAQ

    Qiuly · 2019年2月26日 7:06 下午

    学长,这个问题的话,网上是有文章的。

    我是按这个文章设置的:https://www.luogu.org/blog/zhyan/luo-gu-bei-jing

发表评论

电子邮件地址不会被公开。 必填项已用*标注