- 博客(197)
- 收藏
- 关注
RSS订阅
原创 刷题列表
文章目录T1 [P4310 绝世好题](https://www.luogu.com.cn/problem/P4310)T2 [CF618F Double Knapsack](https://www.luogu.com.cn/problem/CF618F)T3 [P2371 \[国家集训队\]墨墨的等式](https://www.luogu.com.cn/problem/P2371)T4 [P2473 \[SCOI2008\] 奖励关](https://www.luogu.com.cn/problem/P24
2020-09-17 16:00:11
130
原创 防咕列表
知识点图论网络流上下界网络流多项式全家桶数据结构KD-treeLCT边分治带修，树上莫队动态规划数位dp状压dp斜率优化计数dp期望dp字符串广义后缀自动机manacher后缀树回文自动机数学群论二次剩余中国剩余定理博弈论SG函数题目...
2020-06-13 14:22:02
84
原创 题解 P7288 「EZEC-5」树木的愤怒
Description删除两条边，将树分成三个连通块 A,B,CA,B,CA,B,C，贡献为连通块点权和之积删去一条边，问再删去任意一条边后的贡献和Solution考虑预处理出所有答案先将边下放到子节点O(n2)O(n^2)O(n2) 做法：枚举删除的任意两条边，算出贡献，累加到两条边上考虑优化发现删去一条边后，再删第二条边时，对于很多情况，都会有一个连通块不变，考虑剩下连通块的贡献一起算，再乘上这个连通块的贡献分类讨论定义 sus_usu 为子树 uuu 的点权和删的第二条边在
2021-01-26 21:42:59
213
原创 生成函数学习笔记
文章目录生成函数学习笔记前置知识导数理解简单函数复杂函数四则运算复合函数反函数积分泰勒展开常用函数的泰勒展开式莱布尼茨公式广义二项式定理普通生成函数（ogf）数列 转 ogf形式幂级数常见ogf指数生成函数（egf）题目[BZOJ3028 食物](https://darkbzoj.tk/problem/3028)DescriptionSolutionCode生成函数学习笔记前置知识导数理解对函数进行拟合简单函数f(x)f(x)f(x)f′(x)f'(x)f′(x)ccc0
2021-01-04 10:38:00
329
1
原创 题解 CF76A【Gift】
提供一种题解区没有的 麻烦的要死 的 LCT 做法转换题意，求所有生成树 PPP 的Min(Maxi∈Pgi×G+Maxi∈Psi×S)Min(Max_{i\in P}g_i\times G+Max_{i\in P} s_i\times S)Min(Maxi∈Pgi×G+Maxi∈Psi×S)发现和 魔法森林 很像考虑类似的维护方式化边为点，先将边按 gig_igi 排序，然后逐条加入边，维护 sis_isi 的最小生成树，并在图连通后每次更新答案考虑如何维护 sis_isi
2020-11-23 21:38:13
228
3
原创 20201120 专题：斐波那契数列
总览：只是来证一下这个公式的……令斐波那契数列为F(1)=1F(2)=1F(i)=F(i−1)+F(i−2) (n≥3)F(1)=1\\F(2)=1\\F(i)=F(i-1)+F(i-2)\ (n\geq3)F(1)=1F(2)=1F(i)=F(i−1)+F(i−2) (n≥3)有gcd(F(n),F(m))=Fgcd(n,m)gcd(F(n),F(m))=F_{gcd(n,m)}gcd(F(n),F(m))=Fgcd(n,m)...
2020-11-20 22:01:58
182
原创 20201119 专题：卷积求解字符串匹配
总览：时间复杂度：O(nlogn)O(nlogn)O(nlogn)可解带通配符的字符串匹配一般字符串匹配模式串 aaa 和匹配串 bbb，求 aaa 在 bbb 中的出现次数和位置len(a)=n,len(b)=mlen(a) = n,len(b) = mlen(a)=n,len(b)=m默认下标从零开始有匹配函数F(x,y)=A(x)−B(y)F(x,y) = A(x) - B(y)F(x,y)=A(x)−B(y)F(x,y)=0F(x,y) = 0F(x,y)=0 时表示 Ax=B
2020-11-19 21:23:05
200
原创 csp-s 2020 AFO记
T1大模拟手算1h+然后没有特判炸成 40pts据说有公式做法 但是谁去推呢？我讨厌闰年的12月31号有些人还活着，但是他们的????早死了还有就是为什么fc不忽略行末空格啊！！！T2简单的位运算题10min+ 搞定出题人照例卡unsign long long，并且要特判 2642^{64}264卡unsign long long似乎成了传统？T3一看就是图论+数据结构的毒瘤题，于是先看了 T4，然后调死在了 T4……最后回来补了个暴力下来写了一下，调了一个上午，思路挺好理解
2020-11-09 19:39:00
110
原创 20201104 练习：（广义）后缀自动机
总览：后缀自动机广义后缀自动机离线在 Trie 树上建立广义后缀自动机可以看作每次在线从父亲的位置开始插入一个字符（在线做法也可以看做一个只有一条链的 Trie）T1 P6139 【模板】广义后缀自动机（广义 SAM）思路：模板ans=∑len[i]−len[f[i]]ans=\sum len[i]-len[f[i]]ans=∑len[i]−len[f[i]]代码：#include <bits/stdc++.h>using namespace std;#define
2020-11-04 21:16:09
152
原创 20200924 专题：李超线段树
总览：维护若干一次函数的最值李超线段树的结构和普通线段树一样的，只是它每个节点存的是该区间优势最大的线段（优势最大即暴露在最高折线中横坐标跨度最大）李超线段树并不严格，只需满足包括单点的所有线段树区间“优势最大线段”中含有该单点的优势最大线段即可。会出现如果一整个区间最高折线都被一条线段占了的话，只有最大的区间的“优势最大线段”是该线段的情况插入时每个区间分类讨论单点查询时遍历所有区间T1 P4254 [JSOI2008]Blue Mary开公司思路：板子题代码：#include <
2020-09-24 19:49:06
167
原创 20200901 专题：斜率优化
总览：类似 fi=ai×bj+ci+djf_i=a_i\times b_j+c_i+d_jfi=ai×bj+ci+dj 的式子因为存在 ai×bja_i\times b_jai×bj 项，所以不能单调队列优化转化成 dj=−ai×bj+fi−cid_j=-a_i\times b_j+f_i-c_idj=−ai×bj+fi−ci类似于 y=kx+by=kx+by=kx+b，维护凸包其中 kkk 为 −ai-a_i−ai，bbb 为 fi−cif_i-c_ifi−ci，凸
2020-09-24 09:13:48
103
原创 20200923 SCOI模拟T2（倍增/分块）
T2 P4155 [SCOI2015]国旗计划思路：考场想法套路拆环成链，离散化对于一个当前最远位置 www，贪心的选包含这个位置，覆盖最远的人可以用分块预处理每个位置的选择一个人后下一个最远的位置时间复杂度：O(nn)O(n\sqrt n)O(nn)于是对于每个人可以从右端点向后跳，计算跳回左端点的次数考虑优化发现和 弹飞绵羊 很像于是再次分块，对每个位置预处理跳到下一个块的次数，位置对于每个人从右端点向后跳，计算跳回左端点的次数时间复杂度：O(nn)O(n\sqrt n)O(n
2020-09-23 18:44:58
109
原创 20200923 SCOI模拟T1（网络流/贪心）
T1 P4251 [SCOI2015]小凸玩矩阵思路：直接二分答案考虑要从小于等于二分值的点中选出 n−k+1n-k+1n−k+1 个考场想法：脑子抽了，没想出正解……于是……我贪心过了？？？每次找到点数最少的行在这一行中找到点数最少的列然后选它们的交点正解：对每一行建点，每一列建点源点连行，列连汇点行连可选的点连列流量全为一跑网络流判断最大流量代码：mine#include <bits/stdc++.h>using namespace std;name
2020-09-23 18:32:18
97
原创 20200919 SCOI模拟T3（树链剖分）
T3 P4216 [SCOI2015]情报传递思路：一个点如果从 tit_iti 开始收集情报，对于一个询问 Ti,CT_i,CTi,C，如果 Ti−ti>CT_i-t_i>CTi−ti>C，则这个点对答案有贡献变形一下式子：Ti−C>tiT_i-C>t_iTi−C>ti于是将询问离线，时间戳改成 Ti−CT_i-CTi−C，排序后就是树剖裸题了考场脑子抽了，写了个权值线段树维护的树上带修莫队，然后……T成狗了代码：#include <b
2020-09-23 14:08:34
73
原创 20200919 SCOI模拟T2（线段树）
T2 P5226 [SCOI2015]小凸解密码思路：一个位置是否为 0 可以预处理考虑怎么求答案直接找不好找，于是二分答案转为判断一个区间是否存在一段独立的 0可以先查询出一段区间最左/右边的 1，然后判断两个 1 间是否有 0都可以线段树维护于是拆环成链即可代码：#include <bits/stdc++.h>using namespace std;#define re register#define LL long longtypedef unsigned in
2020-09-23 13:57:57
89
原创 20200919 SCOI模拟T1（树形dp）
T1 P4253 [SCOI2015]小凸玩密室思路：对于一个即将点亮的节点 uuu，有这样两种情况:uuu 还没有被点亮，则下一个被点亮的一定是它的儿子uuu 是叶子节点，在下一个被点亮的一定是它的某一级祖先，或者是它某一级祖先的儿子定义数组 fff 和 gggf[i][j]f[i][j]f[i][j] 表示点亮 iii 之后回到i的第 jjj 个祖先的最小花费g[i][j]g[i][j]g[i][j] 表示点亮 iii 之后回到i的第 jjj 个祖先的另一个儿子的最小花费预处理每个点到祖
2020-09-23 13:52:44
86
原创 20200918 专题：Kruskal重构树
总览：处理当一个图只能经过边权大于（小于）某个权值的边的问题对图做最小生成树，当合并两个点集时，建立新结点，并将联通两个点集的最小边权作为点权，将这个点作为原来两个点集的父亲树的节点树为 2n−12n-12n−1树上的叶节点为原图的点，一个非叶节点代表原图中一个最小生成树原图任意两个点路径上边权的最大值为它们树上的 LCA 的点权以每个节点为起点，走边权不超过一定值的边所能到达的点集为树上某一结点的子树，dfn 连续T1 P4768 [NOI2018]归程思路：先跑最短路，然后建树，节点上
2020-09-18 15:23:21
186
原创 20200916 SCOI模拟T3（轮廓线dp）
T3 P3290 [SCOI2016]围棋思路：补集转化后用kmp优化轮廓线dp，再滚动数组优化空间代码：#include <bits/stdc++.h>using namespace std;#define re register#define LL long longtypedef unsigned int uint;typedef unsigned long long ull;#define pb push_back#define mp make_pairnam
2020-09-18 14:44:34
104
原创 20200916 SCOI模拟T2（按位贪心+主席树）
T2 P3293 [SCOI2016]美味思路：按照数位一位一位的贪心，加了一个 xxx，考虑对于所有的 ai+xa_i+xai+x 与 bbb 的按位异或假设我们已经处理到 bbb 的第 iii 位，假设是 111。那么我们只需要查找是否存在 aj+xaj+xaj+x 使得其二进制第 iii 位数字是 000，设当前结果是 ansansans，那么我们需要查找的数的大小就是在区间 [ans−x,ans+(1<<i)−1−x][ans-x,ans+(1<<i)-1-x][a
2020-09-18 14:41:38
78
原创 20200916 SCOI模拟T1（三分）
T1 P3291 [SCOI2016]妖怪思路：设怪物的属性为 a,ba,ba,b，环境值为 x,yx,yx,y ，t=xyt=\frac{x}{y}t=yx每个怪的贡献为a+b+at+b×ta+b+\frac{a}{t}+b\times ta+b+ta+b×t发现是一个单峰函数打表发现总贡献也是单峰的，于是可以三分开口向上的单峰函数的max也是单峰的代码：#include <bits/stdc++.h>using namespace std;namespace
2020-09-18 14:26:13
81
原创 20200915 专题：莫队进阶
总览：带修莫队：加一维时间排序时先按左右端点所在的块，然后按时间树上莫队：先树分块排序按左端点所在的块和右端点的 dfndfndfn 序转移时暴力修改，lcalcalca 特殊处理T1 P1903 [国家集训队]数颜色 / 维护队列思路：带修莫队板子代码：#include <bits/stdc++.h>using namespace std;#define re register#define LL long longtypedef unsigned int u
2020-09-17 11:10:50
83
原创 20200915 专题：FWT
总览：给出两个序列 A,BA,BA,B有Ci=∑j⊕k=iAj×BkC_i=\sum_{j⊕k=i}A_j\times B_kCi=j⊕k=i∑Aj×Bk⊕ 为一种位运算求序列 CCC代码建议背诵证明inline void OR(poly &a, int pos) { int len = a.size(); for (re int i = 1; (i << 1) <= len; i <<= 1) for (re int j =
2020-09-17 10:47:24
81
原创 20200915 专题：舞蹈链（DLX）
总览：解决覆盖问题用十字交叉双向循环链表优化搜索复杂度T1 P4929 【模板】舞蹈链（DLX）思路：板子题代码：#include <bits/stdc++.h>using namespace std;#define re register#define LL long longtypedef unsigned int uint;typedef unsigned long long ull;#define pb push_back#define mp make_p
2020-09-17 10:41:19
117
原创 20200912 专题：斯坦纳树
总览：给定一个包含 nnn 个结点和 mmm 条带权边的无向连通图 G=(V,E)G=(V,E)G=(V,E)再给定包含 kkk 个结点的点集 SSS，选出 GGG 的子图 G′=(V′,E′)G'=(V',E')G′=(V′,E′)，使得：S⊆V′S\subseteq V'S⊆V′G′G'G′ 为连通图E′E'E′ 中所有边的权值和最小。你只需要求出 E′E'E′，中所有边的权值和这个问题可以用状压 DP 来解决首先容易发现一个结论：答案的子图一定是树证明：如果答案存在环，则删去环
2020-09-13 22:48:13
160
原创 20200912 专题：模拟退火
总览：随机出一个解如果比当前答案更优，更新答案如果不优，有选择地接受板子：inline void SA() { node now = ans; double T = 2000, delta = 0.996;//温度，退火参数 while (cp(T, 1e-10) == 1) { node k; get(k); double c=k-ans; if (cp(c, 0) == -1) now = ans = k; else if (ex
2020-09-13 22:23:45
74
原创 20200912 专题：最小乘积生成树
总览：给出一个 nnn 个点 mmm 条边的无向图，第 iii 条边有两个权值 ai,bia_i,b_iai,bi，求该图的一棵生成树 TTT ，使得 ∑ai×∑bi\sum a_i\times \sum b_i∑ai×∑bi 最小对于每一棵生成树，视作一个二维平面上的点，(∑ai,∑bi)(\sum a_i,\sum b_i)(∑ai,∑bi)使得 ∑ai×∑bi\sum a_i\times \sum b_i∑ai×∑bi 最小就是让点所在的反比例函数最靠近坐标轴于是先求出与 xx
2020-09-13 19:54:55
302
原创 20200912 SCOI模拟T3（并查集+倍增）
T3 P3295 [SCOI2016]萌萌哒思路：暴力合并用并查集维护 O(n2)O(n^2)O(n2)不同数字个数为 kkk，答案为 10k−1×910^{k-1}\times910k−1×9考虑优化建图因为区间有每一位一一对应的关系，所以分块，线段树都不行考虑倍增，类似 ST表sti,jst_{i,j}sti,j 表示 iii 开头，长度为 2j2^j2j 的区间对于每一个区间建一个点对于一个 [l,r][l,r][l,r]，将它分成若干个长度为 2k2^k2k 的区间 ，合并区间
2020-09-12 17:06:40
72
原创 20200912 SCOI模拟T2（线性基+树链剖分）
T2 P3292 [SCOI2016]幸运数字思路：先考虑序列上的情况，可以线性基维护再考虑树上的情况，可以树剖维护，合并两个区间时，暴力的将一个区间的所有数插到另一个线性基里时间复杂度：O(nlog4n)O(nlog^4n)O(nlog4n)（树剖nlog2nnlog^2nnlog2n×\times×暴力合并线性基log2nlog^2nlog2n ）代码：#include <bits/stdc++.h>using namespace std;#define LL long l
2020-09-12 16:56:33
102
原创 20200912 SCOI模拟T1（字符串）
T1 P3294 [SCOI2016]背单词思路：每个串向它的最长后缀连边后形成一棵树，贪心的编号发现树就是 ACM 的 last树last树last树考虑怎么编号每个点先给自身编号后向大小最小的子树递归感觉一下是最优的代码：#include <bits/stdc++.h>using namespace std;#define pb push_back#define int long longnamespace IO {char _buf[1 << 2
2020-09-12 16:47:48
67
原创 20200909 SCOI模拟T3（计数）
T3 P5481 [BJOI2015] 糖果思路：发现找出一排的方案数 SSS 后，答案为 PSnP_S^nPSn考虑如何找出一排的方案数容易发现 dpdpdpfi,jf_{i,j}fi,j 为 iii 个数，jjj 列的方案数fi,j=fi−1,j+fi,j−1即f1,n=1,fn,1=nf_{i,j}=f_{i-1,j}+f_{i,j-1}\\即\\f_{1,n}=1,f_{n,1}=nfi,j=fi−1,j+fi,j−1即f1,n=1,fn,1=n手玩一下每一排的通
2020-09-09 20:03:40
74
原创 20200909 SCOI模拟T2（树哈希）
T2 P5043 【模板】树同构（[BJOI2015]树的同构）思路：树哈希板题找重心然后用质数表哈希然而考场找重心出现了莫名其妙的 bug代码：#include <bits/stdc++.h>#include <tr1/unordered_map>using namespace std;typedef unsigned long long ull;namespace IO {char _buf[1 << 21], *_p1 = _buf, *_p
2020-09-09 19:39:46
106
原创 20200909 SCOI模拟T1（后缀数组）
T1 P5479 [BJOI2015]隐身术思路：发现 K≤5K≤5K≤5，考虑爆搜。考虑每个子串都是一个后缀的前缀，不妨枚举后缀对于每个后缀（起始下标为 LLL），设 dfs(i,j,k)dfs(i, j, k)dfs(i,j,k) 为当前需要匹配 AiA_iAi 和 BjB_jBj，还剩 kkk 次编辑的机会。若 Ai=BjA_i=B_jAi=Bj，直接跳到下一个 Ai+l≠Bi+lA_i+l≠B_i+lAi+l=Bi+l 最小的 lll 的位置考虑 Ai≠BjA_i≠B_j
2020-09-09 19:36:06
113
原创 20200908 专题：最近点对
总览：随机化可过大部分题……随机旋转坐标轴，按 xxx 排序，对每个点和后面几个点求距离，取最小KDtree可做分治是正常方法
2020-09-08 22:01:07
94
原创 20200908 练习：坐标旋转
T1 UVA12221 Fractal思路：题目大意：给一条折线，每一次操作把这条折线的所有线段变换成跟这条折线的相同形状，重复 ddd 次。问此时从头到尾走全长的 fff（0≤f≤1）（0≤f≤1）（0≤f≤1）距离，将停在点的坐标输入：T 组数据n 个点点的坐标变换次数走全长的距离设 t=这条折线的长度/头到尾的直线距离t = 这条折线的长度 / 头到尾的直线距离t=这条折线的长度/头到尾的直线距离那么线段变换成折线的时候，长度就会变成 ttt 倍变换 ddd 次，长度就会增大 t
2020-09-08 21:57:13
139
原创 20200908 专题：Pick定理
总览：当点的坐标为整数时三角形面积s 三角形内部点n 三角形边上的点wn+w/2−1=s三角形面积s\ 三角形内部点n\ 三角形边上的点 w\\n + w/2 - 1 = s三角形面积s 三角形内部点n 三角形边上的点wn+w/2−1=s面积叉积，边上的点就是向量的 gcd(x,y)gcd(x,y)gcd(x,y)T1 poj2954 Triangle思路：板子题代码：#include <bits/stdc++.h>using na
2020-09-08 21:47:39
143
原创 20200908 专题：动态凸包
总览：以一个点为基准点，用角度维护凸包插入一个点时，找到前驱后继，分别弹一下可以用 set 维护因为基准点在中间，所以用叉积判断方向时要先判象限T1 #1249. SGU277 HERO 动态凸包思路：板子题代码：#include <bits/stdc++.h>using namespace std;#define LL long longtypedef unsigned long long ull;typedef unsigned int uint;#define
2020-09-08 21:41:27
110
原创 20200908 专题：三角剖分
总览：valB,C,D,E=valB,C+valC,D+valD,E+valE,Bval_{B,C,D,E}=val_{B,C}+val_{C,D}+val_{D,E}+val_{E,B}valB,C,D,E=valB,C+valC,D+valD,E+valE,B以前一直不知道这叫三角剖分……T1 #2391. Cirno的忧郁思路：出题人真神仙，用维护面积的方法维护权值……sumi,jsum_{i,j}sumi,j 为 ΔO,i,j\Delta O,i,jΔO,i,j 的带符
2020-09-08 21:37:33
123
原创 20200908 专题：最小圆覆盖
总览：随机增量法圆的表示：((圆心(x,y)),半径r)((圆心(x,y)),半径r)((圆心(x,y)),半径r)初始圆为 ((0,0),0)((0,0),0)((0,0),0)、枚举每一个点，找到一个圆，使 p1−pnowp_1-p_{now}p1−pnow 在圆内枚举每一个点 pip_ipi，如果 pip_ipi 不在当前圆内，假设它在圆上，将圆设为 ((xi,yi),0)((x_i,y_i),0)((xi,yi),0)再枚举每一个它之前的点 pjp_jpj，如果 pjp_j
2020-09-08 20:59:06
167
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人