[JZOJ4673] 【NOIP2016提高A组模拟7.20】LCS again
题目
描述
题目大意
给你一个字符串和字符的取值范围,问和这个字符串的最长公共子串的长度为N−1N-1N−1的串的个数、
思考历程
一看就知道这是一个神仙题。
思考了一会儿,觉得AC是没有希望的了。
于是我的目标渐渐地降下来,最终,目标变成了如何才能拿分。
这似乎是一道连拿分都不容易的题目!
于是我想过各种方法,什么DP之类的,但是都没有想出来。
于是这题就愉快地没有分了。
比赛后我问同学怎么拿分的。
他说用set
判重。
我恨不得喷出一口老血!
正解
题解的DP方法我还不清楚·,就先说说另一个方法。
显然要再原来的字符串中删去一个字符,然后从某个位置加入另一个字符。
不考虑重复,单纯地想一想:从某个位置删去一个字符,再到其它地方插入的方案数。
在删除这个字符之后的空隙数为nnn,可以放的字符种类为mmm,所以是nmnmnm种方案。
但这当然会有重复。
将字符插入到某个位置旁边的时候,如果这个位置上的字符和它一样,那么插在左边和右边是等价的,也就是重复了。
这样算就有n−1n-1n−1个重复,减去。由于先前的位置不能插入一样的字符,就再减111。
综上,方案数应该是n(m−1)n(m-1)n(m−1)
再考虑更多重复的情况。
可以将原字符串划分成许多块,每块是连续的相同的字符。
我们发现删去块中的每个字符都是等价的,所以我们只需要对于每个块加上n(m−1)n(m-1)n(m−1)的贡献、
难道这就结束了吗?不,其实还有:
举个例子,ab
或ababab
。
我们发现出现子串交替的时候,就会出现一些重复。
在程序实现的时候,其实可以维护末尾为i−2i-2i−2和iii的最长公共子串的长度,这个长度加一就是iii这个位置要减去的贡献。
似乎也就这两种情况了,我不会证明还有没有别的情况。
这种东西在比赛时是极难推出来的,我们姑且将它们算作找规律罢……
代码
using namespace std;
#include <cstdio>
int n,m;
char str[100010];
int main(){
scanf("%d%d%s",&n,&m,str+1);
long long ans=n*(m-1),len=0;
for (int i=2;i<=n;++i){
len=(str[i-2]==str[i]?len+1:0);
if (str[i-1]!=str[i])
ans+=n*(m-1)-len-1;
}
printf("%lld\n",ans);
return 0;
}
总结
比赛时一定要学会找规律……
最新文章
- win7如何让局域网其他电脑通过IP直接访问自己电脑的网站
- oracle initialization or shutdown in progress问题解决步骤
- Android Mina框架的学习笔记
- Apache服务器访问过慢分析及解决
- C#中Messagebox.Show()常用参数用法详解
- [Android学习笔记]LayoutParams的使用
- UML和模式应用学习笔记-1(面向对象分析和设计)
- PHP 常用的header头部定义汇总
- vue 单文件组件中样式加载
- 大前端的自动化工厂(5)—— 基于Karma+Mocha+Chai的单元测试和接口测试
- 盘点 React 16.0 ~ 16.5 主要更新及其应用
- 解决kali linux 开启ssh服务后连接不上的问题
- 关于ip包长度
- 使用u盘安装os&#160;x系统
- DevExpress WPF入门指南:绑定编辑器对话框
- 实战:mysql检查物理磁盘中的二进制日志文件是否有丢失
- 在VMware虚拟机中安装Mac OS 操作系统
- Shell编程-04-Shell中变量数值计算
- vue跳转页面传值怎么传?
- Golang教程:数组和切片