wxyww

分类

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

/ 注册

全部文章（共395篇）

fhq_treap 小结

简介是一种非旋平衡树。在学习这篇文章之前，还是先学习一下普通吧优点相比于普通的，它可以处理区间操作。相比于，它简洁易懂，代码也较短。缺点要比和慢基础操作最基本的两个操作就是分裂和合并。分裂即把一个分为两个。有按照权值分和按照大小分两种方式。具体方法:比着代码划拉划拉就知道了(懒)。...

2019-07-19

0 710

笛卡尔树

定义所谓笛卡尔树，就是将给定的个二元组建成一棵树。使得如果只关注，那么这是一个堆。如果只关注,那么这是一棵二叉搜索树。有没有很像。与不同的是，笛卡尔树是可以在时间内构建的。而且如果给定key,那么是可以被卡成一条链的。构造以小根堆为例。借助栈来完成。先按照val从小到大排序。然后用...

2019-07-19

0 704

noip2018游记

Day0 路上紧张到不行。特别担心今年会挂掉。 Day1 一塌糊涂T1似乎是积木大赛的原题。当时只用了个分治的做法在洛谷上水过去了。考场上发现能被卡成T2看了很久只好写了个exgcd，最后10分钟发现是个完全背包。哎。写完过不了大样例啊啊啊。果断删掉，又不小心把iostream库改了，只好用g++手...

2019-07-19

0 455

SDOI2019游记

Rand1 Day0 一大早就起床，结果忙活了整整一上午。12：20从gryz出发，路上发现把耳机和笔忘另一个背包里了(都怪老爸非得让我换背包)，15：30差不多就到山师了。山师也是蛮漂亮的，花开得挺好。到处是牵着手的小情侣。啧啧啧~。恰逢清明，给他们烧柱香吧一时间难以表达内心的欢愉(第一次带着这...

2019-07-19

0 1497

李超线段树

功能李超线段树资瓷以下两种操作: 1.在二维平面内插入一条线段2.询问与直线相交的线段中，交点纵坐标最大为多少。原理结点李超线段树的每个节点，都维护这一个优势线段。这个优势线段使得该节点所维护区间的中点在该优势线段上最大。修改考虑如何维护上面的结点呢。分三种情况讨论：1.该区间无优势...

2019-07-19

0 1091

CF1195 解题报告

A 题意有种饮料，每两个种类相同的饮料组成一组。每种饮料都有无限组。有个同学。每个同学有一种想喝的饮料。选择种饮料。问最多能有多少个同学喝到自己想喝的饮料。 solve 统计出每种饮料有多少个同学想喝。找出有奇数个人喜欢的饮料个数。答案就是 code /* * @Author: wxyww * ...

2019-07-19

0 585

vijos2055 移动金币

题目链接思路首先这是一个阶梯博弈。我们将金币两两组合，如果对方移动前一个，那么我们把后一个移动相同的距离，局面相当于没有变化。如果对方移动后一个，就相当于\(NIM\)游戏中，取走了一些石子。所以这个游戏也就是金币两两组合后，有\(\lceil \frac{m}{2}\rceil\)...

2019-05-15

0 578

POJ2096 Collecting Bugs

题目链接题意有n个bug和s个系统。每天会等概率的在某个系统中找一个某一个bug。问找到全部n个bug并且在每个系统中都找到bug的期望天数。思路 f[i][j]表示在j个系统中找到了i个bug的期望天数。某天有四种可能： 1.在新的系统中找到新的bug，概率为\(\frac{(n...

2019-05-14

0 474

noi.ac89A 电梯

题目思路首先按照\(t\)排序！！！！首先考虑一个暴力\(dp\) 用\(f[i]\)表示前\(i\)个人到达地点所需要的时间。那么就有如下的转移 \[f_i = min_{1 \le j \le i}(max(f_j,t_i) + max\{w_{j + 1} ... w_...

线段树动态规划dp

2019-03-24

0 501

CDQ分治

$cdq$分治主要思想就是将操作离线下来，然后分治之后统计二分之后，左边的修改对于右边查询的贡献。可以顶替很多复杂的数据结构。学会下面这几类问题差不多就会$cdq$了。个人认为看代码比较容易学。二维偏序先考虑这样一类问题给出n个二元组$(a,b)$，求出有多少对$i,j$满...

CDQ分治

2019-02-15

0 439