首页 > 其他分享 >arc119f-ti-jie

arc119f-ti-jie

时间:2024-05-08 18:23:29浏览次数:25  
标签:状态 jie val text arc119f tree 12 ti dp

arc119f

自动机写法。开始在做的时候题解没讲每个节点代表什么状态,自己推了一遍,记录一下。

思路

计数,求有多少种替换方式使得 $0$ 到 $n$ 存在一条长度小于等于 $K$ 的路径。

可以做 $O(n^3)$ 的 dp。设 $dp_{i,a,b}$ 表示前 $i$ 个位置,最近的 $A$ 和 $B$ 分别在 $a$ 和 $b$。官方题解是优化 $a$ 和 $b$,发现有意义状态下 $a$ 和 $b$ 的差不超过一定数值。

观察发现,在 $\text{BAA...AAB}$ 处,肯定选择从 $B$ 直接跳过去。具体的,当有连续的 $4$ 个 $A$ 后,会选择直接从两端的 $B$ 越过。所以有效的状态并不多。

考虑建一个自动机来求出任意状态对应的下一个状态。由于 $A$ 和 $B$ 可以取反得到,先只考虑当前在 $A$,在 $B$ 同理。以下几种有用状态。

  • 状态 $0$。当前在 $A$,上一个位置为 $B$,记为 $\text{A}$。

  • 状态 $1$ 即状态 $0$ 反过来,记为 $\text{B}$。

  • 状态 $2$。当前在 $A$,上一个位置为 $B$,下一个位置为 $A$,记为 $\text{AA}$。

  • 状态 $4$。当前在 $A$,上一个位置为 $B$,下两个位置为 $AA$,记为 $\text{AAA}$。

  • 状态 $6$。当前在 $A$,上一个位置为 $B$,下三个位置为 $AAA$,记为 $\text{AAAA}$。此时如果往后有 $B$,直接先后退越过;否则走向自己,不会有 $5$ 个 $A$ 的状态。注意到此时无论如何都会后退,所以稍微调整一下。定义状态 $6$ 为当前在 $B$,接下来有连续 $A$ 且一定会选择跳过。

  • 状态 $8$。当前在 $A$,上一个位置不重要,下一个位置为 $B$,记为 $\text{AB}$。此时可以跳到下一个 $A$,也可以爬到 $B$,但不知道走一步后要去 $A$ 还是 $B$。

  • 状态 $10$ 至 $12$。当前既可以当作在 $A$,也可以当作在 $B$,记为 $\text{O}$,称为状态 $12$。状态 $10$ 表示当前在 $O$,下一个为 $A$,记为 $\text{OA}$。

综上,有 $13$ 种有用状态。

  • $\text{A}$,$\text{AA}$,$\text{AAA}$,$\text{AAAA}$,$\text{AB}$。

  • 上面 $5$ 种状态取反得到当前在 $B$ 的另外 $5$ 种。

  • $\text{OA}$,$\text{OB}$,$\text{O}$。

考虑转移。记 $tree_{i,0/1}$ 表示当前状态为 $i$,加入 $A$ 或 $B$,走向哪一个状态,$val_{i,0/1}$ 为转移的代价。

  • 状态 $\text{A}$。如果加入 $A$,走向状态 $\text{AA}$,点没有移动,代价为 $0$。如果加入 $B$,走向状态 $\text{AB}$,点没有移动,代价为 $0$。

  • 状态 $\text{AA}$。如果加入 $A$,走向状态 $\text{AAA}$,点没有移动,代价为 $0$。如果加入 $B$,走向状态 $\text{AB}$,点向后移动一格,代价为 $1$。

  • 状态 $\text{AAA}$。如果加入 $A$,走向状态 $\text{AAAA}$,点后退一步到上一个 $B$,代价为 $1$。如果加入 $B$,可以先向后再向前越过 $AAA$ 到下一个 $B$,也可以爬两步 $A$,即走向状态 $\text{O}$,代价为 $2$。

  • 状态 $\text{AAAA}$。注意这里状态不同于以前,当前点为 $B$。如果加入 $A$,走向状态自己 $\text{AAAA}$,点不动,代价为 $0$。如果加入 $B$,向前越过 $AAAA$ 到下一个 $B$,即走向状态 $\text{B}$,代价为 $1$。

  • 状态 $\text{AB}$。如果加入 $A$,可以向后走到 $B$,也可以跳到下一个 $A$,即走向状态 $O$,代价为 $1$。如果加入 $B$,虽然没有连续 $4$ 个 $B$,但一定会从 $A$ 跳过这段 $B$,即状态 $\text{BBBB}$,代价为 $0$。

  • 状态 $\text{OA}$。如果加入 $A$,虽然没有连续 $4$ 个 $A$,但一定会把 $O$ 当作 $B$ 跳过这段 $A$,即状态 $\text{AAAA}$,代价为 $0$。如果加入 $B$,可以向后走到 $A$,也可以把 $O$ 当作 $B$ 跳到下一个 $B$,即走向状态 $\text{O}$,代价为 $1$。

  • 状态 $\text{O}$。如果加入 $A$,走向状态 $\text{OA}$,代价为 $0$。如果加入 $B$,走向状态 $\text{OB}$,代价为 $0$。

分析完自动机状态的转移,dp 即可。设 $dp_{i,j,k}$ 表示加入前 $i$ 位,走了 $j$ 步,当前状态为 $k$。

$$dp_{0,0,12}=1$$

$$dp_{i+1,j+val_{k,0},tree_{k,0}}+=dp_{i,j,k}$$

$$dp_{i+1,j+val_{k,1},tree_{k,1}}+=dp_{i,j,k}$$

注意到加入一位并不是走到一位。状态设定的当前走到的点不是状态的最后一位。记录 $dis$ 表示状态的最后一位是 $n-1$,状态设定的当前走到的点离终点的距离,稍微处理即可。

复杂度 $O(13nk)$。

code

int n,m,ans;
char c[maxn];
int tree[15][2],val[15][2];
int dis[7];
int dp[maxn][maxn][15];

int T;
signed main(){
	//	freopen(".in","r",stdin);
	//	freopen(".out","w",stdout);
	
	n=read();m=read();
	scanf("%s",c+1);
	tree[0][0]=2;val[0][0]=0;tree[0][1]=8;val[0][1]=0;
	tree[2][0]=4;val[2][0]=0;tree[2][1]=8;val[2][1]=1;
	tree[4][0]=6;val[4][0]=1;tree[4][1]=12;val[4][1]=2;
	tree[6][0]=6;val[6][0]=0;tree[6][1]=1;val[6][1]=1;
	tree[8][0]=12;val[8][0]=1;tree[8][1]=7;val[8][1]=0;
	tree[10][0]=6;val[10][0]=0;tree[10][1]=12;val[10][1]=1;
	tree[12][0]=10;val[12][0]=0;tree[12][1]=11;val[12][1]=0;
	for(int i=0;i<=5;i++){//状态取反。
		for(int k=0;k<=1;k++){
			if(tree[i*2][k^1]==12)tree[i*2+1][k]=tree[i*2][k^1];
			else tree[i*2+1][k]=tree[i*2][k^1]^1;
			val[i*2+1][k]=val[i*2][k^1];
		}
	}
//	for(int i=0;i<=12;i++)cout<<tree[i][0]<<" "<<val[i][0]<<" "<<tree[i][1]<<" "<<val[i][1]<<"\n";
	dis[0]=dis[3]=dis[4]=dis[5]=dis[6]=1;
	dis[1]=dis[2]=2;
	dp[0][0][12]=1;
	for(int i=0;i<=n-2;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=12;k++){
				if(dp[i][j][k]){
					if(c[i+1]=='A'){
						dp[i+1][j+val[k][0]][tree[k][0]]+=dp[i][j][k];
						dp[i+1][j+val[k][0]][tree[k][0]]%=mod;
					}
					else if(c[i+1]=='B'){
						dp[i+1][j+val[k][1]][tree[k][1]]+=dp[i][j][k];
						dp[i+1][j+val[k][1]][tree[k][1]]%=mod;
					}
					else{
						dp[i+1][j+val[k][0]][tree[k][0]]+=dp[i][j][k];
						dp[i+1][j+val[k][0]][tree[k][0]]%=mod;
						dp[i+1][j+val[k][1]][tree[k][1]]+=dp[i][j][k];
						dp[i+1][j+val[k][1]][tree[k][1]]%=mod;
					}
				}
			}
		}
	}
	for(int j=0;j<=m;j++){
		for(int k=0;k<=12;k++)if(j+dis[k>>1]<=m){
			ans+=dp[n-1][j][k];
			ans%=mod;
		}
	}
	printf("%lld\n",ans);
}

标签:状态,jie,val,text,arc119f,tree,12,ti,dp
From: https://www.cnblogs.com/yhddd/p/18180558

相关文章

  • arc106d-ti-jie
    ARC106D思路左边到右边不好,改为任意一个到另一个。$$ans_x=\frac{1}{2}(\sum_in\sum_jn(a_i+a_j)x-\sum_in(2\timesa_i)^x)$$拆开$k$次方。$$(a_i+a_j)x=\sum_{k=0}x(\binom{x}{k}\times{a_i}^k\times{a_j}^{x-k})$$$$ans_x=\frac{1}{2}(\sum_{k=0}x(\sum_in{a_i}^......
  • agc049a-ti-jie
    agc049a思路期望。与CF280C相似的思路。每个点最多被做一次,或者被其他点影响。设$f_i$表示$i$是否被选,为$0$或$1$。答案为$E[\sumf_i]$,即$\sumf_i$的期望。$$ans=E[\sumf_i]=\sumE[f_i]=\sump_i$$所以答案为每个点被选的概率的和。能影响点$i$使其不被......
  • abc349g-ti-jie
    abc349g思路从前往后枚举$i$,每次对$i+1\lej\lei+a_i$的$j$赋值$b_j=b_{i\times2-j}$。同时有$b_{i+a_i+1}\neb_{i-a_i-1}$。用$ban_{i,j}$记录$i$不能是$j$,如果要给$i$赋值就选最小的。最直接的就是并查集倍增将两段区间并起来。可以用类似马拉车的思路得......
  • Elements in iteration expect to have 'v-bind:key' directives.
    当组件中使用v-for时,如果不指定key,则会有红色警告信息。解决方案如下。方案一:绑定key(亲试有效)//方式一<liv-for="(item,index)inlist":key="index">//方式二<liv-for="(item,index)inlist":key="item.id">//方式三<liv-for="(item,in......
  • GeometryCollection 的类型映射器(TypeHandler)
    byemanjusakafromhttps://www.emanjusaka.top/2024/05/mybatis-typeHandler-geometryCollection彼岸花开可奈何本文欢迎分享与聚合,全文转载请留下原文地址。GeometryCollection是GeoJSON数据模型中的一个类型,用于表示一个几何对象的集合。MySQL8中支持了GeometryCol......
  • 为什么在有@Transactional注解的方法,一定要加rollbackFor异常回滚的异常类型?
    在spring项目中,@Transactional注解默认会回滚运行时异常(RuntimeException)及其子类当你在一个有@Transactional注解方法里面抛了一个Expection类型的异常,呢它是不支持事务回滚的,异常继承体系我们在一个方法里面要对事务进行操作,如果要抛异常,应该抛出untimeException,不能直接......
  • spring刷题记录——to be continue
    在牛客网刷的题目,类似于补基础了?这里按照知识点进行分类,因为发现有些同样的知识点不同的题目还是很痛苦。这里就不用颜色标记了,因为我觉得都要记。Spring容器篇Spring容器也叫做Ioc容器(Ioc,在我之前写的随笔里面也有谈到),本质上就是一个工厂。Sp......
  • Windows下使用ONNXRuntime推理YOLOv8
    一、准备工作将训练好的pt文件转为onnx格式。yoloexportmodel=best.ptformat=onnxdevice=0opset=13dynamic#如果是动态Shape的话,命令行参数dydynamic一定要加上,不然就是static的模型二、下载与安装ONNXRuntime注意:下载安装onnxruntime-gpu时需要保证其与cuda的兼容......
  • c# Dictionary<TKey,TValue>.TryAdd
    原文链接:https://learn.microsoft.com/zh-cn/dotnet/fundamentals/code-analysis/quality-rules/ca1864Dictionary<TKey,TValue>.ContainsKey(TKey) 和 Dictionary<TKey,TValue>.Add 都执行查找操作,这是冗余设置。如果字典中已存在键,Dictionary<TKey,TValue>.Add 也会引发异......
  • Server-side vulnerabilities :path traversal
    来自bp的学院,提供了靶机,是个学习好地方服务器漏洞之路径遍历 就是说网站提供的图片,如果直接通过src="/loadImage?filename=xxx.jpg“读取的话,可以通过构造”filename=../../../etc/passwd"参数,拿到服务器的passwd文件,这样能读取服务器的用户放一个靶机地址:https://portswigg......