題意
一個數被稱為是平衡的數當且僅當對于所有出現過的數位,偶數出現奇數次,奇數出現偶數次。給定A,B,請統計出[A,B]内所有平衡數的個數。
1<=A<=B<=10^19
題解
一開始沒看懂題,把奇數看成整體,偶數看成整體了。
後來看了題解才知道是0,1,2....這些數如果出現就要滿足條件。
當然最莽夫的方法就是把每一個數都開一維。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
int t;
ll l,r;
int len,num[25],pos[15];
ll f[20][2][3][3][3][3][3][3][3][3][3][3];
ll dfs(int s,bool qdl,bool lim,int pos0,int pos1,int pos2,int pos3,int pos4,int pos5,int pos6,int pos7,int pos8,int pos9){
if(!s) return pos0&&pos1^1&&pos2&&pos3^1&&pos4&&pos5^1&&pos6&&pos7^1&&pos8&&pos9^1;
if(!lim&&f[s][qdl][pos0][pos1][pos2][pos3][pos4][pos5][pos6][pos7][pos8][pos9]!=-1)
return f[s][qdl][pos0][pos1][pos2][pos3][pos4][pos5][pos6][pos7][pos8][pos9];
int mx=lim ? num[s] : 9 ;
ll ret=0;
for (int i=0;i<=mx;++i){
switch(i){
case 0: ret+=dfs(s-1,qdl,lim&&i==mx,qdl ? pos0 : pos0==2 ? 1 : !pos0,pos1,pos2,pos3,pos4,pos5,pos6,pos7,pos8,pos9); break;
case 1: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1==2?1:!pos1,pos2,pos3,pos4,pos5,pos6,pos7,pos8,pos9); break;
case 2: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2==2?1:!pos2,pos3,pos4,pos5,pos6,pos7,pos8,pos9); break;
case 3: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2,pos3==2?1:!pos3,pos4,pos5,pos6,pos7,pos8,pos9); break;
case 4: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2,pos3,pos4==2?1:!pos4,pos5,pos6,pos7,pos8,pos9); break;
case 5: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2,pos3,pos4,pos5==2?1:!pos5,pos6,pos7,pos8,pos9); break;
case 6: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2,pos3,pos4,pos5,pos6==2?1:!pos6,pos7,pos8,pos9); break;
case 7: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2,pos3,pos4,pos5,pos6,pos7==2?1:!pos7,pos8,pos9); break;
case 8: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2,pos3,pos4,pos5,pos6,pos7,pos8==2?1:!pos8,pos9); break;
case 9: ret+=dfs(s-1,false,lim&&i==mx,pos0,pos1,pos2,pos3,pos4,pos5,pos6,pos7,pos8,pos9==2?1:!pos9); break;
}
}
if(!lim) f[s][qdl][pos0][pos1][pos2][pos3][pos4][pos5][pos6][pos7][pos8][pos9]=ret;
return ret;
}
ll cx(ll x){
len=0;
while(x){
num[++len]=x%10;
x/=10;
}
return dfs(len,true,true,2,2,2,2,2,2,2,2,2,2);
}
int main(){
memset(f,-1,sizeof(f));
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&l,&r);
printf("%lld\n",cx(r)-cx(l-1));
}
}
View Code
這種寫法還挺好看,就是有點長。
最後的判斷如果是2的話會滿足條件是以可以。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
int t;
ll l,r;
int len,num[25],pos[15];
ll f[20][2][3][3][3][3][3][3][3][3][3][3];
ll dfs(int s,bool qdl,bool lim,int pos0,int pos1,int pos2,int pos3,int pos4,int pos5,int pos6,int pos7,int pos8,int pos9){
if(!s) return pos0&&pos1^1&&pos2&&pos3^1&&pos4&&pos5^1&&pos6&&pos7^1&&pos8&&pos9^1;
if(!lim&&f[s][qdl][pos0][pos1][pos2][pos3][pos4][pos5][pos6][pos7][pos8][pos9]!=-1)
return f[s][qdl][pos0][pos1][pos2][pos3][pos4][pos5][pos6][pos7][pos8][pos9];
int mx=lim ? num[s] : 9 ;
ll ret=0;
for (int i=0;i<=mx;++i)
ret+=dfs(s-1,qdl&&!i,lim&&i==mx,!i&&!qdl?(pos0+1)&1:pos0,i==1?(pos1+1)&1:pos1,i==2?(pos2+1)&1:pos2,i==3?(pos3+1)&1:pos3,i==4?(pos4+1)&1:pos4,i==5?(pos5+1)&1:pos5,i==6?(pos6+1)&1:pos6,i==7?(pos7+1)&1:pos7,i==8?(pos8+1)&1:pos8,i==9?(pos9+1)&1:pos9);
if(!lim) f[s][qdl][pos0][pos1][pos2][pos3][pos4][pos5][pos6][pos7][pos8][pos9]=ret;
return ret;
}
ll cx(ll x){
len=0;
while(x){
num[++len]=x%10;
x/=10;
}
return dfs(len,true,true,2,2,2,2,2,2,2,2,2,2);
}
int main(){
memset(f,-1,sizeof(f));
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&l,&r);
printf("%lld\n",cx(r)-cx(l-1));
}
}
View Code
還可以弄成一行。
正解好像是弄三進制狀壓
轉載于:https://www.cnblogs.com/sto324/p/11391331.html