【CF750E】New Year and Old Subsequence

题目大意：给定一个长度为 N 的字符串，定义一个字串是“好的”，当且仅当字串中含有一个 “2017” 的子序列，且不含有 “2016” 的子序列。现给出 M 个询问，每次询问区间 [l, r] 内至少删去多少个字符才能使得该区间变成“好的”。

题解：

由于题目中要求的是子序列，且序列长度仅为 4，考虑状压，即："" -> 0, “2” -> 1, "20" -> 2, "201" -> 3, "2017" -> 4。现假设只有一次询问的话，可以进行全局的一次 dp，状态为：dp[i][s] 表示到 i 下标为止，序列的状态是 s 需要删去的最小字符个数。可以发现转移方程仅与 i - 1 有关，又考虑到要回答区间 [l, r] 的询问，可以采用线段树维护矩阵乘法的形式。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

const int inf = 0x3f3f3f3f;

char s[maxn];

int n, m;

struct matrix {

	int mat[5][5];

	matrix() {

		memset(mat, 0x3f, sizeof(mat));

	}

	int *operator[](int x) {

		return mat[x];

	}

	friend matrix operator*(matrix &x, matrix &y) {

		matrix z;

		for (int i = 0; i <= 4; i++) {

			for (int j = 0; j <= 4; j++) {

				for (int k = 0; k <= 4; k++) {

					z[i][j] = min(z[i][j], x[i][k] + y[k][j]);

				}

			}

		}

		return z;

	}

};

struct node {

	#define ls(o) t[o].lc

	#define rs(o) t[o].rc

	int lc, rc;

	matrix mat;

} t[maxn << 1];

int tot, rt;

inline void pull(int o) {

	t[o].mat = t[ls(o)].mat * t[rs(o)].mat;

}

void build(int &o, int l, int r) {

	o = ++tot;

	if (l == r) {

		for (int i = 0; i < 5; i++) t[o].mat[i][i] = 0;

		if (s[l] == '2') t[o].mat[0][1] = 0, t[o].mat[0][0] = 1;

		if (s[l] == '0') t[o].mat[1][2] = 0, t[o].mat[1][1] = 1;

		if (s[l] == '1') t[o].mat[2][3] = 0, t[o].mat[2][2] = 1;

		if (s[l] == '7') t[o].mat[3][4] = 0, t[o].mat[3][3] = 1;

		if (s[l] == '6') t[o].mat[3][3] = 1, t[o].mat[4][4] = 1;

		return;

	}

	int mid = l + r >> 1;

	build(ls(o), l, mid);

	build(rs(o), mid + 1, r);

	pull(o);

}

matrix query(int o, int l, int r, int x, int y) {

	if (l == x && r == y) {

		return t[o].mat;

	}

	int mid = l + r >> 1;

	if (y <= mid) {

		return query(ls(o), l, mid, x, y);

	} else if (x > mid) {

		return query(rs(o), mid + 1, r, x, y);

	} else {

		matrix ansl = query(ls(o), l, mid, x, mid);

		matrix ansr = query(rs(o), mid + 1, r, mid + 1, y);

		return ansl * ansr;

	}

}

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0), cout.tie(0);

	cin >> n >> m >> s + 1;

	build(rt, 1, n);

	while (m--) {

		int l, r;

		cin >> l >> r;

		int ans = query(rt, 1, n, l, r)[0][4];

		cout << (ans == inf ? -1 : ans) << endl;

	}

	return 0;

}

巴特西

【CF750E】New Year and Old Subsequence

最新文章

热门文章