over 3 years ago

起源

自从 考出翔之后就开始想要发狠搞学习啥的... 然后就做了最新的一套题... 然后就没有然后了... 突然有种做这套题虚度人生的感觉.

A, B太水不说

C

题意

给定若干个二元组 , 问有哪些二元组 使得存在一组 , 的值比其他的更优? (可能存在多个最优解, 这种情况也合题意)

思考

就只有这个题还是良心的送水了... 很显然想到把 画在二维坐标系内, 要求的就是下凸包的左半部分上的点了. 注意这个题可能有重点, 坑了我好久

D

题意

现给定一张无向图, 图中存在点权和边权. 点权有正有负, 边权全为正. 现在两个人开始玩游戏. 点, 点, 两人轮流操作. 每次操作每人选择一个数 . 把离他所处的点距离(定义为最短路)不超过的点点权拿走, 算进他的收益中间. 被拿走的点点权为0, 每次操作至少要拿走一个点, 当无法操作时游戏结束. 游戏结束后, 比较两人得分高低决出胜负平关系. 现问你先手是否有必胜策略. (点数不超过2000)

思考

这个题还是挺鬼畜的...感觉状态比较恶心之类的...

考虑到对于一个点, 到他的距离为, 到他的距离为ty. 我们把画在坐标平面上. 那么每次取相当于竖着画一条线, 把直线左边的点取走, 取也就是横着一条线把线下面的取走.

于是我们考虑 .令 表示还剩(i,j)右上角没选, 当前人的最大收益. 这个就很好转移了. 再搞搞后缀最大值之类的就可以实现了.

E

题意

对于一个0,1串s , 设它被0分成了若干个连续1的区间, 长度分别为 他的值定义为.
现在给你一棵树, 每次询问 , 对于路径, 若边权小于 , 定义权值为0, 否则定义权值为1. 那么对于构成的0,1串, 求他的值.

思考

离线的做法还是比较简单的, 把询问按边权从小到大排序, 边按边权从小到大排序, 一开始所有的边都是1. 每做一次询问把边权小于询问 的边赋值成0. 很明显这个状态满足合并, 我们链剖分上线段树即可.

在线的做法有点类似, 用主席树维护边权前缀的线段树. 询问的时候对于链剖分之后的每一个区间, 二分到主席树位置. 就可以做线段树访问了...

然而这个并不是很好写... 我为了寻求挑战性写在线做法一个下午毛都没有搞出来, 根本调不出来... 然后就弃疗了.

← NOIP2014 总结 祝贺我的好友开了个新的博客 →
 
comments powered by Disqus