rprp

贪心

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 配置(2)

/ 注册

全部文章 / 贪心（共5篇）

JOISC 2016 Day3 电报

JOISC 2016 Day3 电报前置知识（伪）基环树基环外向树基环内向树此题就是一棵基环外向树。其实这些都没什么用，跟这题没啥关系思路考试的时候不会做，考完才发现自己就差那么一点点... 首先考虑这样一张图：我们的目的是让整个图成为一个环，但是这显...

妙啊基环树

2020-05-18

0 416

Luogu P4570 [BJWC2011]元素

题目很显然就是要求序号的线性基。我们希望线性基里的权值最大，就按权值从大到小插入就行了。为什么是对的呢？插入线性基的一个矿石只会和另一些矿石在一个位置上冲突，而那些矿石也只能插入这一位，同时它们价值不如当前的矿石，所以这是最优的。 #include <cstdio> #include...

线性基

2020-05-01

0 451

Luogu P6185 【[NOI Online 提高组]序列】

本来考场切了的，结果代码没保存，爆炸成80，自闭了。考场上我是一个一个部分分做的，所以这里我也一个一个部分分写。 0pts \(n=1\) 这个档位是针对样例写的。。。因为不写我就过不了样例。。。显然如果有一个1操作就输出YES，没有就看相不相等完事。。。贴一个没有什么用的代码。 inl...

并查集二分图

2020-04-30

0 419

Luogu AT2557 【Ball Coloring】

题目大意：有n对数字，让你将这n对数字染色成红的或蓝的，求\((Rmax-Rmin)*(Bmax-Bmin)\) \(n<=2e5,0<a<=1e9\) 解题过程: 还是luogu比较香..... 在atcode上不会做今天用luogu看就会了是什么鬼... (难道我的水平...

线段树妙啊

2020-04-30

0 416

Luogu P4511 CTSC 2015 日程管理

正题一开始的时候显然第\(i\)天以前可以放\(i\)个任务是吧，然后考虑用一棵线段树维护这个数量，设每天的这个值为\(lev(i)\) 考虑在\(t\)这个截止时间位置放了一个任务，那\((t,n)\)这个区间的$ lev(i)$ 都要减去\(1\)。　　插入设插入的终止时间为\(t...

set 线段树妙啊

2020-04-30

0 532