题目:奇数出现偶数次,偶数出现奇数次
光写这个dp数组写的就快睡着了。。。状态0表示这个数字没出现过,1表示出现了奇数次,2表示出现了偶数次。x和y数组统计每个不同的数字出现的次数,简单易懂。可以用三进制来表示状态,我写的与其对比起来就low了好多,效果其实是一样的。最后前导零不要忘记判断。
#includeusing namespace std; typedef long long ll; int t,wei[20]; ll A,B,dp[20][3][3][3][3][3][3][3][3][3][3]; ll dfs(int pos,int x[],int limit,int lead) { int a[11]={0}; for(int i=0;i<=9;i++) if(x[i]) { if(x[i]&1) a[i]=1; else a[i]=2; } if(pos<1) { int flag=1; for(int i=0;i<10;i++) if(a[i]) { if((i%2==1&&a[i]==1)||(i%2==0&&a[i]==2)) { flag=0; break; } } return flag; } if(!limit&&dp[pos][a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]!=-1) return dp[pos][a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]; int up=limit?wei[pos]:9; ll ans=0; int y[11]; memcpy(y,x,sizeof y); for(int i=0;i<=up;i++) { y[i]++; if(lead&&i==0) y[i]--; ans+=dfs(pos-1,y,limit&&i==up,lead&&i==0); y[i]--; if(lead&&i==0) y[i]++; } if(!limit) dp[pos][a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=ans; return ans; } ll solve(ll x) { int len=0,a[11]={0}; while(x) { wei[++len]=x%10; x/=10; } ll ans=dfs(len,a,1,1); return ans; } int main() { memset(dp,-1,sizeof dp); scanf("%d",&t); while(t--) { scanf("%lld%lld",&A,&B); ll ans=solve(B)-solve(A-1); printf("%lld\n",ans); } return 0; }