rprp

分类

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

TA的专栏 1篇文章 0人订阅

1篇文章 668人学习

全部文章（共55篇）

FFT板子

#include <cmath> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #def...

FFT 多项式

2020-05-11

0 387

BZOJ2568 比特集合

题目链接 BZOJ2568 比特集合思路首先考虑不带区间加的情况，显然容易想到对每个数的每一个二进制位维护一个树状数组。设一个树状数组维护的是二进制的第\(k\)位，那就每次往里面存\(num\)的时候在这个树状数组的第\(num\ mod \ 2^k\)这个位置\(+1\)，那么我们...

树状数组位运算

2020-05-08

0 539

ubuntu下c++ Gedit配置

丢个配置。。　编译 #!/bin/sh fullname=$GEDIT_CURRENT_DOCUMENT_NAME name=`echo $fullname | cut -d. -f1` g++ -o $name $fullname -DIN 运行 #!/bin/sh fullnam...

配置

2020-05-08

0 444

P6329 【模板】点分树 | 震波

前言由于这篇题解思路并没有什么区别，所以这篇题解的意义在于稍稍更细致地讲下思路和卡常方法。估计也只有我常数这么大了思路第一感由于题目要查询到一个点距离为\(k\)以内的所有点的权值和，一个显然的想法就是对每个点开一个线段树维护权值和，下标维护距离，然后暴力查询。显然这是\(MLE+T...

线段树动态点分治

2020-05-06

0 657

Luogu P3350 [ZJOI2016]旅行者

这题正常的题面请看这里由大佬之言可知，看见网格图想分治　　所以这题考虑分治。　　考虑把棋盘分成两半，那所有点就会有两种情况：在完整的一半以内跨越两半考虑在我们分成两半的那条中线的所有点跑最短路来更新所有点的答案。然后对于跨越了两半的点就直接保存答案，在同一块的点就类似整...

最短路分治

2020-05-06

0 407

Luogu [ZJOI2015]幻想乡战略游戏

显然，一棵树的带权重心最多只有两个，最少会有一个，而且在这两个点的答案一定相等。（都是带权重心当然相等）鉴于点分治的写法貌似并不太需要这样的分析，就不说了。我不会首先建出一颗点分树，然后考虑在点分树上跳儿子来保证复杂度，于是我们就需要快速算出所有点到这个重心的带权距离和。由于这题是点分树，考虑在点...

动态点分治

2020-05-05

0 375

斐波那契数列简单性质

计数性质 \(F_i=F_{i-1}+F_{i-2}\) \(\sum^{n}_{i=1}F_i=F_{n+2}-F_2\) 证明：当\(n=1\)时，\(F_3-F_2=F_1\)显然成立。当\(n=2\)时，\(F_4-F_2=F_3+F_2-...

斐波那契数列

2020-05-05

0 409

Luogu P2056 [ZJOI2007]捉迷藏

动态点分治先建出一颗点分树，然后维护。对于每一个点维护两个堆，一个堆维护子树内所有点到分治父节点的距离最大值，一个堆维护一个点所有子树的第一个堆的最大值，再全局维护一个堆取所有分治重心的答案的最大值即可。代码细节感人。。。一个比较有用的trick就是用两个大根堆实现可删除的堆但是要开O2 ...

堆动态点分治

2020-05-04

0 398

Luogu P4127 [AHOI2009]同类分布

数位DP 这题最妙的一点在于，由于我们无法存下原来的这个数，我们就考虑存取模之后的值，而这个模数就选择一个可能是最后的每一位数字的和的值。而这个总数只有\(9*18=162\)种，然后存下每一位的和以及从高位到低位的取模结果，数位DP即可。 #include <cstdio> #inc...

数位DP

2020-05-03

0 342

二项式反演学习笔记

前置知识容斥原理组合数约定 \(A'_i\)表示集合\(A_i\)的补集。反演形式形式一 \[f(n)=\sum_{i=0}^{n}(-1)^iC^i_ng(i)\Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^iC^i_nf(...

二项式反演

2020-05-03

0 466