Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

以前看过,数去数来总算数出了思路

Posted by OSJake at 2009-09-05 19:09:10 on Problem 1496
#include<stdio.h>
#include<string.h>
#include<memory.h>
long f[26][6];
long g[5];
void INIT()
{
     memset(f,0,sizeof(f));
     memset(g,0,sizeof(g));
     int i,j,k;
     for(i=0;i<26;i++)
         f[i][1]=1;
     g[1]=26;
     for(k=2;k<6;k++)
     for(i=0;i<26;i++)
     {
                      for(j=i+1;j<26;j++)
                       f[i][k]+=f[j][k-1];
                       }
     for(i=2;i<5;i++)
     for(j=0;j<26;j++)
     g[i]+=f[j][i];
}
bool check(char data[])
{
     int len=strlen(data);
     int i,j;
     for(i=0;i<len;i++)
     {
                       for(j=i+1;j<len;j++)
                       if(data[i]>=data[j])return false;
                       }
     return true;
}
int ans(char data[])
{
    int len=strlen(data);
    int i,j;
    int sum=0;
    int p;
    for(i=1;i<len;i++)
    sum+=g[i];
    sum++;
    for(i=0;i<len;i++)
    {
                      p=len-i;
                      if(i==0)
                      {
                             for(j=0;j<data[i]-'a';j++)
                             sum+=f[j][p];
                              }
                      else
                      {
                         for(j=data[i-1]-'a'+1;j<data[i]-'a';j++)
                         sum+=f[j][p];
                          }
                          }
    return sum;
}
int main()
{
    char data[6];
    INIT();
    while(scanf("%s",&data)!=EOF)
    {
                                 if(!check(data))
                                 printf("0\n");
                                 else
                                 {
                                     printf("%d\n",ans(data));
                                     }
                                     }
    return 0;
    
}
        

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator