admin 管理员组

文章数量: 1184232

spoj 10606 Balanced Numbers 11维数位dp,状压,奇观

文章目录

    • 题意
      • 奇观!$11$维数位$dp$!

题意

求[l,r]区间内所有奇数数字都出现了偶数次,偶数都出现了奇数次的数字个数.没有出现过的数字不算.

奇观! 11 11 11维数位 d p dp dp!

本来这题可以用状压写的.不过我为了观赏效果开了 11 11 11维的 d p dp dp数组.
令 d p [ n o w ] [ c 0 ] [ c 1 ] [ c 2 ] [ c 3 ] [ c 4 ] [ c 5 ] [ c 6 ] [ c 7 ] [ c 8 ] [ c 9 ] dp[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9] dp[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9]表示处理到第 n o w now now位,对于 0 → 9 0\to9 0→9来说, 2 2 2表示没有出现过, 1 1 1表示出现奇数次, 0 0 0表示出现偶数次的数字个数.
因为数据范围 1 0 19 10^{19} 1019,我自己认为要开unsigned long long.
不过这代码跑得倒是快,0ms就过去了.

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){int x=0,f=1;char c=gc();for (;!isdigit(c);c=gc()) f^=c=='-';for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');return f?x:-x;}
template <typename mitsuha>
inline bool read(mitsuha &x){x=0;int f=1;char c=gc();for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';if (!~c) return 0;for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');return x=f?x:-x,1;}
template <typename mitsuha>
inline int write(mitsuha x){if (!x) return 0&pc(48);if (x<0) x=-x,pc('-');int bit[20],i,p=0;for (;x;x/=10) bit[++p]=x%10;for (i=p;i;--i) pc(bit[i]+48);return 0;}
inline char fuhao(){char c=gc();for (;isspace(c);c=gc());return c;}
}using namespace chtholly;
using namespace std;
typedef unsigned long long ull;
ull dp[50][3][3][3][3][3][3][3][3][3][3]; // 规模看起来十分庞大的dp数组
int bit[50];ull dfs(int now,int c0,int c1,int c2,int c3,int c4,int c5,int c6,int c7,int c8,int c9,int lim,int lz){ // 当前枚举到的位置,0-9的个数,是否有最大位限制,否是有前导0.
if (!now) return c0&&c1^1&&c2&&c3^1&&c4&&c5^1&&c6&&c7^1&&c8&&c9^1; // 当枚举到最后的时候判断偶数出现奇数次,也就是相对应的c不为0,奇数相对应的c不为1. 
if (!lim&&lz&&~dp[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9]) return dp[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9];
ull llx=0; int i,da=lim?bit[now]:9;
for (i=0;i<=da;++i){ // 对于当前位枚举的每一个数都特判.switch(i){case 0: llx+=dfs(now-1,lz?c0==2?1:!c0:c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,lim&&i==da,lz); break; /*只有判0的时候需要注意前导0,其他数都没什么区别.*/case 1: llx+=dfs(now-1,c0,c1==2?1:!c1,c2,c3,c4,c5,c6,c7,c8,c9,lim&&i==da,1); break;case 2: llx+=dfs(now-1,c0,c1,c2==2?1:!c2,c3,c4,c5,c6,c7,c8,c9,lim&&i==da,1); break;case 3: llx+=dfs(now-1,c0,c1,c2,c3==2?1:!c3,c4,c5,c6,c7,c8,c9,lim&&i==da,1); break;case 4: llx+=dfs(now-1,c0,c1,c2,c3,c4==2?1:!c4,c5,c6,c7,c8,c9,lim&&i==da,1); break;case 5: llx+=dfs(now-1,c0,c1,c2,c3,c4,c5==2?1:!c5,c6,c7,c8,c9,lim&&i==da,1); break;case 6: llx+=dfs(now-1,c0,c1,c2,c3,c4,c5,c6==2?1:!c6,c7,c8,c9,lim&&i==da,1); break;case 7: llx+=dfs(now-1,c0,c1,c2,c3,c4,c5,c6,c7==2?1:!c7,c8,c9,lim&&i==da,1); break;case 8: llx+=dfs(now-1,c0,c1,c2,c3,c4,c5,c6,c7,c8==2?1:!c8,c9,lim&&i==da,1); break;case 9: llx+=dfs(now-1,c0,c1,c2,c3,c4,c5,c6,c7,c8,c9==2?1:!c9,lim&&i==da,1); break;}}
/*当前枚举的数的cnt为2,变成1;否则变成!cnt,即奇数变偶数,偶数变奇数.*/
return lim?llx:dp[now][c0][c1][c2][c3][c4][c5][c6][c7][c8][c9]=llx;
}ull get(ull x){
for (*bit=0;x;x/=10) bit[++*bit]=x%10;
return dfs(*bit,2,2,2,2,2,2,2,2,2,2,1,0);
}int main(){
memset(dp,-1,sizeof dp);
for (int t=read();t--;){ull l,r; read(l),read(r);write(get(r)-get(l-1)),pl;}
}

本文标签： spoj 10606 Balanced Numbers 11维数位dp 状压 奇观

版权声明：本文标题：spoj 10606 Balanced Numbers 11维数位dp,状压,奇观 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1698538268a307435.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。