博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces 314 E. Sereja and Squares
阅读量:6501 次
发布时间:2019-06-24

本文共 1077 字,大约阅读时间需要 3 分钟。

 

题意:

原本有一个合法的括号序列

擦去了所有的右括号和部分左括号

问有多少种填括号的方式使他仍然是合法的括号序列

括号有25种,序列长度<=1e5

 

传统的做法:

 

令dp[i][j]表示当前到第i个字符,现在还有j个左括号
若第i+1个字符是左括号,则能转移到dp[i+1][j+1]
若第i+1个字符是问号,则能转移到dp[i+1][j-1]与dp[i+1][j+1]
时间复杂度为O(n^2)
 
换种思路
再看这道题,他与传统的括号序列的不同之处是他擦去了所有的右括号
令dp[k][i]表示 假设括号只有一种,前k个里面,填了i个右括号的方案数
如果第i个是问号
若当前可以填左括号 dp[k][i]+=dp[k-1][i]
若当前可以填右括号 dp[k][i]+=dp[k-1][i-1]
dp[n][n/2]就是如果只有一种括号,使序列合法的方案数
现在有25种括号,假设序列中已有q个左括号
那么最终答案=25^(n/2-q) * dp[n][n/2]
 
这个感觉上去也是n^2的
首先把第一维压去,解决空间问题
考虑j的枚举范围
前i个里面,至多有i/2 [下取整] 个右括号
至多可以填m个左括号,所以至少有i-n/2个右括号
平摊复杂度我就不知道了
 
对2^32取模相当于unsigned int 自然溢出
 
然后就过了,跑的还很快

 

 

#include
using namespace std;#define N 100002char s[N];unsigned int f[N<<1];int main(){ int n; scanf("%d",&n); if(n&1) { putchar('0'); return 0; } scanf("%s",s+1); int m=n>>1,q=0; f[0]=1; for(int i=1;i<=n;++i) if(s[i]=='?') for(int j=i>>1;j && j>=i-m;--j) f[j]+=f[j-1]; else q++; unsigned int ans=f[m]; for(int i=1;i<=m-q;++i) ans*=25; printf("%u",ans);}

 

转载于:https://www.cnblogs.com/TheRoadToTheGold/p/8443668.html

你可能感兴趣的文章
cf修改游戏客户端是什么意思_瓦罗兰特很有可能取代cf成为国内最火的fps游戏...
查看>>
matlab打开笔记本摄像头_联想笔记本V310摄像头问题解决
查看>>
proto文件支持继承吗_JavaScript继承(一)——原型链
查看>>
rez注入器源码_最简 Spring IOC 容器源码分析
查看>>
itil 容量管理流程_ITIL/ITSM:服务目录设计「精华」
查看>>
labview如何弹出提示窗口_LabVIEW开发者必读的问答汇总,搞定疑难杂症全靠它了!...
查看>>
移动宽带套餐介绍_奋斗20载 整装再出发|千兆光纤入户“数字推手”烟台移动为生活“加速”...
查看>>
提取series中的数值_Python中None和numpy.nan的区别
查看>>
原理面试题_这12道高频原理面试题,你能答出几道?
查看>>
提交失败_金三提交又失败?小易给你支支招
查看>>
小米笔记本air无法充电_30W、45W、65W PD充电器对小米笔记本Air 13.3英寸0~100%充电测试...
查看>>
fidde调试手机_使用Fiddler抓包和调试移动web页面
查看>>
python 解析模块脚本_Python argparse模块应用实例解析
查看>>
大学生免费查题公众号_大学生免费查题公众号?搜题免费公众号?
查看>>
angular单选按钮_AngularJS单选按钮实例
查看>>
stm32实验报告心得体会_STM32实验报告
查看>>
单片机中XPL指令是什么_8051单片机的指令系统有什么特点
查看>>
datatable.load 是post请求吗_Python接口自动化之requests请求封装
查看>>
wdcp mysql版本_升级WDCP的PHP及MYSQL版本
查看>>
mac mysql打不开闪一下_mysql command line client打不开(闪一下消失)的解决办法
查看>>