19-大数据一班-杨文冠

题解

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

/ 注册

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

Hash Function 来自专栏

求出满足ai%mod≠aj%moda_i\%mod\neq a_j\%modai%mod=aj%mod的最小的mod{mod}mod 之前在百度之星写过类似的题萌新，但是哪一题是求满足ai%mod=aj%moda_i\%mod= a_j\%modai%mod=aj%mod的最小的mod{...

NTT FFT

2021-07-19

1 577

Codeforces Round #732 (Div. 2) 来自专栏

A. AquaMoon and Two Arrays 把数组A中的每个元素改为，然后不断选小于0的和大于0的进行操作，由此可以知道才有解。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ...

2021-07-16

1 514

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

A. Find The Array 列出的一个：1.12.1+13.1+24.1+35.1+3+1。。。9.1+3+510.1+3+5+1 会发现，其实就是要用公差为2，首项为1的等差数列表示一个数，如果小了就补上一个数。 #include <bits/stdc++.h> using n...

2021-07-16

1 669

最长公共子序列

第一个问题应该都是会的，主要分析第二问。定义表示对应的状态长度等于的公共子序列的数量。1.如果，则表示可以由推出。2.如果，则表示可以由推出。3.如果，则表示可以由推出。4.如果，那么，即2、3都会满足，并且都包含，所以此时需要减去一个。还需要滚动数组。 Code: #include <bi...

最长公共子序列 dp

2021-06-04

1 521

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