【codeforces 156C】Cipher

【题目链接】:http://codeforces.com/problemset/problem/156/C

【题意】

给你一个字符串(由小写字母构成);
你可以把任意一个位置i的字母变成a[i]+1,然后a[i+1]变成a[i+1]-1;
或者把第i个字母变成a[i]-1,然后a[i+1]变成a[i+1]+1;
问你这个字符串能变成多少个其他的字符串;

【题解】

在进行这个操作的时候;
可以发现整个字符串的ascill码的总值是不变的;
且ascill码值相同的字符串都能互相到达;
可以以这个点作为动态规划的状态进行转移;
设dp[i][j]表示前i个字符,ascill码的总值为j的方案书;
dp[i][j+k]+=dp[i][j]; (25>=k>=0)
0..25对应’a’..’z’
然后对于输入的字符串;
先算出其ascill码的总值tot(当然也是把a和0, b和1…对应);
获取长度n;
直接输出dp[n][tot]-1;(要除去本身)

【Number Of WA】

0

【完整代码】

复制代码#include <bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define pb push_back #define fi first #define se second #define ms(x,y) memset(x,y,sizeof x) #define Open() freopen("F:\rush.txt","r",stdin) #define Close() ios::sync_with_stdio(0),cin.tie(0) typedef pair<int,int> pii; typedef pair<LL,LL> pll; const int dx[9] = {0,1,-1,0,0,-1,-1,1,1}; const int dy[9] = {0,0,0,-1,1,-1,1,-1,1}; const double pi = acos(-1.0); const int MOD = 1e9 + 7; const int N = 110; int f[N][N*26],t; char s[200]; inline void add(int &a,int &b){ a+=b; if (a>=MOD) a-=MOD; } int main(){ //Open(); Close();//scanf,puts,printf not use //init?????? f[0][0] = 1; rep1(i,1,100){ rep1(j,0,(i-1)*25){ rep1(k,0,25){ add(f[i][j+k],f[i-1][j]); } } } cin >> t; while (t--){ cin >> (s+1); int now = 0; rep1(j,1,strlen(s+1)) now+=(s[j]-'a'); cout << f[strlen(s+1)][now]-1 << endl; } return 0; }

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int MOD = 1e9 + 7;
const int N = 110;
int f[N][N*26],t;
char s[200];
inline void add(int &a,int &b){
a+=b;
if (a>=MOD) a-=MOD;
}
int main(){
//Open();
Close();//scanf,puts,printf not use
//init??????
f[0][0] = 1;
rep1(i,1,100){
rep1(j,0,(i-1)*25){
rep1(k,0,25){
add(f[i][j+k],f[i-1][j]);
}
}
}
cin >> t;
while (t--){
cin >> (s+1);
int now = 0;
rep1(j,1,strlen(s+1))
now+=(s[j]-'a');
cout << f[strlen(s+1)][now]-1 << endl;
}
return 0;
}