New Year and Old Subsequence CodeForces - 750E(线段树 + 矩阵)

New Year and Old Subsequence (CodeForces - 750E)

题意:

给出一个长度为\(N\)的数字串,\(q\)次询问。每次询问一段区间。在区间内删除尽量少的字符,使得区间内含有序列"\(2017\)",且不含有"\(2016\)"。

\(n,q<=200000\)。

题解:

用\(01234\)五种状态分别表示""、 "\(2\)"、"\(20\)"、"\(201\)"、"\(2017\)"。

设矩阵\(M[5][5]\),\(M[i][j]\)表示从状态\(i\)转移到\(j\)需要删除的最少字符数量。

例如,\('2'\)可以把状态\(0\)转移到状态\(1\),所以矩阵就是

\[a=\left[
\begin{matrix}
1 & 0 & \inf & \inf & \inf \\inf & 0 & \inf & \inf & \inf \\inf & \inf & 0 & \inf & \inf \\inf & \inf & \inf & 0 & \inf \\inf & \inf & \inf & \inf & 0
\end{matrix}
\right]\]

代表,如果我们删去这个\('2'\),维持本来的状态\(0\),花费就是\(1\)。如果不删,那么状态\(0\)就可以转移到状态\(1\),所以\(a[0][1] = 0\)。

对于\('0'\ '1'\ '7'\)同理可构造类似的矩阵。

对于\('6'\),可以构造如下矩阵

\[a=\left[
\begin{matrix}
0 & \inf & \inf & \inf & \inf \\inf & 0 & \inf & \inf & \inf \\inf & \inf & 0 & \inf & \inf \\inf & \inf & \inf & 1 & \inf \\inf & \inf & \inf & \inf & 1
\end{matrix}
\right]\]

表示,如果之前有"\(201\)" 或者 "\(2017\)",这个\('6'\)就需要删除。否则就不用删除。

对于两个矩阵的合并,我们只要像\(Floyd\)算法那样,枚举转移就可以了。

因为矩阵的状态转移是满足结合律的,所以用线段树维护区间,就可以多组查询了。

以后再遇到区间上的状态转移,可以尝试用这种方法瞎搞一搞。

代码

#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
typedef long long LL;

char s[maxn];

struct Matrix {
    int m[5][5];
    Matrix() { memset(m, 0x3f, sizeof(m)); }
    Matrix operator * (const Matrix &rhs) {
        Matrix res;
        for (int k = 0; k <= 4; k++)
        for (int i = 0; i <= 4; i++)
        for (int j = 0; j <= 4; j++)
            res.m[i][j] = min(res.m[i][j], m[i][k] + rhs.m[k][j]);
        return res;
    }
};

struct SegTree {
    struct Node {
        int l, r;
        Matrix M;
    }t[maxn * 4];

    void build(int id, int l, int r) {
        t[id].l = l, t[id].r = r;
        if (l == r) {
            for (int i = 0; i <= 4; i++) t[id].M.m[i][i] = 0;
            if (s[l] == '2') { t[id].M.m[0][0] = 1; t[id].M.m[0][1] = 0; }
            if (s[l] == '0') { t[id].M.m[1][1] = 1; t[id].M.m[1][2] = 0; }
            if (s[l] == '1') { t[id].M.m[2][2] = 1; t[id].M.m[2][3] = 0; }
            if (s[l] == '7') { t[id].M.m[3][3] = 1; t[id].M.m[3][4] = 0; }
            if (s[l] == '6') { t[id].M.m[3][3] = 1; t[id].M.m[4][4] = 1; }
            return;
        }
        int mid = (l+r) / 2;
        build(id*2, l, mid);
        build(id*2+1, mid+1, r);
        t[id].M = t[id*2].M * t[id*2+1].M;
    }

    Matrix query(int id, int l, int r) {
        if (l <= t[id].l && r >= t[id].r) return t[id].M;
        int mid = (t[id].l + t[id].r) / 2;
        if (r <= mid) return query(id*2, l, r);
        else if (l > mid) return query(id*2+1, l, r);
        return query(id*2, l, mid) * query(id*2+1, mid+1, r);
    }
}T;

int l, r, n, q;
int main() {
    //fopi;
    scanf("%d%d", &n, &q);
    scanf("%s", s+1);
    T.build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &l, &r);
        int res = T.query(1, l, r).m[0][4];
        printf("%d\n", res >= inf ? -1 : res);
    }
}

原文地址:https://www.cnblogs.com/ruthank/p/11506185.html

时间: 09-11

New Year and Old Subsequence CodeForces - 750E(线段树 + 矩阵)的相关文章

ZOJ 3772 Calculate the Function 线段树+矩阵

Calculate the FunctionTime Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Submit Status Appoint description:  System Crawler  (2014-04-09) Description You are given a list of numbers A1A2 .. AN and M queries. For the i-th query

Codeforces 833B 线段树优化 dp

Codeforces  833B  The Bakery 题意: n 个数要分成 k 块,每块的价值是其不同数的个数,问价值和最大是多少. tags: dp[i][j]表示前 j 个数分成 i 块的最大权值和,转移: dp[i][j] = max( dp[i-1][k] + val[k+1][j] ) , k是 1~j . 但这个过程其实并不好转移,要利用累加的特点,用线段树进行优化 (感觉我不看题解是想不到的,2333) 大概就是,对于第 i 层,我们假定已经知道了第 i-1 层,也就是求出了

codeforces 589G:线段树+二分

离线做 先按照t[]建线段树,维护区间的有效天数以及可用时间 然后把t[]从小到达排序,记得记录t中元素在线段树中的位置 把询问按照d从小到大排序,依次考虑 由于按照d排序,所以当前询问肯定是d最短的,我们在t数组中找到大于当前d的第一个元素位置,把这之前的元素全部从线段树中删除,表示这些天数无效 因为当前d已经是最小,所以删除对后续不会有影响 二分一个天数,查找0~mid天一共的工作时间(工作时间=总可用时间-准备时间*有效天数) #include"cstdio" #include&

CodeForces 343D 线段树维护dfs序

给定一棵树,初始时树为空 操作1,往某个结点注水,那么该结点的子树都注满了水 操作2,将某个结点的水放空,那么该结点的父亲的水也就放空了 操作3,询问某个点是否有水 我们将树进行dfs, 生成in[u], 访问结点u的时间戳,out[u],离开结点u的时间戳 每个结点的in值对应在线段树中的区间的一点 那么对于操作1, 只要将区间[in[u],out[u]] 的值都改为1, 但是如果区间[in[u],out[u]] 原先存在为0的点,那么父区间肯定是空的,这个操作不能 改变父区间的状态,所以需要

线段树 + 矩阵 --- ZOJ 3772 Calculate the Function

Calculate the Function Problem's Link:   http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3772 Mean: 略 analyse: 简单的线段树维护矩阵. 矩阵乘法的结合律(a * b * c == a * (b * c)),注意矩阵乘法不满足分配率(a *b != b * a). 令 M[x] = [1 A[x]]              [1     0 ] ,那么有 [ F

hdu 5068(线段树+矩阵乘法)

矩阵乘法来进行所有路径的运算, 线段树来查询修改. 关键还是矩阵乘法的结合律. Harry And Math Teacher Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 326    Accepted Submission(s): 89 Problem Description As we all know, Harry Porter

CF719E(线段树+矩阵快速幂)

题意:给你一个数列a,a[i]表示斐波那契数列的下标为a[i],求区间对应斐波那契数列数字的和,还要求能够维护对区间内所有下标加d的操作 分析:线段树 线段树的每个节点表示(f[i],f[i-1])这个数组 因为矩阵的可加性,所以可以进行lazy操作 我最开始的想法是每个节点lazy表示该区间下标加了多少,add表示该区间已经加的下标对应的矩阵乘积,这样更新lazy是O(1)的,算add是O(logn)的 但是这样每次pushdown的时候,add下传总要多个log,会TLE 更好的办法是laz

Codeforces 19D(线段树+离散化)

题意:题意很好理解,三种操作: (1)add x y,添加坐标(x,y),(2)del x y,删除坐标(x,y),(3)find x y,找到并输出严格大于(x,y)的坐标里的最小坐标. 题解:因为点有200000个,而点坐标最大到1e9,所以要离散化处理,我们只需要对x离散化,然后每个x对应一个set存y,然后每次修改操作的时候,根据set内的值维护最大y. #include <cstdio> #include <cstring> #include <set> #i

河南省多校联盟二-F 线段树+矩阵

---恢复内容开始--- 1284: SP教数学 时间限制: 2 秒  内存限制: 128 MB提交: 24  解决: 4 题目描述 输入 输出 对于每组数据的2操作,输出一行对1e9 + 7取模的答案 样例输入 7 4 2 2 1 1 3 3 2 2 1 5 2 6 7 1 3 4 3 2 6 6 样例输出 6 3 2 提示 1 <=  n ,m <=10^5 一道很有趣的ST的题目,有趣在维护节点时用到了矩阵运算,减少了计算量. 首先对于矩阵运算法则,百度百科: 基本性质 乘法结合律: (

[tsA1490][2013中国国家集训队第二次作业]osu![概率dp+线段树+矩阵乘法]

这样的题解只能舔题解了,,,qaq 清橙资料里有.. 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <ctime> 7 #include <algorithm> 8 9 using namespace std; 10 11 struct Mat