找规律是最强的
本蒟蒻不会数位DP，不会数学方法，决定重拾起自己小学时学习的——找规律！！！
先上结构体：
struct Count{ int a[10]; Count operator + (const Count x) const { Count ans; memset(ans.a,0,sizeof(ans.a)); for(int i=0;i<10;++i) { ans.a[i]=a[i]+x.a[i]; } return ans; } Count operator - (const Count x) const//重载运算符 { Count ans; memset(ans.a,0,sizeof(ans.a)); for(int i=0;i<10;++i) { ans.a[i]=a[i]-x.a[i]; } return ans; }};
首先我们需要一个暴力，以便寻找规律：
#include#include using namespace std;#define ll long long ll n,ans[10];void work(ll a){ while(a>0){ ans[a%10]++; a/=10; }}int main(void){ scanf("%lld",&n); for(ll i=1;i<=n;i++){ work(i); } for(ll i=0;i<=9;i++){ printf("%lld\n",ans[i]); }}
接下来请跟我在程序里输入几个数
"9,19,29,99,199,299"
答案如下：
" 9: 0 1 1 1 1 1 1 1 1 1"" 19: 1 12 2 2 2 2 2 2 2 2"" 29: 2 13 13 3 3 3 3 3 3 3"" 99: 9 20 20 20 20 20 20 20 20 20""199:29 140 40 40 40 40 40 40 40 40""299:49 160 160 60 60 60 60 60 60 60"
有没有发现：
9到19，1多了11个，而其他的多了1个
19到29，2多了11个，而其他的多了1个
99到199，1多了120个，而其他的多了20个
199到299,2多了120个，而其他的多了20个
如果在多试几组的话更明显，但本蒟蒻先将规律写出：
//对于任意一个：a*10^(l-1)-1;//l即位数//其每一种数字加上：pow(10,l-2)*(l-1);//每一位上加的//其首位a的种类额外加上：pow(10,l-1);int len(int x)//计算位数{ int k=0; while(x>0) { ++k; x/=10; } return k;}int plus(int x)//计算每一个a*10^(l-1)-1到下一个同样满足要求的所要加上的值{ int lx=len(x),llx=len(x+1); if(lx!=llx) { return p[lx]; } return p[lx-1];}//main函数分隔线p[0]=1;p[1]=1;//千万别用pow，不稳定for(int i=2;i<=len(n);++i){ p[i]=p[i-1]*10; for(int j=0;j<10;++j) { s[i].a[j]=p[i-2]*(i-1);//计算每一位需要加上的值 }}int l=9,li;for(int i=19;i<=n;i+=plus(i)){ li=len(i); ans=ans+s[li]; ans.a[i/p[li-1]]+=p[li-1];//计算a额外加上的值 l=i;//下文提到的记录运行位置的变量}
然后，因为题目不可能直接给我们特殊的n，所以我们需要一个变量记录我们运行到了那里，然后用暴力弥补与n之间的差距。
这里有一个小优化，就是可以比较到底是当前运行到的i接近呢，还是下一个i接近？以减少运行次数。
Count each(int x)//暴力程序{ Count ans; memset(ans.a,0,sizeof(ans.a)); while(x>0) { ++ans.a[x%10]; x/=10; } return ans;}//main函数分隔线if(n-l
主要思路到这里就结束了，最后将答案输出就可以AC了（数据太水）
注：细心的oier可能已经发现了，前面的暴力其实是叫帮我写的
附完整代码：
#include#include #define int long longstruct Count{ int a[10]; Count operator + (const Count x) const { Count ans; memset(ans.a,0,sizeof(ans.a)); for(int i=0;i<10;++i) { ans.a[i]=a[i]+x.a[i]; } return ans; } Count operator - (const Count x) const { Count ans; memset(ans.a,0,sizeof(ans.a)); for(int i=0;i<10;++i) { ans.a[i]=a[i]-x.a[i]; } return ans; }};Count each(int x){ Count ans; memset(ans.a,0,sizeof(ans.a)); while(x>0) { ++ans.a[x%10]; x/=10; } return ans;}int len(int x){ int k=0; while(x>0) { ++k; x/=10; } return k;}int n;int p[10];Count s[10];Count ans;int plus(int x){ int lx=len(x),llx=len(x+1); if(lx!=llx) { return p[lx]; } return p[lx-1];}signed main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); scanf("%lld",&n); if(n<=9) { for(int i=1;i<=n;++i) { ans=ans+each(i); } } else { for(int i=1;i<=9;++i) { ans=ans+each(i); } } p[0]=1; p[1]=10; for(int i=2;i<=len(n);++i) { p[i]=p[i-1]*10; for(int j=0;j<10;++j) { s[i].a[j]=p[i-2]*(i-1); } } int l=9,li; for(int i=19;i<=n;i+=plus(i)) { li=len(i); ans=ans+s[li]; ans.a[i/p[li-1]]+=p[li-1]; l=i; } if(n-l
2018-10-01