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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POI16 补充  

2013-08-14 15:41:42|  分类: POI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
由于闲得没事做。。。所以重新滚回来玩了
果然半年过去一点长进也没有的说
。。。。。。。。。。。。。。。。。。。。。。。
最开始做的是stage2 的Isles in a Triangular Grid
怎么讲呢?没有想象中的那么难。。反而是我自己傻逼将代码写了几遍。。。
其实这题就是个模拟题。。。
我的做法:
将点按照一种方式标号。。。随便怎么标都行。。
询问有两种,一种加点,一种问大小为N的形状的个数。。要求使用一种最小表示法。。。
那么代码就非常裸了的说。。。首先最小表示法是顺时钟方向表述了轮廓线。。我们模拟走一遍取出轮廓线上的点,那么边也出来了。。。然后就是在轮廓线上相邻两点之间加入一个点。。。怎么看怎么好些吧。。。最后有了轮廓线上的点,我们要还原回去。。这个也是模拟走一遍即可,用set直接去掉重复,输出,完毕。。
我都不知道我之前纠结那么久究竟是在纠结啥

1.1 Fire Extinguishers
其实这题很简单啊。。。。从深度大的往深度小的考虑,如果没覆盖,就选个深度最小的覆盖它,然后用这个尽可能地覆盖深度深的。。。贪心真的很裸很裸。。但是不知为何当初纠结那么久都没纠结出来,我真的还是太弱了。。
code:http://paste.ubuntu.com/5987913/

说说剩下的题吧。。
题意:平面上的一个凸多边形,点两两连直线,直线可走,然后有m(m<1000000)对点之间的直线被删除,求此时从点1到点n的最短路径。。。你可以走直线或者直线的交点。。
此题关键是看题啊,由于没注意到1和n是相邻的,纵使一看到题就知道是半平面交,却苦于无法转化,但是等到看到被黑体加粗的相邻二字,于是顿时变成简单题了。。主要是半平面交好久没写,顺理成章地被卡了下精度,不过也在预料之中。。。

题意:大概就是猜数字游戏,不过你现在是问是否比某个数要大,如果回答yes付出a的代价,否则付出b的代价,用最少代价猜出这个数。。n<=10^9,a,b<=100000,交互题
题解:其实蛮简单的题了。。注意到ab很小。。是的,所以总代价很小。。另外观察到猜数字的次数不会太多。。至少<=min(n,30*max(a,b)),而且范围越大,代价越大,具有明显的单调性。。。所以可以将状态反过来,代价为a能够确定多大的范围。。于是此题解决。。

题意:太纠结了,直接复制bzoj——版权什么的见鬼去吧
POI16 补充 - hzaskywalker - Yavin(某沙茶的代码库)
保证所有的code的长度之和<=10^8。
题解:
费了我好多时间的题。。。当然我智商低是主要原因。。想通了其实本题是很简单的
题目中的大部分条件可以合成一句话,给定一个01串,解码方式是唯一的。。
我们观察下什么code不是同步编码,其实只有两种情况:
ccccbbbbb
   aaaaddddd
(即这个串的前缀是某个串的后缀,且某个串又是另一个串的后缀,且这个串余下的那个串不能解码完毕)
或者
ccccbbbbb
   aaaaaaaaaaaa
(直接跨越了,这个串成为了另一个串的子串,而且不是后缀,其余条件同上)
这两种。
然后有个重要性质:
我们可以暴力处理出一个code中所有被匹配了的子串——因为从任意位置开始只有一个匹配方法。。。总方案数是串的长度。。
好了,我们首先处理出某个串的前缀是否是另一个串的后缀(由于可以混杂别的完整的串,所以得dp一下)。。这裸的fail指针吧。。
然后我们用这个串来排除其它串——那么其它串的前缀一定是这个串的后缀。。。我们暴枚——因为它的后缀数不会超过串的长度,沿着fail走也只会走串长步。。于是就判断掉了。。至于要求其它串的后续不能匹配完。。。那么我们可以假定匹配完了,那么一定是从最后开始往前数。。。用个类似dp的东东,处理出某个后缀是否能够匹配完。。即可。
至于第二类,是否是某个东西的子串,我们也用某个串来排除。。。这个其实和第一个差不多,而且还简单些。。
复杂度就是O(S)。。大概能承受的范围。
  评论这张
 
阅读(333)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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