19-大数据一班-杨文冠

题解

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

/ 注册

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

Array 来自专栏

原题链接:P4062 [Code+#1]Yazid 的新生舞会解法一分块对于所有的，暴力扫描所有长度不大于的区间，即枚举左端点，然后往右扫描，长度不大于，然后维护众数出现的次数，当众数出现的次数大于区间的一半时，该区间对答案的贡献加一。这里注意不要把的维护进众数里，后面会单独计算每个的为众数...

整数分块树状数组 STL

2021-08-06

1 791

I love counting 来自专栏

思路：如果不考虑去重，一般都会想到可持久化字典树。求的个数满足，很明显用字典树可以轻松的做到。求区间的内的个数的话加个可持久化，前个数组成第个版本的字典树，然后第个版本算出的值减去第个版本算出的值就是答案。字典树求的个数满足的原理：构建字典树时，每个节点存这个节点包含了多少个数。搜索字典树...

树状数组线段树

2021-07-29

2 654

Different Integers

题意：给出个数，求 ,这两个区间不同数的个数思路：其实只要把区间扩大一倍，就是求这个区间了定义数组中第一次出现的数的后缀为，第次出现的数的后缀为该数第次出先时的下标。比如：原数组为，扩大一倍后为，每个数对应的后缀为。如果某个数出现多次，而我们只算最右边的那个，我们会发现最右边的那个数的后缀...

线段树树状数组

2021-07-29

1 593

I love exam 来自专栏

思路：标程奇奇怪怪，有点绕，搞了半天才勉强看懂，还有数据水了先背包求出，表示花天学第门课最多能得多少分。设表示前门课花天学习挂科门能最多能得到的分数，那么有：如果第门课学天，并且不及格，那么有如果第门课学天，并且及格，那么有其实第一维是可以滚掉的，得到，那么有：如果第门课学天，并且不及格，那么...

dp 0/1背包

2021-07-28

1 627

Harbour.Space Scholarship Contest 2021-2022 来自专栏

E. Permutation Shift 思路：原问题等价于把往左挪位，然后最多交换次得到原排列，求有多少种。假设排列表示原排列，表示原排列往右挪位得到的排列，那么当时，对应位置上数字相同的个数为。一个通常能想到的套路就是枚举，然后把排列往左挪位得到排列，然后判断排列能不能通过最多次交换得到原排...

排序树状数组

2021-07-23

1 682

I love max and multiply

如果，那么(具有传递性) 设表示二进制数的集合，且满足。如果我们从大到小计算，那么。因为，所以此时集合已经得到了，并且可以保证的是所有满足的下标在上述的某个集合中。比如：n=32 ... 设表示，表示，表示,表示。那么我们可以在求出的同时算出这些数组。假设表示，如果下标从大到小计算，那么。 ...

二进制

2021-07-22

1 668

Product of GCDs

思路：在集合中任选个数组成一个新集合，求所有新集合的乘积，因为比较小，很容易想到(总数不容易求，常见的套路就是求每个数的贡献)枚举假设表示的新集合的个数，表示(是的倍数)的新集合的个数，表示因子包含的数的个数，的贡献就是。那么，且如果要计算，那么y由上面的定义可以确定的是中已经计算过了，那么可以考虑...

欧拉降幂组合数容斥

2021-07-22

4 535

KD-Graph

思路：按边权由小到大合并边的两个顶点，假设当前需要操作的边为，则：如果和已经在同一个组里了就不用继续合并了如果和不在同一个组里，就将和所在的组合并，则到存在一条路径上的最大值就是，且找不到比其他的路径满足该路径上的最大值小于，因为和目前只有这一条路径(边)，那么每一阶段取出同权值的所有边，将这些边...

并查集

2021-07-21

1 462

Xor sum

字典树需要开的空间等于节点数，而不是需要插入的数的数量，搞错经常会wa、TLE 前言：因为区间异或和不具有单调性，所以很难找到高效的算法去找到一个区间满足区间异或和不小于且长度最短。区间问题的一个老套路是通过前缀和转化为两个点的问题，而且位运算有点难度的题都会涉及二进制，因为后面需要用到搜索，可以...

字典树前缀和 XOR

2021-07-20

0 906

小圆前辈的素数来自专栏

求出集合A+BA+BA+B后，把下标为质数的项的系数加起来就行。由于某一项的系数最大可以为1e5∗1e5>9982443531e5*1e5>9982443531e5∗1e5>998244353，所以用NTTNTTNTT会出错，建议直接用FFT。 code: #include &l...

FFT

2021-07-19

1 411