[关闭]
@Jerusalem 2016-02-14T05:09:40.000000Z 字数 1372 阅读 948

Vol4


ZJOI2010 count
BZOJ1833

定义,代表长为i,开头为j,digit k能出现多少次 。

这可以轻易地被DP出来。

接下来,我们要求的digit出现数量。

很明显,可以将位数不足n的数全部用预处理出来,接下来的可以视为前缀唯一。可以容易地递推出来。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. typedef long long ll;
  8. using namespace std;
  9. struct Data{
  10. ll ans[10];
  11. Data(){
  12. memset(ans,0,sizeof(ans));
  13. }
  14. };
  15. Data operator +(const Data& a,const Data& b)
  16. {
  17. Data t;
  18. for(int i=0;i<=9;i++)
  19. t.ans[i]=a.ans[i]+b.ans[i];
  20. return t;
  21. }
  22. ll l,r;
  23. ll ten[20];
  24. Data f[20][15]; //f[i][j].ans[k]:长为i,开头为j,digit k能出现多少次
  25. void GetPerDigit(ll u,int* dig)
  26. {
  27. dig[0]=0;
  28. while(u>0){
  29. dig[++dig[0]]=u%10;
  30. u/=10;
  31. }
  32. }
  33. Data Calc(ll u)
  34. {
  35. int dig[20];
  36. Data ans;
  37. if(u==0)
  38. return ans;
  39. GetPerDigit(u,dig);
  40. for(int i=1;i<dig[0];i++)
  41. for(int j=1;j<=9;j++)
  42. ans=ans+f[i][j];
  43. for(int i=1;i<dig[dig[0]];i++)
  44. ans=ans+f[dig[0]][i];
  45. ans.ans[dig[dig[0]]]+=(u%ten[dig[0]-1])+1;
  46. for(int i=dig[0]-1;i>=1;i--){
  47. for(int j=0;j<dig[i];j++)
  48. ans=ans+f[i][j];
  49. ans.ans[dig[i]]+=(u%ten[i-1])+1;
  50. }
  51. return ans;
  52. }
  53. void Solve()
  54. {
  55. Data ans1=Calc(l-1),ans2=Calc(r);
  56. for(int i=0;i<=8;i++)
  57. cout<<ans2.ans[i]-ans1.ans[i]<<" ";
  58. cout<<ans2.ans[9]-ans1.ans[9];
  59. }
  60. void First()
  61. {
  62. ten[0]=1;
  63. for(int i=1;i<=12;i++)
  64. ten[i]=ten[i-1]*10;
  65. for(int i=0;i<=9;i++)
  66. f[1][i].ans[i]=1;
  67. for(int i=2;i<=12;i++)
  68. for(int j=0;j<=9;j++){
  69. f[i][j].ans[j]=ten[i-1];
  70. for(int k=0;k<=9;k++)
  71. f[i][j]=f[i][j]+f[i-1][k];
  72. }
  73. }
  74. void ReadData()
  75. {
  76. cin>>l>>r;
  77. }
  78. void Close()
  79. {
  80. fclose(stdin);
  81. }
  82. int main()
  83. {
  84. ReadData();
  85. First();
  86. Solve();
  87. Close();
  88. return 0;
  89. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注