wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

[luogu5077][Tweetuzki 爱等差数列]

题目链接思路数学题首先列出等差数列求和的式子。 \[S = \frac{(n + m)(n - m + 1)}{2}(n为末项，m为首项)\] \[S * 2= (n + m)(n - m + 1)\] 若想让m更小，那么肯定要让等差数列中数字的数目更多。也就是让\((n - m + 1)...

2018-12-10

0 0

[luogu1110][报表统计]

题目链接思路 set+map+优先队列就可以水过去。可以发现，每插入一个元素，都会使得操作2中原来相邻的那个差值消失，然后多了两个新的差值。对于新的差值，只要直接扔到优先队列里就好了。那么删除呢。可以用map记录一下当前元素被删除了多少次。然后查询的时候将被删除的跳过即可。对于操作3，只要将插...

2018-12-09

0 455

[luogu1110][报表统计]

题目链接思路 set+map+优先队列就可以水过去。可以发现，每插入一个元素，都会使得操作2中原来相邻的那个差值消失，然后多了两个新的差值。对于新的差值，只要直接扔到优先队列里就好了。那么删除呢。可以用map记录一下当前元素被删除了多少次。然后查询的时候将被删除的跳过即可。对于操作3，只要将插...

2018-12-09

0 374

[luogu3391][文艺平衡树]

题目链接思路 splay区间操作的裸题。假如要对l-r这段区间操作，那么就先把l-1伸展到根节点，然后把r +１伸展为根的儿子。这样r + 1的左儿子就是要操作的区间了。只要在上面打上标记，以后每次查询的时候pushdown一下。然后对于l-1和r+1节点可能不存在，所以可以放两个标兵元素...

平衡树 splay

2018-12-09

0 444

[luogu3391][文艺平衡树]

题目链接思路 splay区间操作的裸题。假如要对l-r这段区间操作，那么就先把l-1伸展到根节点，然后把r +１伸展为根的儿子。这样r + 1的左儿子就是要操作的区间了。只要在上面打上标记，以后每次查询的时候pushdown一下。然后对于l-1和r+1节点可能不存在，所以可以放两个标兵元素...

平衡树 splay

2018-12-09

0 348

[Splay][学习笔记]

胡扯因为先学习的treap，而splay与treap中有许多共性，所以会有很多地方不会讲的很细致。关于treap和平衡树可以参考这篇博客关于splay splay,又叫伸展树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert...

2018-12-09

0 433

[bzoj1116][POI2008][CLO]

题目链接思路可以先考虑一棵树如图，如果是一棵树我们肯定会想这样子做，但是现在根没有入度。所以现在需要再加入一条边使他变成基环树。假如现在加入一条边\(3-2\)，那就会出现一个3-1-2-3的环。然后以这个环上的点为根，就可以找到很多棵满足条件的树可以发现，这样就解决了根没有入度的...

2018-12-02

0 491

[bzoj1116][POI2008][CLO]

题目链接思路可以先考虑一棵树如图，如果是一棵树我们肯定会想这样子做，但是现在根没有入度。所以现在需要再加入一条边使他变成基环树。假如现在加入一条边\(3-2\)，那就会出现一个3-1-2-3的环。然后以这个环上的点为根，就可以找到很多棵满足条件的树可以发现，这样就解决了根没有入度的...

2018-12-02

0 517

[luogu4309][最长上升子序列]

题目链接思路因为这些数字是从小到大加进去的，所以以当前数字结尾的最长上升子序列可以从前面位置的任何一个数字转移过来。所以只要能知道每个数字最终位于哪个位置就行了。没想到出了treap还有什么办法求出来这个序列。看了眼题解发现用vector的insert直接模拟就能过。(纳尼？)这个函数不是...

2018-12-02

0 0

[luogu4309][最长上升子序列]

题目链接思路因为这些数字是从小到大加进去的，所以以当前数字结尾的最长上升子序列可以从前面位置的任何一个数字转移过来。所以只要能知道每个数字最终位于哪个位置就行了。没想到出了treap还有什么办法求出来这个序列。看了眼题解发现用vector的insert直接模拟就能过。(纳尼？)这个函数不是...

2018-12-02

0 490