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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 187 Div 1 & ABBYY Cup 3.0 & Codefoces 188 Div 1  

2013-06-16 09:35:48|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
不想写题解了。。。
T_T,有时间再补吧
========================================================
实际上。。。是由于法法塔太沙茶了导致题都改不完啊。。
今天才把坑给挖好。。。我真心太弱了
=======================================================
187的题没啥意思。。
特别是E题纯粹的傻逼题,明明是n^2的算法然后将n设置为100000故意诱惑他人。。无力吐槽
反而是D题稍稍有点意思:
求两条直线与x轴分别为45和135度的直线,使得给定点集中离这两条直线距离最远的点的距离最小。点到两条直线的距离是点到这两条直线上的点的所有曼哈顿距离的最小值。
显然将坐标变换(x,y)->(x+y,x-y)
那么其实是求点a,b,使得max( min( abs(a-xi),abs(b-yi) ) )最小。
二分答案为r。。如何判断r呢?我们先将点按照x排序。。枚举abs(x-a)<=r的点——肯定是个连续区间,而且一定是尽可能的覆盖,枚举这个区间,然后O(1)判断剩下的点的能够覆盖y坐标的区间有交——这个非常简单啊。。。
========================================================
ABBYY CUP的好题蛮多的说。
题意就不写了吧

C题:
我觉得这题非常吊炸天啊。。当时比赛的时候有人问我然后随意蒙了个费用流然后就过了!!
当然得证明的啦。。
具体而言,最开始肯定是个匹配,我们假定最终是怎么匹配我们已经知道了。。
那么考虑该怎么置换颜色才能使得改变量最少。。
那么问题转化为一个二分图,现在有了n个匹配。。然后修改最少的颜色。。使得每个颜色的点的个数不变,而且相同边的颜色相同。我们将两边颜色相同的边去掉(改变这些的颜色显然得不偿失),接下来的边颜色各不相同。。记边数为m
显然答案>=m
接下来构造使得答案为m的方案。
我们在相同颜色的点间连上虚边。。
这样每个点的度数是2。。
那么就只有很多虚实边交替的环。。。我们将虚实边交换。。这样得到的新的方案的改变量是m,于是得到答案。。
那么给定一个匹配,答案就是没有颜色不同的边的数量。。
我们要找颜色相同最多的匹配——除了最大匹配还有??

D题:
关键就是要确定一个置换是否能够得到。。
我们将置换拆成轮换。。
接下来就是判断轮换是否能够达到的充要条件。
利用这个条件dp打表找到规律

条件就是——轮换中1的个数不能超过2.
具体证明在我的代码中有
/*
每个循环中最多有两个1
其实我也不知道对不对啊
除掉所有只能是1的。。
ai->aj
aj为1
那么设aj->ak
那么ai得变成ak
这样ai最后必须有一次交换
即ai的交换次数为1。。的递归子问题,由于只是缩点,所以依旧是个轮换。
最终应该会变成一个对换
由于1的数目不会改变
那么。。。
1的数目最多为2
由此构造出答案。
我觉得我吊炸天了
*/


E题傻逼数据结构题。

F题图像识别。。。纠结了半天,WA了好多次。。最后看了题解。。我tm是个,b

G题吊炸天
题意是给定n个串。。求出出现在这n个串中li到ri次的不同的子串个数。。
这题用后缀数组写的话。。。似乎挺暴力而且代码页不长???大雾。。感觉好复杂的样子。
所以最后放弃了。。果断这是看到郁东风大神考场上怒A了。。
赶快膜拜,结果发现写的是后缀自动机。。。吓傻了。。
仔细一看,原来如此。。
给定n个串。。我们可以建出其后缀自动机。。
由于SAM的构造算法是增量。。那么我们可以在任意一个地方插入。。就像trie一样。。于是变成了一个非常裸,但是非常神的题了。
==================================================
188的题有点,啊。。
从tourist滚出+sevenkplus滚出说明了这套题是非常不好的~
这套题除了B题那个暴力可以跑过外。
D题就是个傻逼题。。。暴力sg无话可说。。

但是problem C就是不错的题目
n个点的图,每个点有个统一的容量v,现在每个点都有点东西。。
你要通过边重新分配这些使得每个点达到目标容量——要求操作次数不超过2*n^2
感觉限制条件很奇怪。。但其实是可做的。。
首先——一切图都是树——本题明显是构造。。
图的核心是棵树
我们对于每个连通块将树搞出来。
那么我们要证明,只要保持容量不变,就一定可以构造出来??
这个其实非常简单。。我们要将多出了移动到少了的里面。
那么我们枚举每个点,将这个点多出的全部移动到少了的里面——这个其实非常容易完成的——如果某个子树有欠缺,就放心的移动即可——这是在没有点容量限制的情况下——否则,如果被某个点堵住了,那么就先移动那个点的容量,再用自己的来补充——大概就能在2*n^2步之内跑出来了。
tourist似乎没开long long挂了哇哈哈哈

E题也是个构造。。
大概意思是网格图。。有影子和一个人。。人四连通地移动,人怎么走,影子怎么走。。但是当影子碰到障碍的话就不能移动,你要使得人与影子重合。。有m(m<=400)个障碍,障碍的坐标范围在[-100,100]之间。。
题解:
其实这题的题解很厉害——膜拜xiaodao神
注意到一个很重要的构造方法:如果人和影子远离了障碍的话,只要有障碍就能很容易地移动到一起。。我们只需让人靠近影子,那么显然影子靠在某个障碍上,然后移动人使得某个坐标相等。。。接下来靠在另一边,使得两个坐标都相等。。
那么考虑让影子和人怎么移动。。
题解中的方法:
我们一直让人沿着到影子的最短路走。。如果影子走了一步,那么把影子的这一步添加到人的操作序列中——直到人与影子的重合或者远离了障碍。
远离了障碍的话就可以构造。。
否则得到答案了。
关键是为什么不会死循环??
人往影子走这个向量只会一直重复,按照一定方向的话就会远离障碍了。。。否则,影子没动,那么影子与人的距离减1,离答案更近一步了!
就此完毕。。由于我比较逗,错了好多次
  评论这张
 
阅读(764)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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