题意: 给出求ab之间有多少个平衡数 4139为平衡数 以3为轴 1*1+4*2==9*1
思路很好想但是一直wa :
注意要减去前导零的情况 0 00 000 0000 不能反复计算
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define N 3700+5 #define MID N/2 ll dp[20][20][N]; ll a[20]; ll dfs(int pos,int t,int state,bool lead,bool limit ) { if(!pos)return state==0; if(!limit&&!lead&&dp[pos][t][state+MID]!=-1)return dp[pos][t][state+MID]; ll ans=0; int up=limit?a[pos]:9; rep(i,0,up) { ans+=dfs(pos-1,t,state+i*(pos-t), lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead)dp[pos][t][state+MID]=ans; return ans; } ll solve(ll x) { int pos=0; ll ans=0; while(x) { a[++pos]=x%10; x/=10; } rep(i,1,pos) ans+=dfs(pos,i,0,true,true); return ans-pos+1;//去除前导零 } int main() { int cas; CLR(dp,-1); RI(cas); while(cas--) { ll a,b; cin>>a>>b; printf("%lld\n",solve(b)-solve(a-1)); } return 0; }View Code
或者
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define N 3700+5 #define MID N/2 ll dp[20][20][N]; ll a[20]; ll dfs(int pos,int t,int state,bool lead,bool limit ) { if(!pos)return !lead&&state==0; if(!limit&&!lead&&dp[pos][t][state+MID]!=-1)return dp[pos][t][state+MID]; ll ans=0; int up=limit?a[pos]:9; rep(i,0,up) { ans+=dfs(pos-1,t,state+i*(pos-t), lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead)dp[pos][t][state+MID]=ans; return ans; } ll solve(ll x) { if(x<0)return 0; if(x==0)return 1; int pos=0; ll ans=0; while(x) { a[++pos]=x%10; x/=10; } rep(i,1,pos) ans+=dfs(pos,i,0,true,true); return ans+1;//去除前导零 } int main() { int cas; CLR(dp,-1); RI(cas); while(cas--) { ll a,b; cin>>a>>b; printf("%lld\n",solve(b)-solve(a-1)); } return 0; }View Code