首页 > 代码库 > The Alphabet Sticker

The Alphabet Sticker

题目大意:给你一串字符串,其中有一部分未知,用’?’表示。

现在定义一种合法的Sticker,比如”aabcc”,“ccccab”。即所有相同的字母要在一起才是合法的。现在请问对于给定的字符串,有多少种合法的结果。

比如:”aa??bb”合法的字符串有三种。

分别是“aaaabb” “aaabbb” ”aabbbb”.

‘?’表示的字符只能从已经给出的字符中选,所以”aaccbb”是不合法的。

由于最终结果很大,所以把结果对 1e9+7取模。

题目看懂之后思路就很明确了,一个组合问题。

分析一下:

1、相同字母需要在一起

2、只能从存在的字母中选。

显然的,‘?’只能从左边或者右边的字母中选取。

‘?’出现的情况有一下几种(打引号好累):???xx   xxx??   xx??xx   xx?yy

第一种和第二种是一样的,因为出现在序列首/尾部。这两种情况只有1种。

第三种:只有一种,必须和x一样。

第四种:这个情况比较多,但是很容易感觉到会与‘?’的个数有关,来找下规律

aaa?bbb   长度 1    种数 2   aaaabbb   aaabbbb

aaa??bbb  长度 2    种数 3   aaaaabbb  aaaabbbb  aaabbbbb

aaa???bbb 长度 3    种数 4   aaaaaabbb aaaaabbbb aaaabbbbb aaabbbbbb

规律很快就的出来了,种数 = 长度 + 1。

 

好了,所有‘?’出现的情况都分析过了,下面利用组合数学的知识,对于每一部分‘?’的种数应该乘起来求组合数。只需要在乘的过程中记得对mod取余,防止溢出就好了~

等下,是不是还忘记了一种情况。

我们默认认为数据都是合法的字符串,但是如果给你的就是一个不合法的字符串,那么这时候就应该输出0。

下面附上代码:

/* * Problem: A *    Date: 2014-7-20 *  Author: Wuhen*/#include <map>#include <list>#include <queue>#include <string>#include <vector>#include <cstdarg>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>#define LL long long#define Clean(a) memset(a, 0, sizeof(a))using namespace std;bool vis[300];const LL mod = 1e9+7;LL deal(LL len, char l, char r){    if (l == r) return 1;    else return (len+1)%mod;}int main(){    LL T;    cin >> T;    while(T--)    {        string s;        cin >> s;        Clean(vis);        LL all = 0;        for (LL i = 0; i < s.size(); i++)        {            if (s[i] == ?) continue;            if (vis[s[i]] == 0)            {                all += 1;                vis[s[i]] = 1;            }            else            {                LL find = i-1;                while(s[find] == ? && find >= 0) find--;                if (s[find] != s[i])                {                    all = 0;                    break;                }            }        }        if (all == 0)        {            puts("0");            continue;        }        LL res = 1;        LL start = 0, stop = s.size() - 1;         while(s[start] == ? && start < s.size()) start++;        while(s[stop] == ? && stop >= 0) stop--;        for (LL i = start; i <= stop; i++)        {            if (s[i] != ?) continue;            char left = s[i-1];            LL len = 0;            while(s[i] == ? && i <= stop)            {                len++;                i++;            }            res *= deal(len, left, s[i]);            res %= mod;        }        cout << res%mod << endl;    }    return 0;}