19-大数据一班-杨文冠

分类

学习(23) 未归档(1) 练习(1) 题解(137)

/ 注册

TA的专栏 96篇文章 0人订阅

[kuangbin带我飞]专题十五数位DP

11篇文章 891人学习

[kuangbin带我飞]专题十四数论基础

2篇文章 648人学习

8篇文章 749人学习

动态规划入门

7篇文章 923人学习

1篇文章 669人学习

二分图匹配

2篇文章 653人学习

[kuangbin带我飞]专题七线段树

8篇文章 797人学习

3篇文章 744人学习

线段树进阶

3篇文章 660人学习

codeforces补题

32篇文章 875人学习

莫比乌斯反演

6篇文章 577人学习

网络流初步

4篇文章 762人学习

6篇文章 722人学习

2021杭电多校

3篇文章 783人学习

全部文章（共21篇）

题解 | #校庆#

题解拍照从1∼n{1\sim n}1∼n和从n∼1{n\sim 1}n∼1分别跑一遍最长上升子序列，枚举最高的人i{i}i时，计算1∼i{1\sim i}1∼i和n∼i{n\sim i}n∼i之和，取和最大的i{i}i。（枚举最高的人i{i}i时要保证i{i}i被选到，所以要分别从前和从后跑一遍...

dp 最长上升子序列 ac自动机最大流最小割线段树二分 KM 括号匹配

2021-11-23

2 483

E. Optimal Insertion 来自专栏

考虑是把b{b}b序列中的元素插入到a{a}a序列中，b{b}b序列插入的相对位置一定是值小的在前面。对bi<bj,i<j{b_i<b_j,i<j}bi<bj,i<j，当前得到ans{ans}ans对逆序数，bi、bj{b_i、b_j}bi、bj之间值在...

线段树树状数组逆序数离散化

2021-11-10

1 547

D. Ezzat and Grid 来自专栏

思路线段树优化表示线段能组成漂亮序列最多的行数。那么每次转移的时候，区间上查找与线段对应位有的所有线段，选取最大的一个线段，那么。考虑用线段树去优化，区间上找最大的，然后得到，接着用覆盖线段的区间。因为这个只和上一个状态有关，所以可以直接覆盖。 code: #include<bits/s...

线段树

2021-08-17

2 588

Journey among Railway Stations

思路：考虑如何合并两个相邻的区间，假色表示从出发允许最早的时间，表示从出发允许最晚的时间，表示从到需要的时间。比较和能否和并，其实只需要满足。有没有其它的判断方式呢，有，但是没必要：。（这不是没事找事吗，主要是补题的时候想换个思路写，想通过维护一个和一个来完成合并，画个图就知道这样比较冗余）。所...

线段树

2021-08-11

1 443

I love counting 来自专栏

思路：如果不考虑去重，一般都会想到可持久化字典树。求的个数满足，很明显用字典树可以轻松的做到。求区间的内的个数的话加个可持久化，前个数组成第个版本的字典树，然后第个版本算出的值减去第个版本算出的值就是答案。字典树求的个数满足的原理：构建字典树时，每个节点存这个节点包含了多少个数。搜索字典树...

树状数组线段树

2021-07-29

2 653

Different Integers

题意：给出个数，求 ,这两个区间不同数的个数思路：其实只要把区间扩大一倍，就是求这个区间了定义数组中第一次出现的数的后缀为，第次出现的数的后缀为该数第次出先时的下标。比如：原数组为，扩大一倍后为，每个数对应的后缀为。如果某个数出现多次，而我们只算最右边的那个，我们会发现最右边的那个数的后缀...

线段树树状数组

2021-07-29

1 585

P7492 序列来自专栏

思路：区间或、求区间最大连续字段和。求区间最大连续字段和就是一个板子，用经典做法线段树维护一个分别表示从左开始的最大子段和，右边开始的，区间的和，区间的答案。因为一个数的二进制位只有30位，而或操作只有将至少一个0变成1才对某个值有影响，所以有效的操作最多只会影响30n次改变，每次区间修改用单点修...

最大连续子段和线段树区间或

2021-04-10

2 797

Atlantis 来自专栏

题意：给定平面直角坐标系中的个矩形，求它们的面积并，即这些矩形的并集在坐标系中覆盖的总面积。输入接着输入行，每行输入表示矩形的左下角、右下角顶点坐标，这些坐标不一定是整数。用一条竖直直线从左到右扫过整个坐标系，那么直线上被并集图形覆盖的长度只会在矩形的左右边界出发生变化(废话)。也就是说，整个并集...

线段树扫描线

2021-02-03

2 654

Stars in Your Window 来自专栏

题意：在一个天空中有颗星星(看作平面直角坐标系)，已知每颗星星的坐标和亮度(都是整数)。求用宽为、高为的矩形(都是整数)能圈住的星星的亮度总和最大是多少(矩形边界上的星星不算)。，应该是不大于的思路：因为矩阵大小固定，所以矩形可以由它的任一顶点确定。我们可以考虑把矩形的右上角顶点放在什么位置，...

线段树扫描线

2021-02-02

1 660

E-MAZE 来自专栏

思路：借鉴某位大佬博客，很详细：点击这是一个进阶版的走网格，现在是从上面往左右或者下方走，而且起点和终点是不固定，但起点和终点所在的行数是固定的，同时，还有一些地方是不能走的。我们主要考虑行与行之间的关系，很明显，下一行的某个位置子肯定是由上一行的一些位置走过有来的。假设第行的情况为：那么状态...

线段树 dp

2021-01-27

2 657