1.Amount of Degrees（度的数量）
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=35; int f[N][N]; int k,b; void init() { f[0][0]=1;//C00等于1 for(int i=1;i<N;i++) for(int j=0;j<=i;j++) f[i][j]=f[i-1][j]+f[i-1][j-1];//利用杨辉三角来求组合数 } int dp(int n) { if(!n) return 0;//当n等于0时，一种都不符合，所以返回0 vector<int> a; while(n) a.push_back(n%b),n/=b;//否则讲n每一位存进a数组中 int ans=0,last=0;//ans存的是答案，last存的是当前有多少位是1 for(int i=a.size()-1;i>=0;i--)//因为存进去的时候倒叙存，所以枚举倒叙枚举每一位 { int x=a[i];//取出该位 if(x)//因为枚举的是0~x，则该位为0则不枚举 { ans+=f[i][k-last];//当是(0~x)-1时 if(x==1)//假如该位就是1时，则枚举下一位 { last++; if(last>k) break; } else//否则大与1，则直接加上可以为1的情况 { if(k-last-1>=0) ans+=f[i][k-last-1]; break;//下一位也不用看了 } } if(!i&&k==last) ans++;//假如枚举到最后一位，说明n本身也符合，则ans++ } return ans; } int main() { init();//预处理组合数x int x,y; cin>>x>>y>>k>>b; cout<<dp(y)-dp(x-1)<<endl;//求x~y的区间相当于求0~y的减去0~x-的 return 0; }
2 数字游戏
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=35; int f[N][N]; //预处理的i-1也就是下一步，记住不是前一步 void init() { for(int i=0;i<=9;i++) f[0][i]=1;//独自自己一个也是种合法方案 for(int i=1;i<N;i++)//枚举位数，从右往左 for(int j=0;j<=9;j++)//枚举当前位数 for(int k=j;k<=9;k++)//枚举前一位数的可能 f[i][j]+=f[i-1][k]; } int dp(int n) { if(!n) return 1;//当n等于0时，说明这个也是种合法方案 vector<int> a; while(n) a.push_back(n%10),n/=10;//否则讲n每一位存进a数组中 int ans=0,last=0;//ans存的是答案，last存的是当前最大的末尾数 for(int i=a.size()-1;i>=0;i--)//因为存进去的时候倒叙存，所以枚举倒叙枚举每一位，也就是从左往右 { int x=a[i];//取出该位 for(int j=last;j<x;j++) ans+=f[i][j];//当前位要比上一位大才能符合条件 if(x<last) break;//假如x是不满足大于前一位的，右边分支不用枚举了，不符合条件 last=x;//则当前最大数更新为x if(!i) ans++;//假如枚举到最后一位，说明n本身也符合，则ans++ } return ans; } int main() { init();//预处理 int l,r; while(cin>>l>>r) cout<<dp(r)-dp(l-1)<<endl;//求l~r的区间相当于求0~r的减去0~l-1的 return 0; }
3 Windy 数
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=11; int f[N][N]; //预处理的i-1也就是下一步，记住不是前一步 void init() { for(int i=0;i<=9;i++) f[0][i]=1;//独自自己一个也是种合法方案 for(int i=1;i<N;i++)//枚举位数，从右往左 for(int j=0;j<=9;j++)//枚举当前位数 for(int k=0;k<=9;k++)//枚举前一位数的可能 if(abs(j-k)>=2)//假如满足条件 f[i][j]+=f[i-1][k]; } int dp(int n) { if(!n) return 0;//n不可能为0，则返回0 vector<int> a; while(n) a.push_back(n%10),n/=10;//否则讲n每一位存进a数组中 int ans=0,last=-2;//ans存的是答案，last存的是上一位的数，因为要相差大于2，则初始化小于等于-2和大于等于12都可以 for(int i=a.size()-1;i>=0;i--)//因为存进去的时候倒叙存，所以枚举倒叙枚举每一位，也就是从左往右 { int x=a[i];//取出该位 for(int j=i==a.size()-1;j<x;j++)//不枚举第一位为0的情况，避免前导0的情况 if(abs(j-last)>=2)//假如满足条件 ans+=f[i][j]; if(abs(x-last)<2) break;//假如下一位不满足条件，则不用枚举下一位，直接跳出 last=x;//更新上一位为x if(!i) ans++;//假如枚举到最后一位，说明n本身也符合，则ans++ } //特殊处理前导0的情况，也就是前几位为0的情况 for(int i=0;i<a.size()-1;i++)//枚举每个位数 for(int j=1;j<=9;j++)//枚举该位不能为0 ans+=f[i][j]; return ans; } int main() { init();//预处理 int l,r; cin>>l>>r; cout<<dp(r)-dp(l-1)<<endl;//求l~r的区间相当于求0~r的减去0~l-1的 return 0; }
4 数字游戏2
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=35,M=110; int P; int f[N][15][M]; int mod(int a,int b)//因为c++取模会出现负数，这里让模出来是正数 { return (a%b+b)%b; } //预处理的i-1也就是下一步，记住不是前一步 void init() { for(int i=0;i<=9;i++) f[0][i][i%P]=1;//一个数最高位是自己和mod为自己也是合法 for(int i=1;i<N;i++)//枚举位数，从右往左 for(int j=0;j<=9;j++)//枚举第i位的最高位 for(int k=0;k<P;k++)//枚举第i位模出来的可能 for(int x=0;x<=9;x++)//枚举i-1位的最高位 f[i][j][k]+=f[i-1][x][mod(k-j,P)];//状态计算 } int dp(int n) { if(!n) return 1;//0模任何数都为0，也是一种合法方案 vector<int> a; while(n) a.push_back(n%10),n/=10;//否则讲n每一位存进a数组中 int ans=0,last=0;//ans存的是答案，last存的是枚举过的位数的最高位数和 for(int i=a.size()-1;i>=0;i--)//因为存进去的时候倒叙存，所以枚举倒叙枚举每一位，也就是从左往右 { int x=a[i];//取出该位 for(int j=0;j<x;j++)//枚举0~x的情况 ans+=f[i][j][mod(-last,P)];//这里表示前面枚举过的数的mod last+=x;//更新枚举过的最高数和 if(!i&&last%P==0) ans++;//假如枚举到最后一位，说明n本身也符合，则ans++ } return ans; } int main() { int l,r; while(cin>>l>>r>>P) { memset(f,0,sizeof f);//清空上一层 init();//预处理 cout<<dp(r)-dp(l-1)<<endl;//求l~r的区间相当于求0~r的减去0~l-1的 } return 0; }
5 不要62
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=10; int f[N][N]; //预处理的i-1也就是下一步，记住不是前一步 void init() { for(int i=0;i<=9;i++)//只有一位数的时候都满足，除了4自己 if(i!=4) f[0][i]=1; for(int i=1;i<N;i++)//枚举位数，从右往左 for(int j=0;j<=9;j++)//枚举第i位的最高位 if(j!=4)//假如不是4 for(int k=0;k<=9;k++)//枚举下一位 { if(k==4||j==6&&k==2) continue;//假如不满足条件 f[i][j]+=f[i-1][k];//否则加上这个方案数 } } int dp(int n) { if(!n) return 1;//0也是一种合法方案 vector<int> a; while(n) a.push_back(n%10),n/=10;//否则讲n每一位存进a数组中 int ans=0,last=0;//ans存的是答案，last存的是上一位的最高数 for(int i=a.size()-1;i>=0;i--)//因为存进去的时候倒叙存，所以枚举倒叙枚举每一位，也就是从左往右 { int x=a[i];//取出该位 for(int j=0;j<x;j++)//枚举0~x的情况 { if(j==4||last==6&&j==2) continue;//假如不满足条件 ans+=f[i][j]; } if(x==4||last==6&&x==2) break;//假如最高位是4，或者上一位最高数是6当前位是2则直接跳出 last=x;//更新上一位的最高数 if(!i&&x!=4) ans++;//假如枚举到最后一位并且最后一位不是4，则n本身也符合 } return ans; } int main() { int l,r; init();//预处理 while(cin>>l>>r,l||r) cout<<dp(r)-dp(l-1)<<endl;//求l~r的区间相当于求0~r的减去0~l-1的 return 0; }
