题目链接:uva 1358 - Generator
题目大意:给定n,表示有n中字符,然后给定一个字符串S,一开始字符串为空,现在每次随机生成一个1~n的字符添加到字符串末尾,问说字符串包含S为子串的生成次数期望。
解题思路:首先要对S进行预处理,求出失配数组。
定义dp[i]表示末尾部分匹配了i个S串所需要的次数期望,每次枚举可能出现的字符1~n。对于S字符串,i+1肯定是确定的字符,所以对于其他字符肯定是不匹配的。
假设现在生成了k字符,并且说k字符不等于S[i+1],那么根据S的失配数组,我们可以确定目前还匹配几个字符,(类似KMP匹配问题),假设有匹配j个字符,那么也就是说从匹配j个到匹配i个我们还要重新生成dp[i] - dp[j]次(期望)。
于是f(i)(从匹配i-1到匹配i个需要生成次数的期望)即有公式f(i)=1+∑i=1n(dp[i−1]−dp[lose(k)])+n−1nf(i)(lose(k)为对应生成字符为k的情况下还匹配的字符数)
dp[i] = dp[i-1] + f(i)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 20;
int len, jump[maxn];
void get_jump(char* s) {
int p = 0;
len = strlen(s+1);
for (int i = 2; i <= len; i++) {
while (p && s[p+1] != s[i])
p = jump[p];
if (s[p+1] == s[i])
p++;
jump[i] = p;
}
}
ll solve () {
int n;
ll dp[maxn];
char s[maxn];
scanf("%d%s", &n, s+1);
get_jump(s);
dp[0] = 0;
for (int i = 1; i <= len; i++) {
ll& ans = dp[i];
ans = dp[i-1] + n;
for (int j = 0; j < n; j++) {
if (s[i] == 'A' + j)
continue;
int p = i-1;
while (p && s[p+1] != j + 'A')
p = jump[p];
if (s[p+1] == j + 'A')
p++;
ans += dp[i-1] - dp[p];
}
}
return dp[len];
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
printf("Case %d:\n%lld\n", kcas, solve());
if (kcas < cas)
printf("\n");
}
return 0;
}
分享到:
相关推荐
mybatis-generator-1.3.2包+使用说明 该文件包括mybatis-generator-1.3.2的工具包以及使用详细说明 说明在压缩包中
自己找资料,慢慢高了一个mybatis自动生成代码的类,当然是在mybatis-generator基础之上的,由于项目中有lombok,所以需要对生成的地方进行改造。我将改造后的文件都打包上传了,需要的同学拿去吧 zip包里面包含: ...
mybatis-generator+generator.xml
mybatis-generator 1.3.5 源码+改进+支持自定义文件后缀+表、字段注释 mybatis-generator 1.3.5 源码+改进+支持自定义文件后缀+表、字段注释
赠送jar包:mybatis-generator-core-1.3.7.jar; 赠送原API文档:mybatis-generator-core-1.3.7-javadoc.jar; 赠送源代码:mybatis-generator-core-1.3.7-sources.jar; 赠送Maven依赖信息文件:mybatis-generator-...
mybatis-generator-config_1_0.dtd文件存在于mybatis-generator-core-1.3.2.jar包中,路径如下org/mybatis/generator/config/xml/mybatis-generator-config_1_0.dtd 可以设置开发工具的dtd配置,配置...
mybatis3.0.5+mybatis-spring+mybatis-generator-core-1.3.2
最快速的java代码生成器 rapid-generator
form-generator集成到本地项目
赠送jar包:activiti-image-generator-5.21.0.jar; 赠送原API文档:activiti-image-generator-5.21.0-javadoc.jar; 赠送源代码:activiti-image-generator-5.21.0-sources.jar; 赠送Maven依赖信息文件:activiti-...
包含mybatis-generator-core-1.3.2.jar最新jar包,能够自动生成sqljdbc4.jar SQLServer mysql-connector-java-5.1.25-bin.jar MySql 对应的mapping pojo dao下的三个类还提供了自动生成方法以及命令输入方法。
mybatis-plus最新代码生成器项目源码 :mybatis-plus-generator.zip mybatis-plus最新代码生成器项目源码 :mybatis-plus-generator.zip mybatis-plus最新代码生成器项目源码 :mybatis-plus-generator.zip ...
赠送jar包:activiti-image-generator-5.21.0.jar; 赠送原API文档:activiti-image-generator-5.21.0-javadoc.jar; 赠送源代码:activiti-image-generator-5.21.0-sources.jar; 赠送Maven依赖信息文件:activiti-...
mybatis-generator-core-1.3.5.jarmybatis-generator-core-1.3.5.jarmybatis-generator-core-1.3.5.jarmybatis-generator-core-1.3.5.jar
赠送jar包:mybatis-generator-core-1.3.7.jar; 赠送原API文档:mybatis-generator-core-1.3.7-javadoc.jar; 赠送源代码:mybatis-generator-core-1.3.7-sources.jar; 赠送Maven依赖信息文件:mybatis-generator-...
逆向工程mybatis-generator-1.3.2,命令行生成
jar包,直接替换eclipse->plugin下的 org.mybatis.generator.core_1.3.4.201608190045.jar包即可 如果版本不同的话,那么用外面的*.class文件找到相对应的目录替换jar包里的class就行。 这里也放了未编译的*.java...
form-generator表单设计器api文档,用于设计自定义组件
mybatis-generator-core-1.4.0-SNAPSHOT. 源码生成mybatis-generator-core-1.4.0-SNAPSHOT.jar方法.详细可见 https://blog.csdn.net/dono118/article/details/82980841
mybatis-generator逆向生成持久层代码,所需jar包,版本1.3.6