注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

Codeforces 314E Sereja and Squares  

2014-09-22 18:25:32|  分类: 集训队作业 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
坐标轴上有n个点,第i个点的坐标为i。
现在将所有点两两配对,给每一对点中坐标较小的标上小写字母,较大的标上大写字母,字母不会是x。
如果给每一对点都看作对角顶点画正方形,而这些正方形不相交也不接触,那么这种配对方法是好的。
现在有一个好的配对方法,但是有一些小写字母和全部大写字母看不清了(以"?"代替),问存在多少种可能,使得还原回去的点上标的字母符合某个好的配对方法。答案mod 2^32。
n≤100000。时间限制4s。
Solution
所有的字母都是一样的,把它们都变成'a'。把小写字母看成左括号,大写字母看成右括号。
考虑dp。设dp[i][j]表示前i个字符的括号序列中,左括号比右括号多j个的方案,那么:
dp[i][j]=dp[i-1][j-1], if s[i]='a'
dp[i][j]=25dp[i-1][j-1]+dp[i-1][j+1], if s[i]='?'
如果n=100000,空间会爆,所以滚动数组搞一搞。
时间也会爆,常数优化搞一搞。就AC了。(我觉得我已经优化到极致了……想再快就应该只能换个dp方程了)
typedef unsigned int U;
char a[100086]; int n;
U _dp[250086], *dp = _dp + 100008;

int main(){
	read(n); scanf("%s", a + 1);
	memset(_dp, 0, sizeof(_dp)); dp[0] = 1;
	f(i, 1, n) if(a[i] == '?'){
		register int til = std::min(i, n - i);
		register U *p1 = dp + til + 1;
		while(til--){
			*p1 += *(p1 - 2) * 25u; --p1;
		}
		++dp;
	}else *(--dp) = 0;
	printf("%u\n", dp[0]);
	
	return 0;
}
  评论这张
 
阅读(210)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018