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篇）

第十二届蓝桥杯省赛第一场C++B组

砝码称重 dp题 Code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 7, mod = 1e9 + 7; bitset<maxn>f;...

二分二分答案思维 dp

2021-06-03

1 743

D. Love-Hate 来自专栏

思路：如果知道答案是某个人的子集以及这个人的编号，那么能不能算出答案，以及时间复杂度是多少，然后考虑到生日悖论，因为答案是个人的子集，所以我们任意选一个人，答案不是的子集的概率是（实际更小），那么我们只要取 30 个人，这些人的子集都不包含答案的概率就小到，几乎可以认为不可能发生。...

生日悖论离散状压dp 二进制

2021-06-01

1 882

D. Kill Anton 来自专栏

思路：这题和南京站的Evil Coordinate有着异曲同工之妙。南京的那题的解法也是一定存在某个最优情况中，相同类型的字母连续出现，然后只需要枚举种情况就可以找到最优解。南京那题我不会证，但是多画几个图后发现找不到反例，感觉也有点道理，这题看了一下证明没看懂，感觉是就是吧。枚举出来一个状态后计...

结论题前缀和

2021-05-30

2 709

C. Parsa's Humongous Tree 来自专栏

首先每个顶点的值。如果,证明如下：假设有个靠近顶点的顶点满足假设有个靠近顶点的顶点满足那么当时，将减小到会使得整棵树的美丽值增大当时，将增大到会使得整棵树的美丽值增大当时，将变成或会使得整棵树的美丽值不变或增大定义表示时，的子树的美丽值之和，同理。 MyCode: #include <bit...

思维 dp

2021-05-26

2 732

C. Robot Collisions 来自专栏

思路：括号匹配好题1.能碰撞的两个点坐标的奇偶性一定相同2.一般的，当所有的点不需要经过撞墙反弹后才能碰撞时，坐标奇偶性相同的点碰撞的过程就是一个括号匹配进栈出栈的过程，向右走的点进栈遇到向左走的点就出栈。3.一轮括号匹配结束后剩下的点只要左括号变右括号、右括号变左括号然后继续匹配。处理一般情况的时...

括号匹配栈

2021-05-25

1 694

E. Assimilation IV 来自专栏

思路：每个点被控制之后的贡献都是，所以答案可以转化为求每个点被控制的期望之和。对每个点计算合法排列（城市的排列），合法排列必须满足存在一个城市能控制点，可以用容斥/状压写，复杂度级别的。可以考虑求答案的补集，求每个点的非法排列，即所有的城市都不能控制该点，显然第个操作的城市于点的距离应该，第个操作的...

数学期望

2021-05-25

1 796

E. Partition Game 来自专栏

思路：设表示前个数分成段的最小花费，那么显然有一个满足决策单调性的充要条件是：对于两个决策点，若在处优于，则在处都优于。定理：若满足四边形不等式，则满足决策单调性。定义：若二元函数满足，则称其满足四边形不等式。推论，若只与有关，即，则必然符合四边形不等式。且此时，该类适宜用单调队列优化。而这题是...

莫队决策单调 dp

2021-05-25

1 545

L. Square 来自专栏

思路：为了保证为平方数，如果的某个质因数的个数为奇数个，那么的该质因数个数也应该是奇数个，依次类推，那么所有中出现过的质因数在每个中出现的次数要么都是奇数个要么都是偶数个，取代价最小的。 MyCode: #include <bits/stdc++.h> typedef long long...

2021-05-19

3 808

主席树

P1383 高级打字机这题用红黑树实现的可持久化数据结构可以很轻松的AC，码量非常小，自行百度。 MyCode: #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7; typedef long long l...

可持久化线段树主席树

2021-05-13

1 587

月出皎兮，佼人僚兮。来自专栏

如果颜色最多个数大于其它颜色之和，可以匹配的对数就是其它颜色之和，即其它颜色的都和颜色最多的两两匹配反之，每个颜色都能找到匹配，因为其它颜色匹配后，剩下的只要不断拿出两个去拆已经匹配了的一对，一定能用完。 MyCode: #include<bits/stdc++.h> using nam...

树上启发式合并

2021-05-13

0 665