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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POI16 stage1  

2013-05-02 18:46:38|  分类: POI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
终于重新回到poi了,想当初,打开题目,结果发现第一题都不会,彻底被打击信心,于是不得不放弃。
如今的我已经不再是当年的我了,碰到不会做的题目是不会去碰的,于是成功将第一题无视,将剩下的四道题成功解决!

放弃。

博弈,不知道为什么是对的,暂时也不管了。

题意:给定两个序列,定义一个函数W(x),表示x序列中出现过的数的集合,定义prefix(x),表示x的最长的前缀使得W(x')!=W(x),同理定义suffix(x)。
两个序列相等当且仅当:
W(x)==W(y) && (|W(x)|==1 || (prefix(x)与prefix(y)相等,suffix(x)与suffix(y)相等))
给定序列x,y(x,y<=10^5),其中每个数都小于等于100,判断是否相等。
题解:
判断两个东西相等,自然想到了hash,我们对于一个串进行hash,就是将个序列的prefix和suffix所得的hash值加上suffix与x相差的那个元素组合起来,也就是将整个过程hash起来,如果hash相同那么两个序列自然就是相同的。
接下来就是求hash。很容易想到每次都减小了一个元素,那么总状态数是O(nk)的,利用一下各种单调性可以使得记忆话搜索的时间复杂度变成O(nk),空间复杂度O(nk),但是这个过不了的。。。因为poi只给了64MB。
看了下题解,发现可以非递归的!
记l[i][j],表示左端点是i,包含了j个元素的区间是哪个。对于特定的j,我们可以O(n)扫描处理出这个,然后注意hash[i][j]只与hash[i][j-1]有关,所以可以滚动数组求这个hash值了。膜拜了。

题意:经典题,通过交换花费最小的代价将使一个序列按照一定顺序排列。代价为交换的两个数的和。
题解:循环节考虑。

题意:平面上p个点(p<=10^5),和z(z<=10^5)组询问,每次询问给出两个点,回答:离点1最近的点有多少,离点2最近的点有多少,和两个点一样近的点有多少。采用曼哈顿距离。
题解:
很是蛋疼的题目,被dcrow大神评价为:有写的必要么?
不过看在我写了一半的份上还是最后将它写完了。成就感满满的说。
好吧,我们考虑一个询问:(x1,y1)(x2,y2)
假定x1<x2 && y1<y2
那么就有三种情况
POI16 stage1 - hzaskywalker - Yavin(某沙茶的代码库)
分别对应于组成红色部分 的两个矩形和一个梯形。这些里面的点离上面那个黑点更近,可以推推公式。
回答这些询问都是可以离线+线段树(平衡树)解决的。
但是关键是,这只是其中一种情况,虽然其它情况都可以转化为这种,但是转化起来格外的麻烦的说。。。
慢慢写和慢慢想吧,写代码的时候不要分情况讨论,而是将所有其它其它情况归类为这一种。
此外还有两个特殊情况不能归类为这一种:
1.询问的点有一个坐标相同
2.x1-y1==x2-y2,这样区域只有一个矩形+梯形了。
不过都是挺好解决的。
  评论这张
 
阅读(457)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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