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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforcces 172 div1  

2013-03-11 02:26:15|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
神题一套。。。
出题人阵容强大,lyp,clj,hjt,setter,xiaodao。
简直就是逆天啊。。。
中国人各种屠场。。。
呵呵,我国的题目,别的国家的敢做?
为表支持,特地来做了做。
E题竟然是CTSC级别的,幸好我没有去看。。。
考得还行,最终rank38了
细节白天再说吧。

基本上就是碰运气的比赛啊
A题看着就头疼,明知可以分类讨论但是还是各种纠结蛋疼。。。所以最终还是暴力线段求交搞的,做了40分钟,而且还交了两遍,差点都放弃了。
B题开始也想了会,后来发现就是个单调栈模型,于是就水过了。
C题则毫无思路,猜了结论。。。结果就过了。

唉,以后再也不在tieba泄漏马甲名字了
一直靠着法法塔这个号在tieba到处乱说话。。
算了,懒得搞马甲了
=========================================================================
更新题解啦。。。比官方题解还早哟:
前三题好像已经说过了吧。。。所以我就直接交了考场上的代码。

A题:给定一个中点在原点的矩形,求出其与其旋转一定角度之后的矩形的交的面积。
这种题目就是典型的无聊分类讨论和暴力。。。
但是分类讨论实在是太麻烦了。。。只能orz各种数学帝直接分析。作为傻叉的我只能将旋转后的矩形与原矩形的交点全部求出来最后搞个多边形的面积计算,写得囧死了。

B题:一个数列的lucky值是其最大值和次大值的异或值。求一个元素互不相同的数列lucky最大的连续子序列
好吧,枚举最大的点是哪个,假定次大的在其左边。我们维护一个值递减的单调队列,那么这个单调队列中小于当前值的数是可能作为次大值的。用这些值来更新,这些值就可以踢掉了。。。所以总时间是O(n)的,很快就水过去了。

C题:一道概率题,给定一棵树,每次你可以随机删除以一个点为根的子树。求删除的期望次数。
yy一下,发现每个点给答案的贡献为1/(其祖先的个数)。为什么呢?可以意识流一下的:D。但我们可以这么想,每个点的能够使答案增加1,其留下来的概率是多少呢?如果选择的点不在其祖先的路径上,那么是不相关事件,而考虑在祖先的路径选择,只有选择自己的话才能使答案增加,而这个概率就是所求。。。其实可以画一条链然后算一算即可发现规律的

D:一个数列的k划分,就是选出其不想交的k或k个以下的连续子区间,其值为所有区间中值的和。那么对于数列的询问就是求出最大的k划分的值。现在有一个数列。每次修改一个值,或者询问其一个子区间的k划分。
很神的题目,暴力进行dp并且进行维护应该是很简单的事情。。。但是这样的时间复杂度是O(k^2logn)。
考虑如何求一个数列的k划分,有个很高端的做法:建立费用流模型,源点往每个点连一条边,每个点往汇点和下一个点连边,那么边权值就是点值,流量限定为k,求费用流。。。显然费用流不如dp的。但是对于特殊图有特殊做法。在连续增广路算法时,求出来的肯定是从某个点到某个点的一个区间,即最大的连续子区间,将这个区间取反,答案加入,搞k次或者答案<0。这个将区间值取反和求最大连续子区间似乎是专业线段树吧。。。所以就没有然后了。

E:一个不严格的递增序列,要求将其修改,使得最终每相邻的两个数a,b 满足B>=b-a>=A,且每个数小于等于q大于等于1。不过将a修改为b的代价为(a-b)^2。
到底玩不玩平衡树呢?总是感觉很难写的样子,麻烦死了。。。不管了。。。过了就行
暴力维护导数区间吧。。。这道题目实在是太难了,远非我等傻叉能够想出来,
但是暴力写真的不难。。。而且非常非常好写好调。。
以下是官方的非官方题解:

令dp[i][x]表示只考虑前i个数,并且把第i个数改成x时的最小代价。

dp[i][x]=(a[i]-x)^2+min{dp[i-1][y]|y=x-B..x-A}

这个dp是没办法做的,因为状态是无限的。我们可以把每个dp[i]看成是定义在[1+A(i-1)..Q]的一个连续函数。

手画一下可以发现,每个dp[i]似乎都是由若干段二次函数组成的严格单峰函数。如果真的是这样,我们可以这样完成函数间的转移:找出dp[i-1]的最低点low,将low右边的图线整体向右移B,左边部分向右移A,中间形成一段长B-A的平台,最后将函数(x-a[i])^2加到这个函数上,我们就得到了dp[i]。事实上考场上这样写就是O(n^2)的可以通过了。

  评论这张
 
阅读(233)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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