The 2019 Asia Nanchang Online Programming Contest C. Hello 2019（區間DP + 線段樹分治 + 矩陣)

The 2019 Asia Nanchang Online Programming Contest C. Hello 2019

題目

給一個 2e5 的字元串，有 2e5 的詢問。每次詢問一個區間【l，r】，問區間裡至少删除多少個字元才能保證不含子串 “8102”，但是要含 “9201”。如果不能滿足要求輸出 -1。

分析

其實這個題是之前 cf 原題的改編，​​CF #750E​​ cf 原題大意是不含 “2016”，要含“2017”。先考慮簡單 cf 版本的：

如果是單次詢問的話可以用區間 DP來做，因為要求删去字元數最小，可以将删去一個字元代價看作 1。

定義狀态 0 1 2 3 4 表示 “”，“2”，“20”，“201”，“2017”。對于每個位置的狀态轉移用矩陣表示：

其中

表示從

狀态轉移到

舉個例子，假設目前位置是 2，那麼矩陣為：

因為從 “” 到 “2” 不需要代價，反而從 “” 保持 “” 需要删去目前字元 2 。目前字元是 0、1、7 同理。

目前字元是 6 時，為了滿足題目要求。那麼狀态 3、4 （帶有 201）保持原來狀态需要花費1 代價。即：

上面是區間為 1 矩陣的情況，對于兩個區間合并這裡重載矩陣乘法，我們知道矩陣乘法是：

這裡因為要求最小代價，是以改成：

上面其實就是區間 DP 的狀态轉移了，可以類比 Floyd 的思想。

這樣就解決了單次詢問，對于多次詢問，可以用線段樹區間查詢分治來做，也就是維護每個一區間的矩陣狀态。（因為區間DP支援區間合并）

這次南昌的題可以倒過來看，相應的區間也要倒過來。就轉化為了 cf 的原題。

擴充：增加單點修改，和每個位置對應的代價，求最小代價。

cf 題目

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define fuck(x) cout << (x) << endl
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 2e5 + 5;

int n, q;
char s[N];

struct mat{
    int a[5][5];
    mat() { memset(a, INF, sizeof(a)); }
    mat operator * (const mat& b) const{
        mat c;
        for(int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                for(int k = 0; k < 5; k++)
                    c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
        return c;
    }
} tr[N<<2];     // 線段樹維護區間矩陣狀态。

void build(int l, int r, int rt){   // 線段樹初始化也就是 DP 矩陣初始化
    if(l == r){
        for(int i = 0; i < 5; i++)
            tr[rt].a[i][i] = 0;
        if(s[l] == '2') tr[rt].a[0][0] = 1, tr[rt].a[0][1] = 0;
        if(s[l] == '0') tr[rt].a[1][1] = 1, tr[rt].a[1][2] = 0;
        if(s[l] == '1') tr[rt].a[2][2] = 1, tr[rt].a[2][3] = 0;
        if(s[l] == '7') tr[rt].a[3][3] = 1, tr[rt].a[3][4] = 0;
        if(s[l] == '6') tr[rt].a[3][3] = 1, tr[rt].a[4][4] = 1;
        return;
    }
    int m = l + r >> 1;
    build(lson);
    build(rson);
    tr[rt] = tr[rt << 1] * tr[rt << 1 | 1];     // pushup
}

mat query(int l, int r, int rt, int L, int R){  // 區間查詢
    if(L <= l && r <= R) return tr[rt];
    int m = l + r >> 1;
    if(R <= m)  // 全在左邊
        return query(lson, L, R);   
    if(m < L)   // 全在右邊
        return query(rson, L, R);
    return query(lson, L, R) * query(rson, L, R);
}

int main(){
    scanf("%d%d %s", &n, &q, s+1);
    build(1, n, 1);
    for (int i = 1, x, y; i <= q; i++){
        scanf("%d%d", &x, &y);
        mat ans = query(1, n, 1, x, y);
        int res = ans.a[0][4] > n ? -1 : ans.a[0][4];
        printf("%d\n", res);
    }
    return 0;
}      

南昌題目：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define fuck(x) cout << (x) << endl
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 2e5 + 5;

int n, q;
char s[N], t[N];

struct mat{
    int a[5][5];
    mat() { memset(a, INF, sizeof(a)); }
    mat operator * (const mat& b) const{
        mat c;
        for(int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                for(int k = 0; k < 5; k++)
                    c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
        return c;
    }
} tr[N<<2];

void build(int l, int r, int rt){
    if(l == r){
        for(int i = 0; i < 5; i++)
            tr[rt].a[i][i] = 0;
        if(s[l] == '2') tr[rt].a[0][0] = 1, tr[rt].a[0][1] = 0;
        if(s[l] == '0') tr[rt].a[1][1] = 1, tr[rt].a[1][2] = 0;
        if(s[l] == '1') tr[rt].a[2][2] = 1, tr[rt].a[2][3] = 0;
        if(s[l] == '9') tr[rt].a[3][3] = 1, tr[rt].a[3][4] = 0;
        if(s[l] == '8') tr[rt].a[3][3] = 1, tr[rt].a[4][4] = 1;
        return;
    }
    int m = l + r >> 1;
    build(lson);
    build(rson);
    tr[rt] = tr[rt << 1] * tr[rt << 1 | 1];     // pushup
}

mat query(int l, int r, int rt, int L, int R){
    if(L <= l && r <= R)
        return tr[rt];
    int m = l + r >> 1;
    if(R <= m)  // 全在左邊
        return query(lson, L, R);   
    if(m < L)   // 全在右邊
        return query(rson, L, R);
    return query(lson, L, R) * query(rson, L, R);
}

int main(){
    scanf("%d%d %s", &n, &q, t+1);
    for(int i = 1; i <= n; i++){
        s[i] = t[n - i + 1];
    }
    build(1, n, 1);
    for (int i = 1, x, y; i <= q; i++){
        scanf("%d%d", &x, &y);
        mat ans = query(1, n, 1, n-y+1, n-x+1);
        int res = ans.a[0][4] > n ? -1 : ans.a[0][4];
        printf("%d\n", res);
    }
    return 0;
}