SCUT - 289 - 小O的数字 - 数位dp

秒速五厘米 2021-12-09 05:07 253阅读 0赞

[https://scut.online/p/289][https_scut.online_p_289]  
一个水到飞起的模板数位dp。

#include<bits/stdc++.h> using namespace std; typedef long long ll; bool notp[2000]; const int MAXS1=200; const int MAXS2=2000; int a[20]; ll dp[20][MAXS1][MAXS2]; ll dfs(int pos,int s1,int s2,bool lead,bool limit) { if(pos==-1) { if(notp[s1]||notp[s2]) return 0; else return 1; } if(!limit && !lead && dp[pos][s1][s2]!=-1) return dp[pos][s1][s2]; int up=limit?a[pos]:9; ll ans=0; for(int i=0; i<=up; i++) { ans+=dfs(pos-1,s1+i,s2+i*i,lead && i==0,limit && i==a[pos]); } if(!limit && !lead) dp[pos][s1][s2]=ans; return ans; } ll solve(ll x) { if(x<=0) return 0; int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,0,0,true,true); } int main() { #ifdef Yinku freopen("Yinku.in","r",stdin); #endif // Yinku memset(dp,-1,sizeof(dp)); notp[0]=1; notp[1]=1; for(int i=2; i<2000; i++) { if(!notp[i]) { for(int j=i+i; j<2000; j+=i) { notp[j]=1; } } } int T; scanf("%d",&T); ll le,ri; while(T--) { scanf("%lld%lld",&le,&ri); printf("%lld\n",solve(ri)-solve(le-1)); } }

转载于:https://www.cnblogs.com/Yinku/p/11029378.html

[https_scut.online_p_289]: https://scut.online/p/289

发表评论取消回复

表情：

评论列表（有 0 条评论，253人围观）

还没有评论，来说两句吧...

相关阅读

相关数位dp小结

数位dp小结关于limit的问题在数位dp中,limit的作用主要有两个。控制枚举的界限，倘若没有界限，每一位的枚举范围都是0-9. 但如果有界限，

桃扇骨/ 2023年07月03日 07:22/ 0 赞/ 35 阅读

相关 1084 数字游戏 II（数位dp）

1. 问题描述：由于科协里最近真的很流行数字游戏。某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N 为 0。现在大家又要玩游戏了，指定一个整数闭区间 \[a

我会带着你远行/ 2022年09月14日 09:13/ 0 赞/ 194 阅读

相关 1082 数字游戏（数位dp）

1. 问题描述：科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间

绝地灬酷狼/ 2022年09月14日 08:39/ 0 赞/ 153 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 241 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 219 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 329 阅读

相关【数位DP】C~K的幸运数字

Think: 1知识点：数位DP+记忆化搜索 2思考：（1）：dp数组记录状态应记录\[数位\]\[是否已经含有47\]\[前一位数值\] （2）：dp数组初

淡淡的烟草味﹌/ 2022年06月08日 09:06/ 0 赞/ 186 阅读

相关 SCUT - 289 - 小O的数字 - 数位dp

[https://scut.online/p/289][https_scut.online_p_289] 一个水到飞起的模板数位dp。 include<bits/

秒速五厘米/ 2021年12月09日 05:07/ 0 赞/ 254 阅读

相关数位DP JZOJ 3316. 非回文数字

题目 Description 如果一个字符串从后往前读与从前往后读一致，我们则称之为回文字符串。当一个数字不包含长度大于1的子回文数字时称为非回文数字。例如，162

r囧r小猫/ 2021年11月30日 00:58/ 0 赞/ 282 阅读

相关 ZJOI2010数字计数-数位DP

ZJOI2010数字计数 [题目传送][Link 1] sol: 仍然可以按照记忆化实现的思路来解决此题。 \\(pos,lim,lead\\)的含义不再申明，不了

系统管理员/ 2021年11月22日 17:08/ 0 赞/ 265 阅读