19-大数据一班-杨文冠

题解

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

/ 注册

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

Atlantis 来自专栏

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

线段树扫描线

2021-02-03

2 657

Stars in Your Window 来自专栏

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

线段树扫描线

2021-02-02

1 663

Educational Codeforces Round 103 (Rated for Div. 2) 来自专栏

总结：A、B、C不是白给题吗，D题dp，需要一些思维，E题拓扑排序(+dfs+字典树)，还是要转个弯cf的题都要转个弯 A. K-divisible Sum 题目大意:构造一个长度为n的数组,每个数是正整数,要求整个数组的和是k的倍数,并且整个数组最大的数最小.输出数组的最大值。思路：首先数组的...

扑朔排序字典树拓扑排序模拟思维 dp

2021-02-01

3 697

Gitignore

题意：给n个需要忽视的目录，m个需要保护的目录，求Gitignore的最小行数(有多少文件路径没被忽视--本应该被忽视的) 思路：比赛的时候写了个神仙代码正解应该就是模拟，标记被保护了的路径名父级目录(a/b/c就只标记a、b)，因为输入保证不会同时出现:。接着枚举应该忽略的文件路径，如果某个父级...

第45届ICPC上海 DFS 模拟贪心思维

2021-01-29

2 635

Mine Sweeper II

题意: 给两个的扫雷图，问能不能至多反转个格子，把图B的的空白区权值和变成和图A相同。思路：这题有浓厚的气息，可惜打的有点少，没做出来，一看代码秒懂。既然是式的，样例必然是误导性的，就怕样例给好了让人一眼给看出来。其实答案只要输出A的原图或者反图即可，选原图还是反图不难，原图和反图是互补的，B不...

第45届ICPC上海贪心思维

2021-01-29

1 660

Sum of Log 来自专栏

思路：由于，所以+1其实就是之中最大的那个数的二进制位加一，这个比赛的时候就想到了。直接写状态，上板子即可。比赛的时候只会求单个区间的问题，叠加的没想过，然后死活想不出来怎么去数位dp。叠加的不就是多个数随机组合吗，也就是对应二进制位的随机组合，居然没想到，2333。补题时的时候数位dp的状态不敢多...

数位dp 第45届ICPC上海

2021-01-29

6 750

dh的帽子来自专栏

思路：官方的题解：没想过加下界，加上下界确实很简单。枚举的上下界，状态为：写出状态后发现复杂度其实很低的，只要确保状态没问题就行了。 MyCode: #include <bits/stdc++.h> using namespace std; typedef long long i...

数位dp

2021-01-28

2 671

E-MAZE 来自专栏

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

线段树 dp

2021-01-27

2 661

十进制矩阵快速幂-B

题意：给你六个个数字，求对取余，思路：求广义斐波那契数列的第项，因为比较大，需要去找循环节，或者二进制转十进制运算，后者不注意容易T，但是我只会十进制，广义斐波那契数列的循环节是神仙找的规律。类比二进制的快速幂，有如下例子：设，则：1、2、3、4、 MyCode： #include <...

矩阵快速幂十进制快速幂

2021-01-27

2 503

Pair 来自专栏

思路：我入门时写的数位都是求一个区间内满足某个要求的数有多少个，也就是通常要跑两遍，这题比较特殊的地方在于要求是满足条件的二元关系的数量()。按照传统的思路，我们更喜欢用二进制来表示，比较二进制数的大小从高位开始，高位大的数一定大，后面就不用比较了。从集合的高位开始判断当前二进制位上的两个数的...

数位dp

2021-01-27

2 552