第一站长网,泰安人才网招聘信息网电焊工,建网站的费用,广州品牌设计网站建设Secret Code 一、题目 【NOIP模拟赛A10】Secret Code 时间限制: 1 Sec 内存限制: 128 MB 提交: 10 解决: 6 [提交][状态][讨论版] 题目描述 农夫John#xff08;以后简称“FJ”#xff09;有些不想让他的奶牛看见的秘密消息#xff1b;这条消息是一个长度至少为2仅包含字符… Secret Code 一、题目 【NOIP模拟赛A10】Secret Code 时间限制: 1 Sec 内存限制: 128 MB 提交: 10 解决: 6 [提交][状态][讨论版] 题目描述 农夫John以后简称“FJ”有些不想让他的奶牛看见的秘密消息这条消息是一个长度至少为2仅包含字符A..Z的字符串。为了加密他的消息FJ对这条消息进行了一系列“操作”。一次对字符串S的“操作”是指去掉S开头的若干个字母但不是全部或末尾的若干个字母但不是全部然后将原来的S拼接到其开头或末尾。例如一次对于字符串ABC的操作可能有以下8种结果 AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC 已知最终加密后的字符串请计算FJ有多少种可能的方法对某一源字符串进行一次或多次重复的“操作”得到该加密字符串。尽管对一个字符串的不同方法的“操作”可能得到相同的结果这些方式也应该被视作不同而被分别计数。例如有4种不同的操作方法从AA得到AAA。 输入 第1行一个长度不超过100的字符串。 输出 第1行FJ对某个长度至少为2的源字符串进行一次或多次操作后能够得到该结果字符串的不同方法数答案可能会很大答案请对2014求余。如果没有方法得到结果字符串则输出0。 样例输入 ABABA 样例输出 8 提示 以下是FJ可以得到ABABA的不同方法 1. Start with ABA - ABABA 2. Start with ABA - ABABA 3. Start with AB - ABA - ABABA 4. Start with AB - ABA - ABABA 5. Start with BA - ABA - ABABA 6. Start with BA - ABA - ABABA 7. Start with ABAB - ABABA 8. Start with BABA - ABABA 二、代码及分析 代码一 1 /*2 * 状态3 * f[i][j]表示以i为起点以j为终点的字符串出现的次数4 * 最终状态5 * f[1][n]6 * 初始状态7 * 初始结果字符串的所有的子字符串出现的次数都为18 * 因为我们是要用子串得到别的串而这个子串最开始出现的次数就为19 * 状态转移方程
10 * f[i][j]f[i][k]*f[k1][j] (ikj)并且满足短串是长串的头尾字串;
11 *
12 * f[1][3]f[1][1]*f[2][3]f[1][2]*f[3][3];
13 * 短的串要是长的串的子串并且是那种只截取前面或者只截取后面的那种
14 */
15
16 #include iostream
17 #include cstring
18 using namespace std;
19 int f[105][105];
20 char s[105];
21 int len;
22
23 void printRead();
24 void readData(){
25 scanf(%s,s1);
26 lenstrlen(s1);
27 }
28
29 void printArr_f();
30 void initArr_f(){
31 //因为任意一个长度不为Len的串都可以作为起始串
32 //所以任意一个长度不为Len的串起始可能性都为1
33 for(int i1;ilen;i){
34 for(int ji;jlen;j){
35 f[i][j]1;
36 }
37 }
38 //因为必须要截掉头尾故长度为len的串不行
39 //我不可能去用1-n这个字符串去得到别的字符串吧所以出现次数为0
40 f[1][len]0;
41 }
42
43 //求字符串(c,d)是不是(a,b)的前子字符串
44 bool frontSubstring(){
45
46 }
47
48 //求字符串(c,d)是不是(a,b)的后子字符串
49 bool backSubstring(){
50
51 }
52
53 void init(){
54 readData();
55 printRead();
56 initArr_f();
57 printArr_f();
58 }
59
60 void dp(){
61 for(int ilen;i1;i){
62 for(int ji1;jlen;j){
63 for(int ki;kj;k){
64 f[i][j]f[i][k]*f[k1][j];
65 }
66 }
67 }
68 }
69
70 int main(){
71 freopen(src/in.txt,r,stdin);
72 init();
73 dp();
74 return 0;
75 }
76
77 void printRead(){
78 for(int i1;ilen;i){
79 couts[i];
80 }
81 coutendl;
82 }
83
84 void printArr_f(){
85 for(int i1;ilen;i){
86 for(int j1;jlen;j){
87 coutf[i][j] ;
88 }
89 coutendl;
90 }
91 } AC代码 1 #includebits/stdc.h2 using namespace std;3 char s[150];4 int ans[150][150];5 //ans[i][j]中存储从s中的第i个元素到第j个元素有多少种出现的可能6 bool Front_Maybe(int a,int b,int c,int d)7 {8 for(int i a;i b;i )9 {
10 if(s[i] ! s[c i - a]) return 0;
11 }
12 // printf(前面%d %d %d %d\n,a,b,c,d);
13 return 1;
14 }
15 bool Behind_Maybe(int a,int b,int c,int d)
16 {
17 for(int i b;i a;i --)
18 {
19 if(s[i] ! s[d - b i]) return 0;
20 }
21 // printf(后面%d %d %d %d\n,a,b,c,d);
22 return 1;
23 }
24 int main()
25 {
26 freopen(src/in.txt,r,stdin);
27 scanf(%s,s 1);
28 int Len strlen(s 1);
29 for(int i 1;i Len;i )//起始串的长度
30 {
31 for(int j 1;j Len;j )//起始串的起点
32 {
33 //i是长度j是起点那么ij-1就是终点
34 //如果终点大于长度
35 if(i j - 1 Len) continue;
36 ans[j][i j - 1] 1;
37 //因为任意一个长度不为Len的串都可以作为起始串
38 //所以任意一个长度不为Len的串起始可能性都为1
39 }
40 }
41 for(int i 2;i Len;i )//当前要处理串的长度
42 {
43 for(int j 1;j Len;j )//当前要处理串的起点
44 {
45 if(i j - 1 Len) continue;
46 for(int x 1;x i;x )//添加串的长度
47 {
48 if(j - x 0)//向后加处理串 起点合法
49 {
50 if(Front_Maybe(j - x,j - 1,j,j i - 1))
51 {
52 ans[j - x][i j - 1] ans[j][i j - 1];
53 }
54 if(Behind_Maybe(j - x,j - 1,j,j i - 1))
55 {
56 ans[j - x][i j - 1] ans[j][i j - 1];
57 }
58 ans[j - x][i j - 1] % 2014;
59 }
60 if(i j - 1 x Len)//向前加处理串 终点合法
61 {
62 if(Front_Maybe(j i,j i - 1 x,j,j i - 1))
63 {
64 ans[j][i j - 1 x] ans[j][i j - 1];
65 }
66 if(Behind_Maybe(j i,j i - 1 x,j,j i - 1))
67 {
68 ans[j][i j - 1 x] ans[j][i j - 1];
69 }
70 ans[j][i j - 1 x] % 2014;
71 }
72 }
73 }
74 }
75 printf(%d,ans[1][Len]);
76 return 0;
77 }
