19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

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

棋盘覆盖来自专栏

思路：一个骨牌覆盖两个相邻的格子，也就是相邻的格子有边相连，不相邻的格子没有边相连，所以可以分成两个集合，是偶数的和是奇数的分开，恰好与“0要素”对应。每个格子只能被1张骨牌覆盖，恰好与“1要素”对应。将没有被禁止的格子分成左右两个集合，建一个左集合节点到右集合节点的有向图（根据具体实现的原理可以...

二分图匹配二分图最大匹配

2021-01-19

4 658

P1399 [NOI2013]快餐店

思路：求某个点使得它到图中的所有点的最大距离最小。首先直接找图的直径是不对的，比如环上等距的三个点，然后其中一个点往外扩展了一个点，由于我求出来的点之后按理要放在直径的中点上，但这种情况显然不满足。对于这种带了环的题目（又叫基环外向树），我们一般是断掉环上的某一条边，再作考虑。把环上的某一条边断掉变...

DFS dp

2020-12-18

1 691

蒲公英

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

整数分块

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