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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 174 div1  

2013-03-19 14:43:12|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好久没来空间发东西了,打个哈欠再说。。。 出题就花了我三天的时间,而后断断续续也费了不少功夫。
接下来试图挑战CTSC2011 的无穷图的桥。。。结果失败了,败得很是凄凉
所以必须做做CF涨涨自信再说,否则我还真会这样颓废而虚耗下去
所以说,在昨晚很是昏睡的情况下,做了一下这套题。(其实今天做E又想了一个上午才想出来)

A.
题意:每次将前k个数加上一个值,在最后添加一个数,或者删除最后一个数,询问平均数。
水题,略。O(n)的算法都行。

B.
题意:两个计数器,x,y。每次y+=a[x],x+=a[x],之后y+=a[x],x-=a[x],当x<1 || x>n时停止。现在给定a[2-n]。对于每个可能的a1,求问最后y的值,无穷大输出-1。
每个点往外连一条边,显然是树然后走环对吧。有环就是-1。否则可以直接在树上累计答案。。。没啥好说的,个人比较傻,交了好多好多次。

C.
题意:很多种面值的硬币,然后要求某些硬币的数量大于另外一些。要求湊出t的方案数,t<=100000。这些大于关系只会构成环或链。
有环就无解了吧。链的话,我们对硬币的数量做差分。那么就是要求差分大于0,利用差分来算总和,那么等价于将链中排在后面的往前面加入。修改后的价值乘以差分的值就是答案了,这样将硬币之间的关系取消掉,然后完全背包计算答案。

D.
题意:数对(x,y)合法,那么x可以表示成连续y个数的和。要求将一个数列修改成一个合法数列,也就是数列的相邻两项组成的数对是合法的,求问最少得修改多少个数。(n<=5000)
本题最纠结的地方在于——n比较小,所以注意算法复杂度是n^2的,也就是说可以暴力dp。
我们来观察合法的数对,也就是存在一个n使得(2*n-1+y)*y==2*x。那么条件就是y是2*x的约数且2*x/y与y的奇偶性不同。形象的将,y是x的约数,要么y是奇数,要么y包括了x的所有2因子。
我们将原来的数变成a[i]*2^num[i]的形式
接下来是dp,记f[i]为前i个数修改为合法数对的方案数。找到上一个j使得j可以连在i前面。条件是,a[i]是a[j]的约数,num[i]==num[j]+i-j(也就是一直都是保存2因子)|| num[i]<j-i(代表在某个数的时候变成了奇数)。
很多人都WA on test7了,仅仅是个简单判断语句写错,怨念啊。

E.
1-n的数,每两个数之间具有一个大小关系,开始是小的数小于大的数。操作将[a,b]中的数两两之间的大小关系取反。问最后三元组(a,b,c)的个数(a>b>c c>a)。
会的话这题就是道水题:考虑反的情况,那么只可能是(a>b a>c,cb关系不确定),也就是说a大于的任意两个数就与一组反例一一对应。那么就是对于每个数统计其大于的数有哪些。
这个可以直接用线段树来搞的。

忘了说了,这套题似乎是我见过的最水的一套CF,但是各种错。。。
USACO风格,不想吐槽了
  评论这张
 
阅读(185)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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