首页 > 其他分享 >[题解]P3311 [SDOI2014] 数数

[题解]P3311 [SDOI2014] 数数

时间:2024-08-21 09:37:04浏览次数:7  
标签:int 题解 pos dfs SDOI2014 P3311 bool dp 数位

P3311 [SDOI2014] 数数

看到多模式匹配,我们考虑先对所有模式串建立AC自动机。

然后发现这道题和P4052 文本生成器题解)挺像的,后者让求包含至少一个模式串的个数,这道题让求一个也不包含的个数,这个就是一个用不用\(26^m\)去减的问题,很好处理。但这道题还多了一个条件,“幸运数”必须\(\le n\),而\(n\)足足有\(1200\)位,所以很自然地想到数位dp。

实际上,P4052也可以用数位dp来解决,只不过填写没有大小限制,每个节点都可以填A~Z。换到这道题上也一样,只不过记忆化的前提是“当前非前导\(0\)”而且“填写当前位无限制”。

下文中的“答案”均表示“不可读的字符串个数”。

用\(f[pos][p]\)来表示“主串第\(pos\)个字符对应自动机上节点\(p\)”的答案。

数位dp提供\(4\)个参数:

  • int \(pos\):当前在主串的哪一位(从最高位开始,以\(pos=0\)为结束条件)。
  • int \(p\):\(当前pos\)对应自动机上哪个节点。
  • bool \(limit\):填写是否受限(数位dp标配)。
  • bool \(zero\):是否是前导\(0\)(数位dp标配)。

用\(f\)记忆化即可。

int dfs(int pos,int p,bool limit,bool zero){
	if(en[p]) return 0;//如果遇到字符串结尾,则答案一定为0
	if(!pos) return !zero;//限定正整数
	if(!limit&&!zero&&~f[pos][p]) return f[pos][p];
	int rig=limit?a[pos]:9;
	int ans=0;
	for(int i=0;i<=rig;i++){
		int tzero=zero&&!i;
		ans=(ans+dfs(pos-1,tzero?0:tr[p][i],limit&&i==rig,tzero))%mod;
	}
	if(!limit&&!zero) f[pos][p]=ans;
	return ans;
}

时间复杂度\(O(\log_{10}n\times \sum|s|\times |\Sigma|)\)。

点击查看代码
#include<bits/stdc++.h>
#define mod 1000000007
#define N 1510//节点数(模式串总长)
#define M 1210//主串长度
#define C 10//字符集大小
using namespace std;
int n,m,tr[N][C],fail[N],cnt;
int q[N],head,tail,f[M][N],a[M];
bool en[N];
string s,t;
void ins(string s){
	int p=0;
	for(char i:s){
		int c=i-'0';
		if(!tr[p][c]) tr[p][c]=++cnt;
		p=tr[p][c];
	}
	en[p]=1;
}
void get_fail(){
	head=0,tail=-1;
	for(int i=0;i<C;i++) if(tr[0][i]) q[++tail]=tr[0][i];
	while(head<=tail){
		int u=q[head++];
		for(int i=0;i<C;i++){
			if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q[++tail]=tr[u][i],
				en[tr[u][i]]|=en[fail[tr[u][i]]];
			else tr[u][i]=tr[fail[u]][i];
		}
	}
}
int dfs(int pos,int p,bool limit,bool zero){
	if(en[p]) return 0;
	if(!pos) return !zero;
	if(!limit&&!zero&&~f[pos][p]) return f[pos][p];
	int rig=limit?a[pos]:9;
	int ans=0;
	for(int i=0;i<=rig;i++){
		int tzero=zero&&!i;
		ans=(ans+dfs(pos-1,tzero?0:tr[p][i],limit&&i==rig,tzero))%mod;
	}
	if(!limit&&!zero) f[pos][p]=ans;
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>s>>m;
	for(int i=1;i<=m;i++){
		cin>>t;
		ins(t);
	}
	get_fail();
	memset(f,-1,sizeof f);
	n=s.size();
	for(int i=0;i<n;i++) a[n-i]=s[i]-'0';
	cout<<dfs(n,0,1,1)<<"\n";
	return 0;
}

一个问题

好像发现了什么……

题解区有些不用dfs,用数组线性递推答案的写法,可以把\(f\)的第一维滚掉,因为第一维是最外层循环枚举的,且\(f[i]\)只和\(f[i-1]\)有关;然而dfs写法应该是滚不掉的,因为一次跑到底,那么每个\(f[i]\)都存在有用的值,所以不能滚。

解决数位dp一般首选dfs,但上面的空间问题,难道是dfs写法的一个弊端吗?能否解决这个问题?

想到了bfs之类的解决方案,但是还没梳理出头绪,网上也貌似完全没有提到bfs实现的数位dp。

如果大家有任何想法请发在评论区,谢谢!

标签:int,题解,pos,dfs,SDOI2014,P3311,bool,dp,数位
From: https://www.cnblogs.com/Sinktank/p/18369775

相关文章

  • Prometheus部署以及问题解决
    Prometheus作用:Prometheus监控(PrometheusMonitoring)是一种开源的系统监控和警报工具。它最初由SoundCloud开发并于2012年发布,并在2016年加入了云原生计算基金会(CNCF)。Prometheus监控旨在收集、存储和查询各种指标数据,以帮助用户监视其应用程序和系统的性能和运行状态。部署流......
  • 题解:CF454B Little Pony and Sort by Shift
    题目描述题目传送门给定一个长度为$n$的数组$a$,每次可以将最后一个元素移动到第一个,问:至少需要几次操作,让序列从小到大排好序,若无解输出$-1$。算法1(暴力枚举)不难想到,将最后一个元素拼接在第一个元素之前,就可以实现将链转换成环,再依次遍历在数组$a_i$中长度为$n$的......
  • Postman中Body添加注释后请求报错问题解决【保姆级教程!!!】
    本文介绍关于Postman中Body添加注释后请求报错问题解决方法如:请求返回下述报错操作失败!系统异常,JsonParseException:Unexpectedcharacter(‘/’(code47)):maybea(non-standard)comment?(notrecognizedasonesinceFeature‘ALLOW_COMMENTS’notenabled......
  • P2261 [CQOI2007] 余数求和 题解
    题目传送门思路数学数学非常经典的题目注意到\(k\bmodi=k-\lfloork/i\rfloor*i\)。于是可以对题目进行转化,从求\(G(n,k)=\sum_{i=1}^kn\bmodi\)变为求\(G(n,k)=n\timesk-\sum_{i=1}^n\lfloork/i\rfloor\timesi\),所以仅需求出\(\sum_{i......
  • 题解:AT_jag2016secretspring_b 豪邸と宅配便
    思路设\(T\)为总时间。由于第一次太郎一定会花\(m\)时间到达门口,所以\(t\)要先减去\(m\)。之后太郎就有两种选择在门口等待下一个快递,时间花费为\(a_i-a_{i-1}\)。回书房,学习一会,再拿快递,时间花费为\(2\timesm\)。则最优时间花费为\(\min(2\timesm,a_i-a_{i-1}......
  • 题解:CF362A Two Semiknights Meet
    题意有两个走法为中国象棋象的棋子,棋盘上有一些坏格子,问它们是否可以在好格子相遇。思路则判断两个棋子是否相遇有两个条件是否可以在一个格子相遇。那个格子是否是好格子。先考虑条件\(1\)设第一个棋子的坐标为\(a_x\)和\(a_y\),第二个棋子的坐标为\(b_x\)和\(b_y......
  • NOI2003 逃学的小孩 题解
    NOI2003逃学的小孩题解传送门。题目简述给定一棵树\(T\),需要选择三个点\(A,B,C\),需要从\(C\)走到\(A,B\)​​的最远距离。(第一段题目是在讲剧情吗。。)前置知识图树树的直径思路简述这题在蓝题(提高+/省选-)中还是比较水的^_^来看看样例吧用瞪眼法(——数学......
  • 题解:CF991D Bishwock
    思路考虑贪心。从左往右扫,找到一个就标记一个即可。但是要注意,当遇见这种情况时000000最优的方法是左右各放一个积木,共放入两块。但如果按照刚刚的方法,则有可能会是这样0X0XX0所以在一些地方有多种放法时,应该优先放置开口朝右的积木。ACCode#include<bits/stdc++.h>......
  • 题解:AT_abc365_c [ABC365C] Transportation Expenses
    题意已知\[\sum_{i=1}^{n}\min(x,a_i)\lem\]问\(x\)最大为多少。思路由于答案具有单调性,所以考虑二分答案。但是有一点要注意,当\(\sum_{i=1}^{n}a_i\lem\)时,应该输出infinite。因为此时的\(x\)可以为任意一个数。ACcode#include<bits/stdc++.h>#defineintun......
  • 题解:CF997A Convert to Ones
    题意给定一个长度为\(n\)的01字符串,有以下两种操作:将一个子串翻转,花费\(X\)将一个子串进行取反,花费\(Y\)求把原字符串变为全是\(1\)的字符串的最小代价。思路只有\(2\)操作的情况下贪心策略。考虑到任意范围取反的花费相同,我们可以将相同的部分合并,如下图合并......