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

Saffah's Blog

 
 
 

日志

 
 

Codeforces Round #278 (Div.1 and Div.2) 命题报告  

2014-11-24 10:54:20|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
囧……总想写个回忆录然后发现什么也写不出……只能写命题报告玩了……


488A Giga Tower

题意:
给a,求最小正整数b,使得a+b的十进制表示中包含数字8。
-10^9≤a≤10^9。

题解:
其实这题本来不是8而是1……然后发现如果出成8会有一点小trick于是就变成8了……
做法很显然,从小到大枚举b,找到最优解,一般情况下不出10步就能找到了。
但是,8的话b枚举到10是不够的,需要枚举到16,也就是a=-8的时候。
代码:http://ideone.com/hlzsh2
(Python2,93B)


488B Candy Boxes

(这题原来是当Div.1 A的……结果因为太难被换到了这个位置)
题意:
有4个数,n个已知,4-n个未知。要输出一种在剩下4-n个位置填数的方案,使得4个数的平均数、中位数、极差都相等,或输出无解。
0≤n≤4,1≤每个数≤500。1≤输出的数≤10^6。

题解:
设4个数是a,b,c,d那么(a+b+c+d)/4=(b+c)/2=d-a。推得d=3a并且a+d=b+c。

解法1:
设给出的数从小到大依次为x,y,z,u。
如果n是0,直接输出随便一个解。
如果n是1,直接输出{x,x,3x,3x}。
如果n是2,要看3x和y的关系。如果3x≥y,那么输出{x,y,4x-y,3x},否则无解。
如果n是3,解只可能是{x,y,z,3x},{z/3,x,y,z},{x,y,x+z-y,z}中之一,都不是就无解。
如果n是4,直接判合法就行了。
代码:http://ideone.com/wAdm3f
(C++,1.12K)

解法2:
从1到500枚举x,从x到2x枚举y,那么所有的{x,y,4x-y,3x}就包含了所有可能的四元组。
那么对于每个四元组看看是否能和已知数匹配就好了。
代码:http://ideone.com/x9z7XI
(C++,713B)

解法3:
如果n是0,1或4,同解法1。
否则,从1到1500枚举剩下的1个(或2个)数,判合法就行了。
代码:http://ideone.com/KGHA54
(C++,957B)


487A/488C Fight the Monster

(这题本来是Div.2 B……)
(据说Yang翻译成俄语以后变成了Yoga)
(其实我想表达的是羊神)
题意:
羊神要打一个怪,两人都有血攻防,每回合给对方造成的伤害等于自己攻击减去对方防御,血≤0就死了。给出两人的初始属性和购买单位血攻防的价格,问羊神最少花多少钱能打过怪。
所有数字是[1,100]的整数。

题解:
攻击不用加到太高,能一击必杀就不用再加了,所以不会超过200。防御不用加到太高,能让对面打不动就不用再加了,所以不会超过100。
枚举攻击和防御,就能算出战斗时长,进而得出需要的血。所有价格取最优解就好了。
那些攻击只枚举到110的闹哪样= =……HP只枚举到100的又是闹哪样= =……表示实在不太能理解为啥Hack能这么多……
而且这题前十几个过pretests的都fst了……囧……
代码:http://ideone.com/98ZQXR
(C++,527B)


487B/488D Strip

(本来这个位置是一个挺有意思的构造题……然后被Maxim换掉了……)
(因为Maxim说不能只有构造和DS……)
(于是就换了半道DS过来了……)
题意:
一个长为n的数组要切成若干条线段,要求每条长度至少为l,并且极差(怎么又是极差)不超过s,问最少切多少段。
n,l≤10^5,a_i,s≤10^9。

题解:
考虑动态规划:dp[i]表示长度为i的前缀最少要切成的段数,那么dp[i]=min_{j=left(i)-1}^{i-l}dp[j]+1,其中left(i)表示以i结尾的一段,开头最早可以出现在哪里。这个方程应该是显然的。
作为Div.1的选手,显然能发现left(i)是可二分的,二分以后变成了RMQ问题,开个ST表就好了。然后快速算dp[]发现还是个RMQ(注意ST表是可以支持在末尾插入元素的),于是3个ST表就能解决了。O(n log n)。
当然线段树大法好,O(n log^2 n)也很快。当然也可以优化成一个log的。
当然也可以用单调队列优化成不用log的……
总之想到了dp,而且不是暴力应该都没问题的。

Egor15分钟怒拿fb。
不过这题还是有两个小坑……
有些单调队列的写法在n<l的时候会挂……233
有些写法在-1000000000 1000000000这样的数据会integer overflow……

线段树(两个log)代码:http://ideone.com/htNTum
(C++,1.58K)
ST表(一个log)代码:http://ideone.com/m3Tofd
(C++,1.67K)


487C/488E Prefix Product Sequence

(这题本来有个很玄乎的题面被Maxim怒砍掉……555)
(现在看看幸亏砍掉了,要不然这题过的人更少……)
题意:
找一个1..n的排列,使得它的前缀积在mod n意义下是一个0..n-1的排列。
n≤10^5。

题解:
我先说说我第一次看到这题的想法吧。
首先第一眼能想到a[1]=1,a[n]=n,这个是显然的否则前缀积最后就要出一堆0。
然后就发现了前缀积的倒数第二个元素一定是(n-1)!,这个mod n=0!除非n是质数!
那么合数无解,质数有解,1特判。
问题来了,质数的解怎么造呢?人肉暴搜2 3 5 7发现前缀积居然可以是[1,2,...,n-1,0]耶!
暴搜了一下11也没问题……然后发现卧槽这么简单的结论……
于是跟trz讨论了一下……被告知少考虑了一个4……
二!三!三!
后来排难度的时候,就决定把这题放到C,而且pretest不给4不给1……
要不然这道题怎么能值1500分!
比赛的时候……rng_58怒拿fb……
值得一提的是,Egor40分钟过了这道题,然后秒锁(没判4!),
然后想象一下他当时看别人代码的心情……233

解法1:
好像上面说完了……
1和4特判,合数无解,质数这么构造解:
a[1]=1,a[n]=n,a[i]=i*(i-1)^(-1) mod n。
代码:http://ideone.com/N0VZDQ
(C++,781B)

解法2:
1和4特判,合数无解……
但是如果被样例带跑了怎么办?样例的n是7,答案是[1,4,3,6,5,2,7]。
先想想如果这题不是前缀积而是前缀和怎么办?易证对于n是奇数则无解,偶数那么解很好构造,比如6的答案就可以是[6,5,2,3,4,1]之类的。
原题里面n是质数,那么就可以找到一个原根g。然后我们就发现问题被转化成了n=偶数时候的前缀和问题!
暴力找个原根然后乱搞就行了。
代码:http://ideone.com/jWFIi5
(C++,1.64K)


487D Conveyor Belts

(这题是唯一一个没有大改动的题……)
题意:有一个n×m的矩形地图,每个格子写着"<^>"之一,一旦进入一个格子就必须顺着箭头走直到走出地图或者死循环。现有q次询问,每次可以修改一个字符,或者查询某个位置的目标点(或输出死循环)。
n≤10^5,m≤10,q≤10^5,修改次数p≤10000。

题解:

解法1:
给地图水平分块,对于每个格子处理出走出当前块的第一个点。
每次询问用这个预处理结果加速模拟就好了,每次询问暴力重构当前块。
设块大小为S,那么每次修改是O(S),每次查询O(nm/S)。总时间O(pS+qnm/S)。
取S=O(sqrt(qnm/p)),总时间O(sqrt(pqnm))。
代码:http://ideone.com/wxbzk3
(C++,1.55K)

解法2:
离线,对询问分块,每S个修改分一块。←请仔细看这句话
对于每一块的开头,暴力处理出此时除了将要被这一块的修改影响的点的所有点的目的地。(好像有点长,仔细看看)每个目的地可以是:地图边界外,死循环,或者是一个将要被修改的点。
对于每个查询,用这个预处理表加速模拟。每次对于每个特殊点只会经过一次(否则就是出现了死循环),每次查询的时间是O(S)。
所有预处理表的总时间是O(nmp/S)。总时间O(qS+nmp/S)。
取S=O(sqrt(nmp/q)),总时间O(sqrt(pqnm))。

解法3:
线段树大法好!线段树维护行,每个区间记录最后一行的m个点的走出这个区间的目的地,两个区间可以O(m)合并,叶子可以O(m)计算。当然实在是懒的话写O(m^2)也没问题。
每次修改O(mlogn),每次查询O(logn)。
总时间O(nm+qlogn+pmlogn),写的不好可能还要带一个O(pm^2)。
代码:http://ideone.com/mnFx2A
(C++,2.27K)

Bonus:
如果字符集有"v"怎么办呢?可以在较长边上反着走了。
解法1依然适用,但是每次查询用时需要额外乘m,所以总时间要额外乘sqrt(m)。
解法2很神,根本没有用到“没有v”这个条件,管你什么字符集,加多少个方向都不会有问题。
解法3需要做一些大修改,需要再记录第一行的m个点的目的地才能进行合并,而且每次查询的时间还要乘m,所以略拙计。


487E Tourists

(trz出的“裸模板题”……)
题意:给n点m边无向连通图,点上有权。q次询问,每次可以修改一个点权,或者查询从a到b的所有简单路径的点权最小值的最小值。
n,m,q≤10^5。

题解:
一句话,双连通缩点建树后当QTREE做。
anta当场1.5hAC写了15k代码简直吓傻+跪傻。
没了?没了。
真没了?细节问题一大堆。
首先割点归谁管?割点自己显然是要在树中的,但是也要在他所属的块里有所体现。如果改了个割点,怎么更新它相连的块?暴力更新会被菊花图卡掉。
anta为此写了个根号算法……由于数据没有专门卡根号所以跑的很快。
其实只需要割点的信息只在它的父亲存就好了(如果父亲是块)。每次树上查询的时候,如果发现LCA是块,而且这个块的父节点还是个割点,那么要把割点的答案也算进来。
没了?没了。
真没了?建树不错就行了。
我为了不错,强行让割点成为根,强行让割点的孩子都是块,让块的孩子都是割点。这样就需要把所有块都建出来,即使块只有一两个点或者全是割点也要建。
没割点的情况还要再写个特判……每个块里随便用个什么比如multiset<int>之类的维护块内最小值就好了吧。
树上可以LCT搞。
当然,线段树大法好,轻重链剖分一下上线段树就行了,线段树还能顺便把块内最小值神马的也搞定了。(如果你要用LCT维护块内最小值当我没说= =)
剩下的问题就是保证你的Tarjan模板是对的……
然后就可以愉快地AC了!截至发稿一共有5人AC了这道题!嗯,耐心一些还是不难的。
但是我们好像忘了证明算法的正确性……我们需要证明一定能找到这样一条简单路径。好办!建网络流图,从中点开始流2的流量,如果能流到起点和终点各1的流量就没问题了!注意要给点容量限制。
我们可以证,在双连通图里面是能找到这样的流的!只需要证最小割大于1就行了。这个还是比较容易的。
最后考虑数据怎么造。
链啦环啦随机树啦菊花啦三角套三角啦太阳形啦随机仙人掌啦之类的,一共是26个pretest,58个test。
最最坑爹的是写暴力……
我写了个状压dp,trz写了个网络流,各种stress。
(网络流居然比双连通+树上暴力还慢233)

轻重链剖分线段树代码:http://ideone.com/U3eCEk
(C++,6.73K,带注释)

LCT代码:http://ideone.com/73dAzW
(C++,6.88K,带注释)


  评论这张
 
阅读(286)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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