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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

9、10月份的Codeforces  

2012-12-17 11:18:53|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Codeforces Round #138 (Div. 1)
A:注意到一个括号和谁匹配是固定的。那么记录每个右括号与之匹配的左括号是谁。然后如果出现")("、"]("等等情况,且两个括号都能与某个括号匹配,那么就把括号匹配从"(.........)(.......)"改成“(.........)(.......)”。前缀和记录中括号个数,然后扫一遍所有匹配的括号间中括号个数取最大的就是了。
B:记l[i]为s的前i个字符组成的序列中最长的是t的前缀的子序列的长度。(好绕口……)r[i]就是s的后i个字符组成的序列中最长的是t的后缀的子序列的长度。然后枚举下i,看l[i] + r[i] + 1是不是>= |t|即可。
C:用压缩了的矩阵乘法或推公式。C(k - 1, k + j - 1)
D:没做。好像是很麻烦的计算几何。
E:没做。用流来搞。非常神奇的题目。
D、E的话自己看官方题解吧 >_<

A:类似汉诺塔的问题。F(n) = F(n - 1) + 1 + F(n - 1) + 1 + F(n - 1),解得F(n) = 3^n - 1,用快速幂搞一下就行了。
B:把合并过程看成一棵树,点权为子树权值之和+自己,代价就是树的点值之和。由于cost = sigma(depth * value),所以把大家从大到小排序然后顺着放就行了。但是这可能TLE呃……首先把k = 1特判掉,对于其他情况树高是logn的,于是乎搞个前缀和,相同深度的在一起统计答案,就行了。
C:gcd(Fib(i), Fib(j)) = Fib(gcd(i, j))。若最优解的gcd为g,那么一定是kg, (k + 1)g, (k + 2)g, ..., (s - 1)g, sg,l <= kg <= sg <= r。个数为[r / g] + [(l - 1) / g],然后发现很多时候[x]是相等的,一块一块跳就行了。
D:你没有搞错!调整法就是正解!发现某行或某列为负就取反就行了。由于总和是单调递增的,所以一定会结束。最坏情况下是sum / 2次调整。
E:看了题就知道是裸数据结构题,但是太坑了!倍增求第k,函数式线段树维护dfs序列进行查询……

A:枚举究竟是哪一列,随便搞搞就出来了。
B:有时间限制的最短路,直接Dijkstra就行了。因为早到永远比晚到好。
C:可以得出如下等式:
9、10月份的Codeforces - vfleaking - vfleaking的博客
于是就没有然后了。求出每个点的度,然后用公式。
D:贪心+DP,高度矮永远比高度高好。
E:概率题……最坑爹的地方就是“Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly.”
9、10月份的Codeforces - vfleaking - vfleaking的博客
f[i][j]记录前i个中选了j个与限制相等的元素的方案数,g[i][j]记录总和。最后除一下得到答案。

A:首先搞一个环数最接近k的团出来,然后一个个加点。加入一个点时,每次跟所有之前已有的点连边,直到环数等于k。
B:第i列的黑点数 = 第i + n列的黑点数。于是只用对前n列进行DP就行了。后面的列用快速幂算。
C:给斐波拉契图跪烂了……分治一下就行了。一开始把所有可能分治到的n搞出来,然后从小到大递推。
D:没做。树状数组 + 后缀数组。
E:没做。
D、E的话自己看官方题解吧 >_<

A:随便搞搞。
B:裸DP。
C:首先奇数和偶数打,然后% 4 < 2的跟% 4 >= 2的打,...,% 2^n < 2^(n - 1)的跟% 2 ^ n >= 2 ^ (n - 1)的打。
D:正反正反地拼一起就行了。
E:首先只管好路,求强连通分量缩点,那么擒贼先擒王,首都所在连通分量跟入度为0的连通分量有路可达就行了。如果要修路,这条路一定是要通向一个不可达的入度为0的连通分量的。由此如果有解,修路数一定是不可达的入度为0的连通分量个的。所以直接bfs一遍按照上述规则修路就是最优解。
F:26棵线段树维护之。

orz 出题人wjmzbmr!!!
A:找规律~
B:推公式~
C:没做
D:没做
E:没做
题目太神了!让蒟蒻情何以堪!9、10月份的Codeforces - vfleaking - vfleaking的博客
A、B、C、D、E的话自己看官方题解吧 >_<
  评论这张
 
阅读(750)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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