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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 575 Div1  

2013-04-11 20:43:51|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
成功解决一套tc的题目。。。不吐槽1000分的题了,这种经典网络流建模方式全都是在tc学到的。
不过现在头也不疼了,脖子也不酸了。。感觉感冒都好了(果然颓颓身体爽啊
题目都不难,基本上无压力的说。。不过第二题稍稍坑爹了一下。

A题:
一个数,两个人玩游戏,每次可以将这个数减去它的一个约数,问先手是否必胜?
和lyy试图欢乐地不用打表的方法找出答案。。结果以失败告终。。于是打了个表:
2的偶数次幂及其它偶数是必胜的。

B题:
一列数,首先随机K次选择两个数交换,然后随机一个区间,求期望的区间和。
。。。这道题开始我想偏了,想固定区间然后求每个数落进去的概率。。结果发现要解线性递推方程,麻烦死了。
于是就这样,计算每个数在某个位置的概率,注意除了原本的位置,落在其它地方的概率都是相同的,那么存下这两个值进行递推就行了,很简单的。

C题:L(占三个格子)形尽可能多地覆盖棋盘(黑白相间),要求中间的必须在黑格,有些地方有障碍。求最多能放多少L形。
据说是原题,但是这么裸的网络流也不需要是原题。。几乎一遍AC了。感觉状态真心碉堡。
由于中间的必须是黑格,那么就相当于用黑格连接两个相邻的白格。每个黑格只能用一遍,说明边的容量为1。
这样之后白格之间的图是个二分图。那么差不多像个二分图匹配那样搞就行了,偶数行的白格从源点连边,奇数行的连向汇点,中间用黑色格子的边连接,跑得飞快。
  评论这张
 
阅读(161)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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