poj 1850 1019 （简单位数dp）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[27][11],l,ans;
char s[11];
void Get_f()
{
    for(int i=1;i<=26;i++)
      f[i][1]=1;
    for(int j=2;j<=10;j++)
      for(int i=1;i<=26;i++)
        for(int k=i+1;k<=26;k++)
          f[i][j]+=f[k][j-1];
}
int main()
{
    scanf("%s",s+1);
    l=strlen(s+1);s[0]=96;
    for(int i=2;i<=l;i++)
      if(s[i]<=s[i-1])
        {
          printf("0
");
          return 0;
        }
    Get_f();
    for(int i=1;i<=26;i++)
      for(int j=1;j<l;j++)
        ans+=f[i][j];
    for(int i=1;i<=l;i++)
      for(int j=s[i-1]-95;j<s[i]-96;j++)
         ans+=f[j][l+1-i];
    printf("%d
",ans+1);
    return 0;
 }

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int T,n;
long long s[maxn+10],a[maxn+10];
void Get_sa()
{
    for(int i=1;i<=maxn;i++)
      {
          int t=i,l=0;
          while(t)l++,t/=10;
          a[i]=a[i-1]+l;
          s[i]=s[i-1]+a[i];
      }
}
int main()
{
    Get_sa();
    scanf("%d",&T);
    while(T--)
      {
          scanf("%d",&n);
          int i=1;
          while(n>s[i])i++;
          n-=s[i-1];i=1;
          while(n>a[i])i++;
          n-=a[i-1];
          int data[10],l=0;
          memset(data,0,sizeof(data));
          while(i)
            {
                data[++l]=i%10;
                i=i/10;
          }
        printf("%d
",data[l-n+1]);
      }
    return 0;
}