悠然w

分类

BZOJ(6) cdq分治(2) CodeForces(2) DP(6) dsu on tree(2) FFTNTT(4) FWT(1) KDtree(4) loj(1) luogu(6) min-max容斥(1) ODT/珂朵莉树(6) OI无关(1) 二分(2) 二分图匹配(3) 克鲁斯卡尔重构树(1) 分块(1) 分治(3) 动态点分治(1) 区间DP(1) 单调栈(8) 双指针(1) 后缀自动机(1) 奇技淫巧(3) 学习笔记(4) 容斥定理(1) 差分(3) 广搜bfs(3) 扫描线(1) 数位DP(3) 数论(1) 整体二分(1) 文化课(1) 最小生成树(1) 最短路(3) 未归档(57) 杂记(11) 树状数组(4) 树链剖分(1) 概率&期望(3) 模拟(4) 洛谷(10) 状压DP(3) 生成函数(2) 矩阵乘法&矩阵快速幂(2) 矩阵乘法&矩阵快速幂(2) 矩阵树定理(2) 线段树(4) 组合数学(1) 结论题(2) 考试总结(20) 莫队(1) 贪心(3) 随机(2) 题解(1) 高斯消元(2) 高精度(6)

/ 注册

全部文章（共232篇）

[武汉加油] 2020.3.17考试T3 string

一个长度为 \(n\) 字符集大小为 \(k\) 的字符串，它的回文串的个数是 \(k^{\lceil \frac{n}{2} \rceil}\) 发现根据题目里给的操作二，可以生成最小循环节的长度个满足条件的字符串，用这个长度的字符串拼出来长为 \(n\) 的字符串必须是回文串设这...

2020-03-17

0 0

[武汉加油] 洛谷 P3107 [USACO14OPEN]Odometer S

记忆化搜索既然需要出现的次数 \(\geq\) 长度的一半，我们不妨就枚举这个数，按照记搜的套路，我们记录一下这个数的出现次数以及是否没了前导零即可。记录次数的时候如果往后添的数是枚举的数，则 \(++cnt\) ,否则 \(--cnt\) ,易证符合条件当且仅当 \(pos=0\) 时 \...

2020-03-15

0 0

[武汉加油] CF830C Bamboo Partition

分块题目大意给定 \(n\) 个数 \(a_1\) ~ \(a_n\) ,求最大的 \(d\) , 满足 \(\displaystyle \sum_{i=1}^{n}d-((a_i-1)\%d + 1) \le k\) 首先我们看到取模很难化简式子，考虑用除法代替。 \(\displ...

2020-03-09

0 0

[武汉加油] [NOI Online 提高组]最小环

结论题其实没那么难，只不过真的被附加说明给恶心到了。首先我们将相乘的数连边，能看出来会形成几个环，显然环与环之间互不影响。然后易证一共有 \(gcd(n,k)\) 个环，每个环里就有 \(\frac{n}{gcd(n,k)}\) 个数,显然我们给每个环分配的数连续更优。关于一个环里怎...

2020-03-07

0 0

[武汉加油] luogu P6178 【模板】Matrix-Tree 定理

矩阵树定理想必大家应该都会高斯消元吧，不会的话可以看模板,我们现在着重讲一下建矩阵的方法。前置知识：我们用到的矩阵，也就是基尔霍夫矩阵的任意一个代数余子式是所有生成树的边权积的和。当所有边边权为1时求的就是生成树的个数了。我们以下设 \((x,y,z)\) 为 \(x\) 到 \(y...

2020-03-05

0 0

[武汉加油] bzoj 5099: [POI2018]Pionek 几何+双指针

几何+双指针题目大意：现在有 \(n\) 个向量，请你选出来一些向量使它们的和的长度最大，输出最大值的平方。假如我们已经知道了最终向量的方向，我们要想使长度最大，就需要将所有投影在最终向量正方向上的向量都加起来。所以我们可以按角度枚举最终向量的方向，我们需要加起来的就是一段移动的区间，我...

2020-02-22

0 0

[武汉加油] bzoj 1135: [POI2009]Lyz

忽略数据范围，我们就可以用二分图搞一搞，但事实证明我们并不能忽略(滑稽) Hall定理：对于一个二分图，设左边有个n点，右边有个m点，则左边个点能完全匹配的充要条件是：对于1<=i<=n,左面任意i个点，都至少有i个右面的点与它相连。换成人话就是这样的：设\(a_i\)为...

2020-02-16

0 0

[武汉加油] 2020.2.15 考试T1

题目描述给定一个\(n\),求\(\displaystyle \sum_{i=1}^n\sum_{p|i}d(p)\),d(n)表示n的约数个数。 \(n \le 10^{11}\) 方法一：原式等价于\(\displaystyle \sum_{i=1}^{n}\lfloor \frac...

2020-02-15

0 0

[武汉加油] 如何用杜教筛筛约数个数

本来考试遇到一个类似的，结果没动脑子直接上的杜教筛。。 g函数取\(\mu\)函数就行了，f就是约数个数函数（相当于\(1*1\)），套用杜教筛公式就好啦，但貌似\(\mu\)也要杜教筛.. 注意\(\displaystyle \sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^...

2020-02-15

0 0

[武汉加油] bzoj 3689: 异或之 Tire树

听说要建可持久化Trie树，但是我太懒菜了，所以自己就yy了一种不用可持久化的想法。我们先建一棵Trie树，顺便记录一下树上节点的size，这样我们就能求出一个值和所有n个数异或起来后第k小。我们维护一个优先队列，里面的元素hao表示数列中的第hao个数，val表示a[hao]和整个序列...

2020-02-14

0 0