首页 > 其他分享 >P9192 [USACO23OPEN] Pareidolia P 题解

P9192 [USACO23OPEN] Pareidolia P 题解

时间:2024-11-07 21:57:59浏览次数:1  
标签:USACO23OPEN P9192 return Mat int 题解 序列 dp define

P9192 [USACO23OPEN] Pareidolia P 题解

首先自然考虑不带修的情况。

考虑问题的本质就是求序列中 尽量短bessie 序列个数。对于 尽量短 的理解是对于 bessiebessie 序列,不考虑其由 \(1,8\sim 12\) 构成的序列,只考虑 \(1\sim 6,7\sim 12\) 组成的序列。

于是考虑 dp:设 \(dp_{i,j}\) 表示前 \(i\) 个字符,下一个匹配的是 bessie 第 \(0\sim 5\) 位置的数量。注意 dp 时维护 尽量短 的序列要求是维护新的字符转移后删去原有字符的贡献,这样的 dp 记录的是每一个 bessie 结尾处的贡献,于是对答案前缀和。具体见代码:

#include <bits/stdc++.h>
#define N 200005
#define M 6
#define int long long
using namespace std;
int T;
int n;
string s;
int dp[N][M];
void keep() {
	int res = 0;
	int ans = 0;
	memset(dp, 0, sizeof dp);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < M; j++)
			dp[i][j] = dp[i - 1][j];
		if (s[i] == 'b') {
			dp[i][1] += dp[i][0];
			dp[i][0] = 0;
		}
		else if(s[i] == 'e') {
			dp[i][2] += dp[i][1];
			dp[i][1] = 0;
			ans += dp[i][5];
			dp[i][0] += dp[i][5];
			dp[i][5] = 0;
		}
		else if(s[i] == 's') {
			dp[i][4] += dp[i][3];
			dp[i][3] = 0;
			dp[i][3] += dp[i][2];
			dp[i][2] = 0;
		}
		else if (s[i] == 'i') {
			dp[i][5] += dp[i][4];
			dp[i][4] = 0;
		}
		if (s[i] == 'b') ++dp[i][1];
		else ++dp[i][0];
		res += ans;
	}
	cout << res << "\n";
}
signed main() {
	cin >> s;
	n = s.size();
	s = " " + s;
	cin >> T;
	keep();
	while (T--) {
		int x;
		char v[4];
		scanf("%lld%s", &x, v);
		s[x] = v[0];
		keep();
	}
	return 0;
}

对于带修的情况,考虑 dp 的转移维度很少,是近似线性的,考虑矩阵优化,建出矩阵线段树维护动态 dp 即可。

代码:

#include <bits/stdc++.h>
#define N 200005
#define M 9
#define int long long
using namespace std;
string s;
int T;
int n;
struct Mat {
	int a[M][M];
	Mat() {
		memset(a, 0, sizeof a);
	}
};
Mat operator * (Mat a, Mat b) {
	Mat res;
	for (int i = 0; i < M; i++)
		for (int j = 0; j < M; j++)
			for (int k = 0; k < M; k++)
				res.a[i][j] += a.a[i][k] * b.a[k][j];
	return res;
}

Mat newnode(char c) {
	Mat a;
	for (int i = 0; i < M; i++)
		a.a[i][i] = 1;
	if (c == 'b') {
		a.a[8][1] = 1;
		a.a[0][1] = 1;
		a.a[0][0] = 0;
	}
	else if(c == 'e') {
		a.a[8][0] = 1;
		a.a[1][2] = 1;
		a.a[1][1] = 0;
		a.a[5][6] = 1;
		a.a[5][7] = 1;
		a.a[5][0] = 1;
		a.a[5][5] = 0;
	}
	else if(c == 's') {
		a.a[8][0] = 1;
		a.a[3][4] = 1;
		a.a[3][3] = 0;
		a.a[2][3] = 1;
		a.a[2][2] = 0;
	}
	else if(c == 'i') {
		a.a[8][0] = 1;
		a.a[4][5] = 1;
		a.a[4][4] = 0;
	}
	else a.a[8][0] = 1;
	a.a[6][7] = 1;
	return a;
}
#define lc (p << 1)
#define rc (lc | 1)
Mat e[N << 2];
void push_up(int p) {
	e[p] = e[lc] * e[rc];
}
void build(int p, int l, int r) {
	if (l == r)
		return e[p] = newnode(s[l]), void();
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	push_up(p);
}
void update(int p, int l, int r, int x) {
	if (l == r && l == x)
		return e[p] = newnode(s[l]), void();
	int mid = (l + r) >> 1;
	if (x <= mid) update(lc, l, mid, x);
	else update(rc, mid + 1, r, x);
	push_up(p); 
}

void kudo() {
	Mat bas;
	bas.a[0][8] = 1;
	bas = bas * e[1];
	cout << bas.a[0][7] << '\n';
}

signed main() {
	cin >> s;
	n = s.size();
	s = " " + s;
	build(1, 1, n);
	kudo();
	cin >> T;
	while (T--) {
		int x;
		char v[4];
		scanf("%lld%s", &x, v);
		s[x] = v[0];
		update(1, 1, n, x);
		kudo();
	}
	return 0;	
}

标签:USACO23OPEN,P9192,return,Mat,int,题解,序列,dp,define
From: https://www.cnblogs.com/Rock-N-Roll/p/18534095

相关文章

  • CF1956F Nene and the Passing Game 题解
    处理很妙的题,部分细节请教了未来姚班zyl和LYH_cpp,在此鸣谢。首先考虑把题目给的式子进行转化,设\(i<j\),那么\(i\)和\(j\)能传球当且仅当\(l_i+l_j\lej-i\ler_i+r_j\)。移项并拆开得到,\(i+l_i\lej-l_i\)且\(i+r_i\gej-r_j\),如果画到数轴上的话......
  • 题解:P11253 [GDKOI2023 普及组] 小学生数学题
    所求的式子带除法,模意义下除法计算复杂度带\(\log\)太慢了,先改写成乘法:\(\sum_{i=1}^ni!\timesi^{-k}\)。想求这个式子,最简单的思路就是对于每个整数\(i\in[1,n]\),分别预处理出\(i!\)和\(i^{-k}\)的值,最后乘起来再\(O(n)\)暴力加起来就好了!对于\(i!\),注意到:\[i!=\b......
  • P4621 [COCI2012-2013#6] BAKTERIJE 题解
    一道很好的数学题。首先不难想到每个细菌的移动路线是有循环节的,循环节外的时间最多就是每个格子的四个方向都走一遍,也就是\(4\timesN\timesM\)。可以预处理每个细菌分别通过四个方向第一次到达终点的时间\(b_{i,0/1/2/3}\)和再次回到当前状态的循环节长度\(md_{i,0/1/2/......
  • 题解:[BZOJ2958] 序列染色
    ProblemLinkBZOJ2958序列染色题意给出一个长度为\(n\),由\(\ttB,W,X\)三种字符组成的字符串\(S\),你需要把每一个\(\ttX\)染成\(\ttB\)或\(\ttW\)中的一个。Solution字符串,染色,方案数,一眼\(dp\)。要求前半段是B,后半段是W。考虑容斥。\(f_{i,0/1},g_{i,......
  • IOR的脚本化、版本兼容性及常见问题解答
    脚本化IOR可以使用-f选项在命令行中使用输入脚本。在-f选项之前设置的命令行选项将被视为运行脚本的默认设置。例如:mpirun./ior-W-fscript将使用隐式-W运行脚本中的所有测试。脚本本身可以覆盖这些设置,并且可以设置为在一次执行下运行许多不同的IOR测试,重要的是要注意在-......
  • 【题解】CF1944
    CF1944A简要题意给定完全图删k条边使得从一号点开始的可达点最少Solution注意到最多需要删n-1条边就可以使得任意一个其他点都到达不了又注意到只要删的边少于n-1就可以从一号点走出去,主要走出去就可以走到任何点所以这题答案只有两种如果k≤n-1答案为n否则答案为1......
  • 题解:P11248 [GESP202409 七级] 矩阵移动
    题目传送门题目大意给出一个nnn行mmm列的只包含0、1、?的矩......
  • 【记录】Cordial Sync具身智能协作源码复现及问题解决
    论文简要总结智能体需要合作将家具移动到客厅的指定位置。这个任务与现有的任务不同,它要求智能体在每个时间步都必须进行协调。模型部分1.SYNC-policies(SynchronizeYourActionsCoherently)为了解决智能体在每个时间步都需要协调的问题,研究者提出了SYNC-policies。这......
  • AtCoder Beginner Contest 284题解
    AtCoderBeginnerContest284A没有什么难点,反着输出一遍就可以了。#include<bits/stdc++.h>usingnamespacestd;stringa[2000];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=n;i;i--)cout<<a[i]<<'\n';......
  • 题解:HDU5628 Clarke and math
    数学题可爱捏~HintAnalysis注意到形式很好看,猜测是某种神奇迭代。考虑特殊情况\(k=1\),于是有:\(g(i)=\sum_{i_1\midi}f(i_1)=(f*1)(i)\)$即\(g=f*1\)。于是猜测\(g=f*1^k\),这里的幂运算表示多次Dirichlet卷积。简单证明一下,采用数学归纳法:基本情况\(k=1\),已经证过,......