tyvj专题

BZOJ 3224 Tyvj 1728 普通平衡树(权值线段树)

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3224 题目大意：您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，

tyvj 1305 最大子序和 (dp 单调队列)

题目限制时间限制内存限制评测方式题目来源1000ms131072KiB标准比较器Local 题目描述输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。例如 1，-3,5,1，-2,3 当m=4时，S=5+1-2+3=7 当m=2或m=3时，S=5+1=6 输入格式第一行两个数n,m 第二行有n个数，要求在n个数找到最大子序和输出格式一个数

tyvj P4620 一方的loli量产计画（快速幂）

为什么我要写这道水题呢？那是因为Yi大佬也写了这题啊…… 题面非常明显，Last Order只可能跑掉一次。更加明显的是：如果她会跑掉，跑掉的时刻一定不超过k，因为循环节的长度不会超过k。于是，我们直接暴力做k次，然后快速幂就可以了。时间复杂度： O(k+logn) O(k+logn)。虽然很想直接Link到卡拉斯科的博客，不过反正我在酒店也没事做，谁能告诉我纪中的OJ怎

Tyvj P1033 悠闲的漫步

悠闲的漫步链接题目给出一棵树求树的最大深度思路水题可以考虑从底向上统计到祖先为止的长度取MAX 代码#include <cmath>#include <iostream>#include <algorithm>using namespace std;const int Maxn=1001;int tot,n,sum=1,th;int

bzoj3196 Tyvj 1730 二逼平衡树

传送门终于把这个大坑填完了。。。 sb树套树看似最不合理的方案恰恰是正确方案，树套树并不会MLE，它的空间复杂度非常科学，O(nlogn)。（结果因为空间算错数组开小神奇的T掉，浪费了我两天时间）嘛。貌似除了操作二没什么好说的。转换成判定性问题就好了，二分O(nlog 3 ^{3}n)解决。其他按照正常线段树和平衡树写就好了。 CODE： #include<cstdio>#in

[BZOJ3224] Tyvj 1728 普通平衡树

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=3224 题目大意支持以下操作 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的

[bzoj 3224] Tyvj 1728 普通平衡树（Splay）

题意：维护一些数，支持这些操作：插入x、删除x、查询x的排名（多个x则输出最小者）、查询排名为x的数、查询小于x的最大数、查询大于x的最小数。初始序列为空，操作数不超过10^5，每个数的数据范围：[-1e7,1e7]。写一棵普通的平衡树就好了。由于是想练习一下Splay Tree，就决定是它了。以前用指针写lct，非常难以调试，解决方案是用map把指针映射成数再输出……自此以后就改用数组了

tyvj P3737 逐个击破

http://tyvj.cn/p/3737 时间: 1000ms / 空间: 131072KiB / Java类名: Main 描述秉承伟大军事家的战略思想，作为一个有智慧的军长你，遇到了一个类似的战场局面：现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价

Tyvj P1062 合并傻子

背景从前有一堆傻子，钟某人要合并他们~ 但是，合并傻子是要掉RP的…… 描述在一个园形操场的四周站着N个傻子,现要将傻子有次序地合并成一堆.规定每次只能选相邻的2个傻子合并成新的一个傻子，并将新的一个傻子的RP数，记为该次合并的RP数。（合并方法与NOI1999石子合并（本题库的沙子合并）相同，请大家参考上题合并方法）将N个傻子合并成1个的最小RP数为RPn和最大RP数为RPx

Tyvj P1288 飘飘乎居士取能量块

背景 9月21日，pink生日；9月22日，lina生日；9月23日，轮到到飘飘乎居士（狂欢吧，(^__^) 嘻嘻……）。描述 9月21日，今天是pink的生日，飘飘乎居士当然要去别人的领土大闹一番啦！为了收集更多的能量到pink家大闹，飘飘乎居士准备从后花园中取出自己多年积攒的p个能量块。后花园一共被划分n个地区，能量块被分散在里面，现在飘飘乎居士拿出地图，发现自己站在1的地方，而他

Tyvj P1015 公路乘车

描述一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如样例的第一行就是一个费用的单子。没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。输入格式第一行十个整数分别表示行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。