wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

[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

[vijos1459][车展]

题目链接思路首先可以证明当这个高度是中位数的时候耗费时间是最少了。所以可以\(n^2log(n)\)用一个treap预处理出每个区间的中位数。然后就是知道了中位数怎么计算答案的问题。然后发现暴力n*m的扫能过而且跑的还不慢但是作为一个正直善良的OIER我还是用\(n^2log(n)\)...

2018-12-02

0 366

[vijos1459][车展]

题目链接思路首先可以证明当这个高度是中位数的时候耗费时间是最少了。所以可以\(n^2log(n)\)用一个treap预处理出每个区间的中位数。然后就是知道了中位数怎么计算答案的问题。然后发现暴力n*m的扫能过而且跑的还不慢但是作为一个正直善良的OIER我还是用\(n^2log(n)\)...

2018-12-02

0 475

[luogu1486][郁闷的出纳员]

题目链接思路这个题其实就是对于treap中的删除操作进行一些修改。自己yy了一种做法。就是在删除的时候，如果要删除的数比这棵子树的根大，那么就把根变成根的右孩子，这样就相当于删除了整棵左子树和根节点。然后重新维护一下siz，并且维护一下平衡性就行了。竟然把rotate函数写错了。调了30m...

2018-12-02

0 0

[luogu1486][郁闷的出纳员]

题目链接思路这个题其实就是对于treap中的删除操作进行一些修改。自己yy了一种做法。就是在删除的时候，如果要删除的数比这棵子树的根大，那么就把根变成根的右孩子，这样就相当于删除了整棵左子树和根节点。然后重新维护一下siz，并且维护一下平衡性就行了。竟然把rotate函数写错了。调了30m...

2018-12-02

0 389

[luogu2286][宠物收养所]

题目链接思路比较裸的一道平衡树的题。用一个变量S来表示当前树的情况，当S为负数时树内为宠物，当S为正数时树内为人。然后每次分情况讨论一下。如果树为空或者是与来的东西(人或宠物)与树内存的相同。那么就无法领养，直接将这个东西扔到树里。否则就从树里面找一个与当前值最接近的数字，然后统计进答案。 ...

2018-12-01

0 0

[luogu2286][宠物收养所]

题目链接思路比较裸的一道平衡树的题。用一个变量S来表示当前树的情况，当S为负数时树内为宠物，当S为正数时树内为人。然后每次分情况讨论一下。如果树为空或者是与来的东西(人或宠物)与树内存的相同。那么就无法领养，直接将这个东西扔到树里。否则就从树里面找一个与当前值最接近的数字，然后统计进答案。 ...

2018-12-01

0 379

[luogu1503][鬼子进村]

题目链接思路将哪些村庄已经被摧毁了放到treap里。查询的时候如果当前村庄已经被毁了，那么就可以直接输出0.不然就输出这个村庄的后继-前驱-1。原因显然代码 #include<cstdio> #include<iostream> #include<cstd...

2018-11-29

0 432