4.密码编码（scode）

题目描述

农夫约翰最近想发一些秘密的信息，但是他不想让奶牛们知道。这些信息是‘A’到’Z’的字符组成的，长度至少是2。
为了对这些信息进行加密，农夫约翰对这些信息进行了一系列的操作，每次操作，约翰把字符串S去掉从第一个开始连续的若干个字符或者从最后一个字符开始连续若干个字符（至少去掉一个字符，也不能全部去掉），然后把剩余的字符串添加到原来S串的左边或者右边。例如，对于字符串ABC，一次操作可以有8种结果：
AABC
ABABC
BCABC
CABC
ABCA
ABCAB
ABCBC
ABCC
现在给定最后加密好的字符串，约翰想要知道这个字符串可能由多少种方法加密而来，注意，AAA可以由AA通过四种加密操作得来，虽然产生的AAA是一样的，但是加密的过程是不一样的我们就认为是不同的方法。

输入

一个字符串。

输出

输出这个加密的字符串可以由多少种方法加密而来。【答案要mod 2014】

样例输入

ABABA

样例输出

8

数据范围限制

【数据规模】
字符串的长度不超过100。

提示

【样例说明】
我们有8种方法可以得到ABABA：

  1. Start with ABA -> AB+ABA
  2. Start with ABA -> ABA+BA
  3. Start with AB -> AB+A -> AB+ABA
  4. Start with AB -> AB+A -> ABA+BA
  5. Start with BA -> A+BA -> AB+ABA
  6. Start with BA -> A+BA -> ABA+BA
  7. Start with ABAB -> ABAB+A
  8. Start with BABA -> A+BABA

正解
我们可以用递归，累加4种情况
第一种和第二种
ABABA
A=A
递归 ABAB 和 BABA
第三种
ABABA
AB=AB
递归 ABA
第四种
ABABA
ABA=ABA
递归 ABA

用map记忆化，字符串下标的int类型

洛谷同样的题目
P3102 [USACO14FEB]Secret Code S

AC代码

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
string s;
map<string,int>f;//map定义
int find(string x)
{
   
    if (f[x]!=0) return f[x];//记忆化
    int num=1,l=x.size();
    for(int i=1;i*2<l;i++)//4种情况
	{
   
        if(x.substr(0,i)==x.substr(l-i,i)) 
         num+=find(x.substr(i,l-i))%2014+find(x.substr(0,l-i))%2014;
        if(x.substr(0,i)==x.substr(i,i))
         num+=find(x.substr(i,l-i))%2014;
        if(x.substr(l-2*i,i)==x.substr(l-i,i)) 
         num+=find(x.substr(0,l-i))%2014;
    }
    return f[x]=num%2014;
}
int main()
{
   
	freopen("scode.in","r",stdin);
	freopen("scode.out","w",stdout);
    cin>>s;
    find(s);
    cout<<f[s]-1;//减掉自己
    return 0;
}

下面附本次比赛的其它题目

2020.03.08模拟赛14（第一题）
2020.03.08模拟赛14（第二题）
2020.03.08模拟赛14（第三题）
2020.03.08模拟赛14（第四题）
2020.03.08模拟赛14（总结）

谢谢