19-大数据一班-杨文冠

分类

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

/ 注册

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

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

11篇文章 896人学习

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

2篇文章 652人学习

8篇文章 754人学习

动态规划入门

7篇文章 926人学习

1篇文章 673人学习

二分图匹配

2篇文章 658人学习

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

8篇文章 801人学习

3篇文章 750人学习

线段树进阶

3篇文章 663人学习

codeforces补题

32篇文章 882人学习

莫比乌斯反演

6篇文章 581人学习

网络流初步

4篇文章 767人学习

6篇文章 727人学习

2021杭电多校

3篇文章 791人学习

全部文章（共173篇）

蒲公英

思路：注意输入的的意思，强制在线处理。求一个区间的众数不具有区间“区间可加性”，树状数组和线段树去维护非常困难，而分块大段维护、局部朴素就非常的适合。看完题解自己在实现有点难度，蓝书就点拨一下，不给多余提示。这题是要用到桶的，所以先把出现的离散化到自然数上。将序列分成段，每段的长度为，不一定要是，...

整数分块

2020-12-11

2 607

Assign the task 来自专栏

题意：一颗n个节点n-1条边的树，T X Y表示给节点x及其子树涂色，C X表示询问节点X的颜色（初始都是-1）思路：（不要漏写运算符了）vis标记入度大于等于1的点，未标记的点就是根结点。dfs序可以把子树映射到连续的区间上，维护每个节点的dfs序以及子树最后一个节点的dfs序。区间修改单点查询...

线段树

2020-12-07

1 577

Tunnel Warfare 来自专栏

题意：1-n个地道，m个次操作，D代表摧毁第i个地道，Q代表查询包含第i个地道的最大连续地道数目，并输出。R代表修复最近摧毁的那个地道。第二次写了，看到题目有大致的思路，但还是不知道具体怎么实现。思路：可以维护一个区间的左连续区间长度li[]，以及右连续区间长度ri[]。如果左孩子区间整个区间是...

线段树

2020-12-07

2 632

Can you answer these queries? 来自专栏

题意：给一个序列，有俩种操作，一种是求区间和，一种是将区间每个数开根号后向下取整（QQ浏览器翻译成了四舍五入，坑了我很久）。思路：因为是对区间内的每个数开根号，没有办法用延迟更新，但是取根号在6，7次就会到1，所以如果父节点的权值等于r-l+1就不用往下跟新了，因为这个区间里每个数都是1，这样修改...

线段树

2020-12-07

1 621

Balanced Lineup 来自专栏

题意：给一个数组，每次询问一个区间，输出区间内最大值和最小值的差。思路：维护一个区间最小值，一个区间最大值 Code： #include<algorithm> #include<cstring> #include<cstdio> #include<iost...

线段树

2020-12-07

2 659

Count the Colors 来自专栏

题意：n次操作，每次给出x1,x2,c，表示在区间[x1,x2]上涂上颜色c，如果能看到颜色i，就输出i并输出颜色i有几个不相交的区间。思路：对于线段而言，如果长度大于等于1，它的两端被别的颜色占了，那么这个颜色还是能看到的。但如果涂区间内的点，如果长度等于1，它的两端被别的颜色占了，那么这个颜色...

线段树

2020-12-07

2 591

Just a Hook 来自专栏

题意：屠夫的钩子有三种连起来，他可以改变某一段的钩子种类来改变钩子的长度m次。问m次后改变链子的长度。思路：这个算是区间赋值吧，在最后在输出整个区间的和，lazy标记和处理完孩子后更新当前节点一个不能少。因为是赋值，所以lazy标记不要去累加。 Code： #include<algorith...

线段树

2020-12-07

1 584

Mayor's posters 来自专栏

题意：输入t组数据，输入n代表有n块广告牌，按照顺序贴上去，输入区间，问贴完以后还有多少块广告牌可以看到（因为有的被完全覆盖了）。输入：2 4表示这块广告牌占了第2、3、4个格子。思路：这是占格子类型的题，Count the Colors是涂颜色的问题两者有点区别。可以理解为这题是涂[l,r]上的点...

线段树离散化

2020-12-07

1 622

二分图匹配学习笔记来自专栏

二分图：左集合的点永远向右集合连边，右集合的点永远向左集合连边，但是集合内不能相互连边二分图的充分必要条件：至少有两个顶点且没有奇环二分图的匹配（判断是否有奇环）1.黑白染色 2.如果是不断加入边，然后判断是否是二分图，用并查集二分图最大匹配问题：匈牙利算法算法思路：1.对于一个男孩子x，如果...

二分图匹配

2020-12-03

1 618

【模板】Link Cut Tree(动态树) 来自专栏

能够解决的问题:1.求LCA2.求最小生成树3.维护链上信息(最大最小，链上和等)4.维护联通性5.维护子树信息(需要配合树)6.优化单纯性算法，在的复杂度下求最大流（这两个是在它的论文最开头提到的，资料比较少）（以上现在只是听过）看别的大佬博客入门：【参考博客】链剖分一般分为三种：重链剖分，也就...

LCT

2020-12-02

4 673