题目:
有一个字符串S，长度为n，现在要对其作变换。变换的规则如下：对于第i（1<=i<=n）个字符，可以保持不变，或者变换为第i-1个字符（如果有的话）或者第i+1个字符（如果有的话）。
请计算一下最多可以变换出多少种不同的字符串，最后总数对 1000000007(109+7) 取余后输出。
样例解释：
样例1中，变换出来的字符串是aa, ag, ga,和 gg。
样例2中，只能变换出aa。
输入
多组测试数据。
第一行有一个整数T（1 ≤ T ≤ 128），表示测试数据的数目。
接下来有T组数据。
每一数据给出一个字符串S（1<=|S|<=1000，只由小写字母组成）。
输出
对于每一组数据，输出一个整数表示答案，占一行。
输入样例
样例输入1
2
ag
aa
输出样例
样例输出1
4
1
解法：
统计每个位置可以变得个数，然后相乘即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<iostream>
#include<set>
#include<string>
using namespace std;
long long mod = 1e9 + 7;
long long solve(string s)
{
int l = s.length();
long long ans = 1;
for(int i = 0; i < l; i++){
set<char> c;
if(i - 1 >= 0)
c.insert(s[i - 1]);
c.insert(s[i]);
if(i + 1 < l)
c.insert(s[i + 1]);
ans = (ans * c.size()) % mod;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string s;
cin >> s;
printf("%lld\n",solve(s));
}
return 0;
}he
|