Salazar Slytherin's Locket CodeForces…
2018-06-17 21:50:41来源:未知 阅读 ()
Salazar Slytherin's Locket CodeForces - 855E
http://www.cnblogs.com/ftae/p/7590187.html
数位dp:
http://www.cnblogs.com/xz816111/p/4809913.html
http://blog.csdn.net/wust_zzwh/article/details/52100392
1.
1 #include<cstdio> 2 #include<cstring> 3 typedef long long LL; 4 LL q,b,l,r; 5 LL ans[11][70][2049][2]; 6 LL w[70];//记录拆出来的i进制的各个数字 7 //ans[i][j][state][k]:i进制,i进制下j长度,状态为state,k表示是否处于前导0 8 //状态为0-b-1的数字出现奇数/偶数次 9 LL dp(LL jz,LL pos,LL state,bool pre0,bool limit)//pre0表示当前位的前一位是不是0 10 { 11 if(pos<1) return !state;//只有状态全0也就是所有数字出现偶数次才有1个答案,曾经忘记 12 if(!limit&&ans[jz][pos][state][pre0]!=-1) 13 return ans[jz][pos][state][pre0]; 14 LL i,res=0,end=limit?w[pos]:(jz-1);//当前位上界,limit为0表示前面某一位已经取了不是最高值,那么后面的位可以取0-9//曾经把最大值错写成9 15 for(i=0;i<=end;i++) 16 if(i==0&&pre0)//如果当前位取0,且前面都是前导0,那么开头的0显然是不计入状态的 17 res+=dp(jz,pos-1,state,1,limit&&i==w[pos]);//曾经忘记写limit&& 18 else 19 res+=dp(jz,pos-1,state^(1<<i),0,limit&&i==w[pos]); 20 return limit?res:(ans[jz][pos][state][pre0]=res); 21 } 22 LL get(LL b,LL x) 23 { 24 LL g; 25 for(g=0;x>0;x/=b) w[++g]=x%b; 26 return dp(b,g,0,1,1);//这一种的返回的直接就是1-x的总答案 27 } 28 int main() 29 { 30 memset(ans,-1,sizeof(ans)); 31 scanf("%I64d",&q); 32 while(q--) 33 { 34 scanf("%I64d%I64d%I64d",&b,&l,&r); 35 printf("%I64d\n",get(b,r)-get(b,l-1)); 36 } 37 return 0; 38 }
2.
1 #include<cstdio> 2 #include<cstring> 3 typedef long long LL; 4 LL q,b,l,r; 5 LL ans[11][70][2049]; 6 LL w[70]; 7 //ans[i][j][state][k]:i进制,i进制下j长度,状态为state,k表示是否处于前导0 8 //状态为0-b-1的数字出现奇数/偶数次 9 LL dp(LL jz,LL pos,LL state,bool pre0,bool limit)//pre0表示当前位的前一位是不是0 10 { 11 if(pos<1) return !state;//只有状态全0也就是所有数字出现偶数次才有1个答案 12 if(!limit&&!pre0&&ans[jz][pos][state]!=-1) 13 return ans[jz][pos][state]; 14 LL i,res=0,start=pre0?1:0,end=limit?w[pos]:(jz-1);//当前位上界,limit为0表示前面某一位已经取了不是最高值,那么后面的位可以取0-9 15 for(i=start;i<=end;i++) 16 res+=dp(jz,pos-1,state^(1<<i),0,limit&&i==w[pos]); 17 if(!limit&&!pre0) 18 ans[jz][pos][state]=res; 19 return res; 20 } 21 LL get(LL b,LL x) 22 { 23 LL g,i,ret=0; 24 for(g=0;x>0;x/=b) w[++g]=x%b; 25 for(i=g;i>=1;i--) ret+=dp(b,i,0,1,i==g);//如果总位数不到g,那么显然所有数字都可以随便取 26 return ret;//这一种的dp返回的是0(1)-x的数中i位的数满足条件的答案 27 } 28 int main() 29 { 30 memset(ans,-1,sizeof(ans)); 31 scanf("%I64d",&q); 32 while(q--) 33 { 34 scanf("%I64d%I64d%I64d",&b,&l,&r); 35 printf("%I64d\n",get(b,r)-get(b,l-1)); 36 } 37 return 0; 38 }
3.
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- Building & Debugging chromium on CLion for Linu 2020-05-19
- 洛谷P1164->小A点菜 2020-05-18
- 表达式·表达式树·表达式求值 2020-04-29
- STL之<string> 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash