题目
这套题做的很囧
第一题 题目没什么说的就是模拟 不过很麻烦
但是题目里的游戏很好玩 真的很好玩
第二题 一开始看像04年 ACM上海赛区的H题 田忌赛马 记得集训队资料里的解法是O(n^2)
但是发现 n<=
100000 后来发现这题与田忌赛马是不一样的
田忌赛马 是求最大|小分差 那么怎么贪心呢
以求最高分为例 提出一个策略：
设我方的选手集为A 对方为B
若Amax>Bmax
则A-=Amax,B-=Bmax ans+=2
否则 A-=Amin,B-=Bmax 如果Amin==Bmax ans+=1
下面是证明
若Amax>Bmax
假设有一种方案 使得Bmax不与Amax交战&得分>当前方案
设于Bmax、Amax交战的分别为a,b
则将Bmax与Amax交战 a与b交战 其余与该方案相同 易证此方案不亚于 该方案&此方案得分=原方案
若Amax<=Bmax 同上述方法可证 这里就不多说了
值得一说的是第4题 我想了2天 实在没有思路将一些想法记在下面并将它添加到未解决问题中
首先想到的是将它想LCA->RMQ一样搞出一个欧拉序列 通过维护这个序列解题
那么借助什么数据结构好呢 线段树？
这好像不可能 倒不是得到答案的问题
关键是每次更改都要不止更改一个或常数个
看来 搞成一个序列是没戏 那么仍保持树状结构呢
这回 更改时好办了 但怎么得到答案哪
我又标程 不过我这个人最不擅长就是读程序 但可以看出标程用到平衡树
实在是不会 等oibh好了到哪顶上问问应该会有结果幻灯片 20
posted on 2009-03-14 23:21
250 阅读(752)
评论(4) 编辑 收藏 引用 所属分类:
oi