题解 P1564 膜拜

· · 题解

Statement

给长度为 n 的 \texttt{12} 串 s 分成若干个子串，使得每个子串要么全部同字符，要么 \texttt{1,2} 个数差不大于 m。求最少的子串个数。

Solution

提供一个显然的 O(n\log n) 解法。优于目前所有题解。

记 f_i 表示子串 s_1...s_i 中 1 比 2 多几个。

记 g_i 表示子串 s_1...s_i 的最少划分数。

那么 g_i=\min\{g_j+1\}(1\le j <i) 其中 j 需要满足 s_{j+1}...s_i 同字符或者 |f_i-f_j|\le m。

第一种情况很好维护。而对于第二种情况，只需要在算出每一个 g_j 的时候把 g_j 的值扔到一个序列里面下标为 f_j 的位置，如果比原来的值小就覆盖它，否则就忽略。然后算 g_i 的时候用这个序列 [f_i-m,f_i+m] 这个子区间最小值就可以最快找出最小的满足条件的 g_j。

单点修改，区间最小值，可以用线段树或者树状数组维护。这里用的是线段树结果人傻常数大只拿到次优解。这题数据比较水完全跑不满 O(n\log n)。

注意 f_i 的值可能是负的所以要下标平移。

Code

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int _=10055*2;
int n,m,a[5005],f[5005],g[5005],allsame,mxf=0;
class segtr{// 线段树板子。
    public:
    int minx[_],nl[_],nr[_];
    segtr(int len){
        nl[1]=1,nr[1]=len,minx[1]=_;
        for(int i=2; i<=2*len+5; i++){
            minx[i]=_;
            if(i&1)
                nl[i]= ((nl[i>>1]+nr[i>>1])>>1)+1,
                nr[i]= nr[i>>1];
            else
                nl[i]= nl[i>>1],
                nr[i]= ((nl[i>>1]+nr[i>>1])>>1);
        }
    }
    void modif(int pos,int val,int o=1){
        minx[o]=min(minx[o],val);
        if(nl[o]!=nr[o]){
            if(pos<=nr[o<<1])
                modif(pos,val,o<<1);
            else
                modif(pos,val,o<<1|1);
        }
    }
    int query(int ql,int qr,int o=1){
        if(ql<=nl[o] && nr[o]<=qr)
            return minx[o];
        else if(ql>nr[o] || qr<nl[o])
            return _;
        else 
            return min(query(ql,qr,o<<1),query(ql,qr,o<<1|1));
    }
};
int main(){
    ios::sync_with_stdio(0),
    cin.tie(0),cout.tie(0);
    cin>>n>>m, g[1]=1;
    for(int i=1;i<=n;i++)
        cin>>a[i], 
        f[i]= f[i-1] +1-(a[i]&2), // 计算 f, 用了位运算小技巧
        mxf= max(mxf,abs(f[i])+1); // 偏移量
    segtr tr((mxf<<1)+10); tr.modif(0+mxf,0);
    for(int i=2;i<=n;i++){
        if(a[i]!=a[i-1])
            allsame = i-1; // s[allsame+1..i] 同色。
        g[i]=min(tr.query(f[i]-m +mxf,f[i]+m +mxf)+1,g[allsame]+1);
        if(g[i]<g[allsame])
            allsame=i;
        tr.modif(f[i] +mxf,g[i]);
    }
    cout<<g[n]<<endl;
}