wxyww

未归档

精品(28) 题解(65)

/ 注册

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

[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

[luogu1503][鬼子进村]

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

2018-11-29

0 377

[luogu3369][普通平衡树]

题目链接思路模板只是有几个容易出错的地方第45行容易忘记第54行里面的cnt--和siz--容易忘记第56行是根据id判断不是val 第60行siz--容易忘记第64行是siz+1不是siz+cnt 第77行和82行等于的情况容易忽略代码 #include<cstdio...

2018-11-29

0 433

[luogu3369][普通平衡树]

题目链接思路模板只是有几个容易出错的地方第45行容易忘记第54行里面的cnt--和siz--容易忘记第56行是根据id判断不是val 第60行siz--容易忘记第64行是siz+1不是siz+cnt 第77行和82行等于的情况容易忽略代码 #include<cstdio...

2018-11-29

0 0