POJ 1850 Code POJ 1496 Word Index

mac2022-06-30  124

两个题是一样的,就有一点小小的不同,我会在代码中注释出来。

题目大意:

按照题目描述给出的定义:

a->1,b->2……z->26,ab->27……vwxyz->83681.

合法的字符串序列是每一个小写字母比后一个小写字母ASCII码要大,不合法输出0。

主要思路:

先判断是否合法。

合法后同POJ 3252 一样,要分两部分来处理这个字符串。

第一部分:小于字符串长度的。

假设长度是5。

那么要枚举长度是4,3,2,1,一共有多少的字符串符合要求。

当长度是1的时候,有=26个;

当长度是2的时候,有=;

长度为3有,4 也是这样。

这样第一部分就解决了。

第二部分:等于字符串长度。

第一小部分:对于s【0】。

枚举从a开始到s【0】-1,有多少种字符串符合要求,字符串长度为len-1。

第二小部分:s[1]~s[len-1];

对于每一个s[i]来说,枚举从s[i-1]+1到s[i]-1,有多少种字符串符合要求,字符串长度为len-1-i;

最后输出是总数要加一,因为字符串本身还没被计算。

下面是代码:

#include <stdio.h> #include <string.h> char s[15]; int c[30][30]= {0}; bool check(int len) { for(int i=0; i<len-1; i++) { if(s[i]>=s[i+1]) { return true; } } return false; } int Partone(int len) { int sum=0; for(int i=1; i<len; i++) { sum+=c[26][i]; } return sum; } int Parttwo(int len) { int sum=0; char ch='a'; while(ch<=s[0]-1) { sum+=c['z'-ch][len-1]; ch++; } for(int i=1; i<len; i++) { ch=s[i-1]+1; while(ch<=s[i]-1) { sum+=c['z'-ch][len-1-i]; ch++; } } return sum; } int main() { int i,j,len,sum; for(int i=0; i<=26; i++)//组合数初始化 { for(int j=0; j<=i; j++) { if(!j || i==j)c[i][j]=1; else c[i][j]=c[i-1][j-1]+c[i-1][j]; } } c[0][0]=0; while(scanf("%s",s)!=EOF) { len=strlen(s); sum=0; if(check(len)) { puts("0"); return 0;//1850在这里return 0, 1496在这里是continue。 } sum+=Partone(len);//处理第一部分 sum+=Parttwo(len);//处理第二部分 printf("%d\n",sum+1); } return 0; }

转载于:https://www.cnblogs.com/lin375691011/p/3996720.html

相关资源:JAVA上百实例源码以及开源项目
最新回复(0)