yizimi远欣

题解

其他(14) 算法及模板(3) 课内(2)

/ 注册

全部文章 / 题解（共39篇）

题解 P3835 【【模板】可持久化平衡树】

就是可持久化后的普通平衡树嘛（逃题目描述不写了（懒了这里是题目主要思路：FHQ Treap + 可持久化普通FHQ Treap加上一点可持久化的东西如下：(打上注释的代码是可持久化的特殊操作) inline int merge(int x, int y) { ...

可持久化平衡树 FHQ Treap

2018-12-06

0 452

题解 P4146 【序列终结者】

题目描述给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作：将[L,R]这个区间内的所有数加上V。将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。求[L,R]这个区间中的最大值。最开始所有元素都是0。输入输出格...

平衡树 FHQ Treap

2018-12-05

0 630

题解 POJ1151【Atlantis】

题目大意给你n个矩形，让你求所有矩形覆盖的总面积，重叠的地方只算一次输入格式输入的第一行包含一个整数n，表示可得到的地图数目。以下n行，每行描述一张地图。每行包含4个整数x1,y1,x2和y2（0≤x1＜x2≤30000,0≤y1＜y2≤30000）。数值（x1,y1...

线段树扫描线

2018-12-02

0 510

题解 SP4487 【GSS6 - Can you answer these queries VI】

题目大意给出一个由N个整数组成的序列A，你需要应用M个操作： I p x 在p 处插入一个元素 x (解释：这里插入是p - 1和p 之间插入) D p 删除p 处的一个元素 R p x 修改p 处元素的值为 x Q l r 查询一个区间[l,r]的最大子段和 N <= 1...

FHQ Treap 平衡树

2018-12-02

0 425

题解 P1967 【货车运输】

题目描述 A国有n座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。输入输出格式输入格式：第一行有两个用一个空格隔开的整数 n,...

Kruskal 最小生成树 Kruskal重构树 LCA

2018-12-02

0 680

题解 P1441 【砝码称重】

题目描述现有n个砝码，重量分别为a1，a2，a3，……，an，在去掉m个砝码后，问最多能称量出多少不同的重量（不包括0）。【数据规模】对于20%的数据，m=0；对于50%的数据，m≤1；对于50%的数据，n≤10；对于100%的数据，n≤20，m≤4，...

搜索剪枝

2018-12-02

0 585

题解 P3128 【[USACO15DEC]最大流Max Flow】

题目描述 FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。 FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运...

树上差分 LCA

2018-12-02

0 465

题解 P1949 【聪明的打字员_NOI导刊2011提高（10）】

题目描述阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：swap0,swap1,up,dow...

队列搜索模拟

2018-12-02

0 609

题解 P1966 【火柴排队】

题目描述涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为： Σ(\(a_i\) - \(b_i\))² 其中a_i表示第一列火柴中第 i 个火柴的高度，b_i表示第二列火柴中第 i 个火...

线段树权值线段树

2018-12-02

0 708

题解 P1895 【数字序列】

题目背景查找数字题目描述在下列的无穷数字序列1121231234123451234561234567123456781234567891234567 8910123456789101112345678910......中，查找第i个数字。输入输出格式输入格式：...

STL

2018-12-02

0 429