枫林晚 的博客

枫林晚 的博客

题解 P3566 【[POI2014]KLO-Bricks】

posted on 2018-10-31 21:20:40 | under 题解 |

全网唯一 一篇O(n)题解+bzoj/luogu最优解

(截止2018.10.31)

这个题看大家都是优先队列,然后直接贪心放置。

还有用权值线段树来模拟堆过的%%%。

其实不用带logn也可以过的。

大家的方法是从左往右扫过去的。

对于这种插空排序的问题,还有一种考虑方法就是每个种类每个种类来考虑。

好处是,前面放过的种类放完了,和当前第i种永远不会产生冲突。

这就是我的大方向思路。

一、先不考虑端点固定的情况。

其实,不一定要先放最多的。

顺序可以随便。

假设放到完了前i种,那么,一共有sum[i]个。

对于后面的n-i种来说,前i种的方法对后面没有影响。

所以,肯定前i种放法中,选择相邻的情况最少的方案咯!

怎样凑出这个方案?

放完了前i种,设还剩下k个相邻位置。

1.对于第i种,肯定先插那k个位置中。这样每次相邻的-1,已经最优。

2.如果i种还剩下,那就从前面开始插空(不能和1中放的相邻)。这样相邻的数量不增不减。已经最优。

3.如果还剩下,那没有办法了。为了之后好处理,我们都把这些剩下的都放在末尾。

这样,不管你是数量较多的,还是数量较少的,

较多的,可以放在一起,由后面的再插空隔开。

较少的,就隔开之前相邻的。

至于怎么插空?

用一个最普通的链表就可以维护。

当然,我们每次要维护3中,开始连续的那一串的起始位置。方便下次直接访问。

二、有固定点呢?

两个端点比较麻烦。

所以我们就先放端点好了。

放的方法和上面差不多。

先放p,再放q

如果p的数量大于等于q。

那么放q的时候,直接插空,然后无论如何留下一个放末尾。

如果p的数量小于q。

那么放q的时候,插完空,直接往后放完即可。

(注意的是,这样的话有一个情况,就是在最后一个和倒数第二个之间还要插一个,后面放的时候特判一下)

然后放剩下k-2种。

按照刚才的策略即可。注意不能放在1前面,以及最后一个后面。

由于策略一直是最优的。

所以放完了之后,还有相邻元素,那就无解了。

三、一些细节

1.可能有两个端点颜色相同的情况。特判即可。bzoj上还有端点相同,且这个颜色只有一个的数据。。。。

2.刚才“二”中说的那个注意事项。

3.乱七八糟的各种边界情况和+1-1等等。

画个示意图就好理解了。

代码:

全程链表,所以复杂度线性。

(其实应该还有很多常数优化空间2333)

(这个题输入输出优化都很有用,输出优化快了400ms???)

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
const int N=1000000+5;
int nxt[N],id[N];//nxt后继,id颜色编号 
int tot;
int k,p,q;
int a[N];
il void rd(int &x){
    char ch;x=0;
    while(!isdigit(ch=getchar()));
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
}
il void prin(int x){
    if(x/10) prin(x/10);
    putchar(x%10+'0');
}
il void upda(int o,int to,int d){//初始化链表元素 
    nxt[o]=to;id[o]=d;
} 
int main(){
    rd(k);rd(p);rd(q);
    for(reg i=1;i<=k;++i)rd(a[i]);
    if(p==q&&a[p]==1){//特判一个点 
        if(k>1) printf("0");
        else printf("%d",p);
        return 0;
    }
    int las=0;
    for(reg i=1;i<=a[p];++i){//放p 
        upda(++tot,0,p);
        if(las) nxt[las]=tot;las=tot;
    }
    las=1;
    int pos=0;//pos是每一次最后的连续一部分同种相邻颜色的起始位置 
    if(p!=q){//放q 
        int i;
        for(i=1;i<=a[q]-1&&las<=a[p];++i){
            upda(++tot,nxt[las],q);
            nxt[las]=tot;++las; 
        }
        if(a[p]>=a[q]){
            nxt[a[p]]=++tot;
            upda(tot,0,q);
            pos=a[q];
        }
        else{
            pos=tot;
            while(i<=a[q]){
                nxt[tot]=tot+1;
                upda(++tot,0,q);
                ++i;
            }
        }
    }
    else{
        pos=1;
    }
    int nd=tot;//末尾的编号 
    for(reg i=1;i<=k;++i){//放其他的 
        if(i==p||i==q) continue;
        int tmp=a[i];
        while(a[i]&&nxt[pos]!=nd){//插后面的空 
            upda(++tot,nxt[pos],i);
            nxt[pos]=tot;
            a[i]--;++pos;
        }
        if(a[i]&&nxt[pos]==nd&&id[pos]==q){//细节2 
            upda(++tot,nxt[pos],i);
            nxt[pos]=tot;
            pos=tot;//warning!!!
            a[i]--;
        }
        if(a[i]){//从前面插空 
            int now=1;//start from a[p]
            while(a[i]&&id[nxt[now]]!=i&&nxt[now]!=nd){
                upda(++tot,nxt[now],i);
                int to=nxt[now];
                nxt[now]=tot;
                now=to;
                a[i]--;
            }
            if(a[i]){//如果还有剩余 
                int las=pos;
                if(id[pos]!=i) pos=tot+1;//warning!!! tot+1
                while(a[i]){
                    upda(++tot,nxt[las],i);
                    nxt[las]=tot;
                    las=tot;
                    a[i]--;
                }
            }
        }
    }
    for(reg i=1;i!=nd;i=nxt[i]){//判断不合法 
        if(id[i]==id[nxt[i]]){
            printf("0");return 0;
        }
    }
    for(reg i=1;i!=nd;i=nxt[i]){
        prin(id[i]);putchar(' ');
    }prin(id[nd]);
    return 0;
}

总结:

注意处理排序插空问题的两个大方法:

1.从左到右扫描。期间往往用数据结构维护。

2.分类别,同一个类别一起考虑。往往用到对插入的物品排序(当然本题不用)