主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
P3413 SAC#1-萌数
最后更新于 2025-07-31 14:53:43
作者
whg_IOI
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
洛谷P3413 SAC#1-萌数 题解 前言 本题并不难,同为数位DP板子题,可细节较多,需耐心分析,所以子标题也会分得较细(有些与上题重复,将不再赘述) 题目分析 我们首先看一眼数据范围,就会发现r最大能取到$n^{1000}$,这显然是暴力无法承受的,这是我们又发现这题是按位分析的,所以考虑数位```DP```(跟上题差不多) 输入 我们注意到这题的```r```的范围,显然即使是```unsigned long long```也无法承受,这时我们考虑```string```的读入 这里需要注意的是,因为我们背的板子是倒序遍历,所以我们在初始化时要倒序记录 初始化 与上一题几乎一模一样,可是当我用上一题的方法写时发现TLE了,所以我采取了优化措施 ```res+=dfs(cnt-1,i,10,false,i==num[cnt]);``` 这里与上一题不同的是我们将```i<num[cnt]```改成了```i==num[cnt]```这样可以减少时间复杂度,虽然我也不知道为什么,逻辑与之前一样 这里```b```初始化为10是怕之后的判断将未遍历的数和前导0弄混,所以不设-1,设10,当然,0~9更不行,因为要不然它会将这个看成已经遍历的数拿来判断 记忆化搜索 设计状态 与上题基本一致 ```p``` 是第```p```位 ```a ```第```p+1```位是什么 ```b ```第```p+2```位是什么 ```c ```之前是否已经回文 ```d``` ```limit```是否能取到9(等于0时可以,等于1时不行,这里不解释了,之前已经解释过了) 考虑边界 1. 显然,当```p```遍历完时就结束了,可以直接返回```c```作为答案 2. 3. 如果```dp[p][a][b][c][d]```已经遍历过了,且```d==0```,就可以回溯了,如果不加```d==0```,会导致答案出错 考虑```p+1```位的枚举上限 因为加了优化,需将上题的```d==true```改成```d==false```,其他不变 考虑转移 与上题类似,只需将```c```与```d```改变一下就可以了,这里我搞错了,当时想法:但是```c```这里要格外注意,因为有时我们会判断```aba```型的回文串,将调用到```p+2```位,可是初始化时我们初始化的是10,也就是前导0,而前导0不能算在判断中,所以我们需要加上```b!=10```这一限制。现在再一想,因为```limit```最多取到9,可我们前导0赋的值是10,所以绝对不可能相等。 状态转移 ``` for(int i=0;i<=limit;++i){ bool new_c=c||i==a||i==b; res+=dfs(p-1,i,a,new_c,d&&(i==limit)); res%=MOD; } ``` 这里```res```取模是怕```res```过大,超出```long long```限制 考虑返回 这里加了优化,所以返回值为 ``` if(!d)dp[p][a][b][c][d]=res; return res; ``` 结尾特判 因为输入用的是字符串处理,所以无法实现```ans(r)-ans(l-1)```只能实现```ans(r)-ans(l)```,这也就意味着l没有被算进去,所以我们要判断l本身是不是回文串,是的化```answer```就要加一,最后别忘了取模 优化总结 1 将初始化时的```i<num[cnt]```,改为```i==num[cnt]``` 2 将记忆化转移```if(dp[p][a][b][c][d]!=-1)return dp[p][a][b][c][d];```改为```if(!d&&dp[p][a][b][c][d]!=-1)return dp[p][a][b][c][d];``` 3 将判断时 ``` if(d==1){ limit=9; }else limit=num[p]; ``` 改为 ``` if(d==0){ limit=9; }else limit=num[p]; ``` 4 将转移时```res+=dfs(p-1,i,a,new_c,d||(i<limit));```改为```res+=dfs(p-1,i,a,new_c,d&&(i==limit));``` 5 将回溯时```return dp[p][a][b][c][d]=res;```改为```if(!d)dp[p][a][b][c][d]=res;return res;``` 附上代码 ``` #include<bits/stdc++.h> using namespace std; const int MOD=1000000007; string s,s1; int cnt,dp[1001][11][11][2][2],num[1005]; long long dfs(int p/*第p位*/,int a/*p+1位*/,int b/*p+2位*/,bool c/*回文*/,bool d/*是否取9*/){ if(p<=0)return c; if(!d&&dp[p][a][b][c][d]!=-1)return dp[p][a][b][c][d]; int limit=0; if(d==0){ limit=9; }else limit=num[p]; long long res=0; for(int i=0;i<=limit;++i){ bool new_c=c||i==a||i==b; res+=dfs(p-1,i,a,new_c,d&&(i==limit)); res%=MOD; } if(!d)dp[p][a][b][c][d]=res; return res; } long long ans(string s){ cnt=s.length(); memset(dp,-1,sizeof(dp)); for(int i=0;i<s.length();++i){ num[cnt-i]=s[i]-'0'; } long long res=0; for(int i=1;i<=num[cnt];++i){ res+=dfs(cnt-1,i,10,false,i==num[cnt]); res%=MOD; } return res; } bool meng(string s){ for(int i=0;i<s.length()-1;++i){ if(s[i]==s[i+1])return true; if(i<s.length()-2&&s[i]==s[i+2])return true; } return false; } int main(){ cin>>s>>s1; long long ans_1=ans(s1); long long ans_2=ans(s); long long answer=(ans_1-ans_2+meng(s)+MOD)%MOD; printf("%lld",answer); return 0; } ```
正在渲染内容...
点赞
1
收藏
0