【noip模拟赛3】编码

描述

Alice和Bob之间要进行秘密通信,他们正在讨论如何对信息进行加密:

Alice:“不如采用一种很简单的加密方式:’A’替换成1,’B’替换成2,„„,’Z’替换成26。”

Bob:“这种加密方式太傻了,Alice。如果我想要传送一个单词’BEAN’给你,它加密后就是25114。但你有很多种不同的方法来解密,从而得到许多单词!”

Alice:“你说的是没错,但是除了’BEAN’有意义以外,其他解密出来的’BEAAD’、

’YAAD’、’YAN’、’YKD’和’BEKD’都没有任何含义。”

Bob:“是的,但是同一个加密后的数字序列,可能的得到数以亿计的不同解密方案。”

Alice:“是吗?有这么多吗?”

你要帮助Bob编写一个程序,来说服Alice。对于一个加密后的数字序列,告诉她确切的解密方案数。

输入

有若干个加密后的数字序列,每行一个,行数不超过10,每行的数字数量不超过10000个。序列一定是符合要求的,例如没有先导的零和连续两个零等情况。数字间没有空格。一行一个零表示输入结束,这是不需要处理的。

输出

对于每个加密后的数字序列,输出一行。一个整数,表示解密的不同方案数。结果保证在32-bit带符号整数(longint)范围内。

输入样例 1 

25114  
1111111111
3333333333
0

输出样例 1

6  
89
1

题解:

类似斐波那契数列,对于一个点s[i],如果(s[i-1]-'0')*10+s[i]-'0'<=26,则还要加上它上上个点的距离

//
//  main.cpp
//
//
//  Created by Edwin on 2019/3/8.
//  Copyright &#169; 2019 Edwiv. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
const int maxn=10000+100;
using namespace std;
ll dis[maxn];
string s;
void work(int len){
    fill(dis,dis+len+1,0);
    dis[0]=dis[1]=1;
    for(int i=1;i<len;++i){
        if(s[i]!='0')
            dis[i+1]=dis[i];
        if(s[i-1]!='0'&&((s[i-1]-'0')*10+s[i]-'0'<=26))
            dis[i+1]+=dis[i-1];
    }
}
           
int main(){
    while(getline(cin,s)){
        if(s[0]=='0')
            break;
        work(s.length());
        printf("%lld\n",dis[s.length()]);
    }
    return 0;
}

 

发表评论,支持MarkDown语法