发表于 | 更新于 | 分类于 ， ， ， | 评论数：
UVALive5879 题意： 就是规定了一个发牌和收牌的规则。 总共N个人玩游戏，有5*N张牌（分别是1,2,….5N）, 按照规则发牌，如果有一个人拿到了1,2,3,4,5的牌，这个人就赢了，否则进行收牌，然后再来。 要预测是第几个人赢，，以及第几次赢。 就是发牌规则和收牌规则得到一个映 ...
阅读全文 »

发表于 | 更新于 | 分类于 ， ， ， ， ， | 评论数：
ZOJ2112 有点大材小用了。 替罪羊树套splay的话，可以在线搞，而且支持插入删除等操作。 本题只有查询和修改操作。 完全可以把替罪羊树换成树状数组或者线段树了。 其实这里用替罪羊树，也没啥作用，重构操作都没有。就是当成线段树用的。 比较容易MLE。 Dynamic Rankings ...
阅读全文 »

发表于 | 更新于 | 分类于 ， ， ， ， | 评论数：
BZOJ3065 带插入、修改的区间k小值在线查询。 网上看的别人的做法确实没看懂， 然后自己想了一下，用替罪羊树套上splay去搞。 替罪羊树维护相对位置信息，然后每个子树用splay去维护值。 这样就可以查询一个区间 <= val的出现了几次。 替罪羊树重要的是不会旋转，维护起来很 ...
阅读全文 »

发表于 | 更新于 | 分类于 ， ， ， ， | 评论数：
UAVLive6045 题意： 给了二维平面上的N个整点（\(N \leq 50000\)）。每次操作给了点\((x_i,y_i)\),需要曼哈顿距离小于\(E\)的点进行一个变换。 输出最后的点的坐标，保证变换次数不超过50000. 这题做的方法比较多。 KD树的做法就是先进行坐标选择 ...
阅读全文 »

发表于 | 更新于 | 分类于 ， ， ， | 评论数：
链接： here 这题的做法比较多。 今天学习了cwj巨巨的替罪羊树做法，调试了一个下午，卧槽！ 替罪羊树的好处就是不需要旋转，这样的话，维护起来就很方便了。 Links: edward-mj Scapegoat-Tree 套了一个map, 然后就可以轻松搞定这个题了。！ 很优美的做法。 ...
阅读全文 »

发表于 | 更新于 | 分类于 ， ， ， | 评论数：
负责出了一场网络赛，勉勉强强算是顺利过去了，虽然产生了很多意外~~本场共有12道题，教练提供了3个题给我，学弟shumj出的1011的LCT。 然后本来这场是11个题的，开场前教练担心爆零的比较多，临时叫我加了一个水题，就是1012了。 搞完这场网络赛，估计被喷出翔了, 虽然有个别题我卡的比较紧，但 ...
阅读全文 »

发表于 | 更新于 | 分类于 ， ， ， ， ， | 评论数：
HDU4918 经典的树分治的题目。 进行点分治。 题意： 给一颗树，每个点有权值。 两种操作： 一种是把某个点的权值改为v. 一种是查询距离u不超过d的权值和。 树分治结合树状数组去搞。 树分治的关键就是每个点最多被logn个点更新到。 这样的话，就很容易搞了、 Query on the su ...
阅读全文 »
0%