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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

Croc Champ 2013 - Round 2 (Div. 2 Edition)  

2013-04-23 13:50:44|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
比赛中做了A,B,C三题,但是结果C题被卡掉了。。。
三题都不难,比赛刚开始,服务器就卡死了,结果延迟了10分钟,而且把两场比赛顺序换了,结果一开始没仔细看就点了进去看题,等把第一题代码敲完,提交时才发现做的题不是自己报的那场。。。。还好这题是比赛的C题,交上去WA了。。。。这时就有点慌了,不知道该做A题去还是去debug。最后还是决定先做简单的题先。。。
哎,不知道是不是服务器原因,比赛一开始节凑就乱了,结果后面做题慌慌张张的,范了好几个低级错误。

题意:
给出一个n个数的序列,在序列里找一个数a[i],满足a[i]能够整除序列里的n个数,如果存在这样的a[i],输出a[i],否则输出-1。
题解:
题目很简单,找出n个数里最简单的数t,如果t能够整除这n个数,则输出n,否则输出-1。
总结:做的时候太慌了,没仔细看数据范围,1<=a[i]<=10^9,结果找最小值时,直接赋了0xfffffff。。。这才2^28(约2.68亿)
,结果交上去果断WA了,改完后才A。

题意:
先输入n和k,然后是一个n长的字符串,由 '.' 和 '#' 组成,‘.’表示可站立的地方,‘#’表示不可站立的地方,k表示最多可以从i走到i+k,问是否可以从左到右走一遍,可以的话输出YES,否则NO。
题解:
这题也很简单,做的很顺利,一A了。从左到右循环一遍,如果有多个'#'相连,则判断长度是否大于等于k,如果有则输出NO,否则输出YES。

题意:
输入一个数n,接着是两个长为n*2的字符串A串和B串,均由0或1组成。有两个人A和B玩游戏,两人轮流选一个1到n*2的数k,选完为止,选过了不能再选。若A选,则取出A串里的第k个数并记录,B也如此。最后两人手里都有n个数,最后两人分别将这n个数以任意顺序排列组成一个数,比较这两个数大小(可以有前导0),A大输出“First”,B大输出“Second”,一样大输出“Draw”。A先选,假设两人都是按着最优策略进行游戏。
题解:
可以发现,如果A选了k,则B不能选k。所以最优策略应该是这样:对于A来说,先选取A串和B串中a[i]都为1的,然后选取A串为1 B串为0的,接着选A串为0 B串为1的,最后选A串为0 B串为0的。对于B来说,他的最有策略也是如此。
所以,只需要统计下A串和B串中都为1的个数记为nc,A串为1 B串为0的记为na,B串为1 A串为0的几位nb,用sa和sb来记录A和B最后1的总个数。
如果nc是个偶数,则记sa=0,sb=0;如果是个奇数,sa=1,然后对sb进行讨论,如果na大于0,则na--;如果na等于0,nb大于0,则sb=1,nb--。否则sb=0。
然后讨论na和nb大小关系,如果na大,则sa+=(na-nb+1)/2;如果nb大,则sb+=(nb-na)/2;因为是A先取,所以A占优势(注意加粗部分区别)。
最后比较下sa和sb的大小即可。
总结:这道题出的很好,有很多陷阱,或者说有很多地方容易出错
一:题目数据范围n最大到10^5,但是字符串给的长度是2*n,所以数组应该开到2*n;
二:策略中,对A来说,取完两个串都为1的,取完A为1 B为0后,接下来应该取的是A为0,B为1;
三:策略中,要注意nc为奇数,在对sb进行讨论是,别忘了有一种情况是na为0,nb大于0;
四:在讨论na和nb关系时,因为A先取,所以A占优势,对于B来说,如果nb>na,sb应该sb+=(nb-na)/2,而不是sb+=(nb-na+1)/2。
在比赛中,陷阱一,二,四都遇到了,一一解决后过了预测试数据,但是陷阱三没有考虑到,比赛后被卡了,看到数据后才意识到,改完后就A了。哎,这题太可惜了,还是差了一点,1000多分就这么没了。。。
  评论这张
 
阅读(64)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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