当前位置: 代码迷 >> 综合 >> poj-1850-数学
  详细解决方案

poj-1850-数学

热度:77   发布时间:2023-12-19 11:28:55.0

题意:

给你一串字母,求他们应该是第几位。

a - 1 
b - 2 
... 
z - 26 
ab - 27 
... 
az - 51 
bc - 52 
... 
vwxyz - 83681 

前面的字母一定比后面的字符小。如果比后面的字母大,就输出0;

做法:

定义一个函数f(x,y,z)表示字符串一共有z个长度,第一个字母从x搜到y的结果。

比如对字符串dhw进行分析:

先求出,比def小的所有长度为3字符串的个数即为:f(1,d-1,3);

然后再求出比ef大,比hi小的所有长度为2字符串的个数:f(5,h-1,2);

然后再求出所有比i大,比w小的字符案串个数:f(i,w-1,1);

比dhw小的所有长度为3的字符串的个数即为:x=f(1,d-1,3)+f(5,h-1,2)+f(i,w-1,1);

然后求出所有长度小于3的字符串的个数设为y;

则所有比dhw小的字符串的个数为z=x+y;

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
long long put(int st,int x,int n)
{int i;if(n==1)return x-st+1;long long sum=0;for(i=st;i<=x;i++){sum+=put(i+1,26,n-1);}return sum;
}
int main()
{int n,i;char str[20];gets(str);n=strlen(str);long long sum=0;for(i=0;i<n;i++){if(i==0)sum+=put(1,str[i]-'a',n-i);else{sum+=put(str[i-1]-'a'+1+1,str[i]-'a'+1-1,n-i);if(str[i]<=str[i-1]){printf("0\n");return 0;}}}sum++;for(i=1;i<n;i++){sum+=put(1,26,i);}printf("%lld\n",sum);return 0;
}