POJ 1850 Code 字符串 难度:1

时间:2023-03-09 18:37:03
POJ 1850 Code 字符串 难度:1

题意:

1 如果是严格升序的字母字符串,那么可以输出非0解码,否则不能译码输出0

2 字符串解码 遵循递增原则,其值为 到现在为止的所有按字母序小于该字符串的数量 + 1;

#include <iostream>

using namespace std;
char ans[11];
int a[10];
int c[27][27];
long long f[10];
void generc(){//生成组合数
for(int i=1;i<27;i++)c[i][0]=c[i][i]=1;
for(int i=2;i<27;i++){
for(int j=1;j<27;j++){
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
}
void generf(){//如果字符串长度为len ,首先统计长度小于len的所有严格升序字符串个数
f[0]=0;
for(int i=1;i<10;i++){
f[i]=f[i-1]+c[26][i];//长度为i 的 字符串中会出现所有字母,且不重复取到i个后有唯一顺序
}
} long long calc(){
int len=0;//记录长度,不想用cstring
for(len=0;len<10;len++){
if(ans[len]==0)break;
a[len]=ans[len]-'a';//习惯处理数字,无关紧要
} int former=0;//记录前一位的值+1,该值将作为下一位所有可能的起点,因为是首位,设存在a[-1]=-1;所以a[0]从0('a')开始
long long res=0;//记录答案
res+=f[len-1];//记录所有长度小于len的严格升序字母字符串
for(int i=0;i<len;i++){//记录所有第i位按字母序小于a[i]的字符串
for(int j=former;j<a[i];j++){//
res+=c[25-j][len-1-i];//25-j 可用字母数量 len-1-i 还未确定的字母个数 由于题意保证,不需要加条件判断正确性
}
former=a[i]+1;
}
return res+1;//只记录了比自己小的字符串所以+1
}
bool check(){//检验是否严格升序,没看清题意忘了检验,wa第一次
int fl=true;
int len=0;
char former='a'-1;
for(len=0;len<10;len++){
if(ans[len]==0)break;
if(ans[len]<=former){
fl=false;
break;
}
former=ans[len];
}
if(len==0)return false;//无关紧要
return fl;
}
int main(){
generc();
generf();
cin>>ans;//只有一组数据,wa第二次
if(check())cout<<calc()<<endl;
else cout<<0<<endl;
return 0; }

  

这道题虽然水,但反映了我不读题意的问题,我写的也不好,接下来去找大神题解去

解法2  看了题解后的新想法,dp,但是悲哀的是忘了former的存在//16ms

#include <iostream>
using namespace std;
char ans[11];
int a[10];
int len;
long long memo[11][27];//memo[i][j] i 当前长度 j 以何种字母开头 (j=26相当于所有字母皆可的'X')
//memo[i][j] 长度<i && 字典序 小于j 的所有严格升序字符串
void setmemo(){
//memo[1][0]=0;//a前面没有 符合条件的字符串
for(int i=1;i<27;i++)memo[1][i]=memo[1][i-1]+1;
for(int i=2;i<11;i++){
//memo[i][0]=0;
for(int j=1;j<26;j++){
memo[i][j]=memo[i][j-1]+memo[i-1][26]-memo[i-1][j];//所有可能减去小于j的可能
}
memo[i][26]=memo[i][25];//任何长度>1的字符串首位必然不是z
}
}
long long calc(){
long long ans=0; for(int i=0;i<len;i++){
ans+=memo[len-i][a[i]];
if(i)ans-=memo[len-i][a[i-1]+1];
ans+=memo[i][26];
}
return ans+1;
}
bool check(){
bool fl=true;
char former='a'-1;
for(len=0;len<10;len++){
if(ans[len]==0)break;
if(ans[len]<=former){
fl=false;
break;
}
a[len]=ans[len]-'a';
former=ans[len];
}
if(len==0)return false;
return fl;
}
int main(){
setmemo();
while(cin>>ans){
if(check())cout<<calc()<<endl;
else cout<<0<<endl;}
return 0;
}