- 博客(52)
- 收藏
- 关注
RSS订阅原创 知识点整理：斜率优化DP
前言概要知识点讲解单调性归纳证明基于单调性的转移优化例题AC代码练习题BZOJ1096 仓库建设解题思路AC代码BZOJ1911 特别行动队解题思路AC代码前言最近刷BZOJ的题目的时候，发现做到了很多题目都是用到了斜率优化，这个优化很早也接触过，但也没有仔细地去学。最近认真的去学了一下，就在这里做个整理概要斜率优化是基于单...
2018-08-01 19:28:37
297
原创 知识点整理：FFT详解
前言前置知识知识点讲解概要多项式相乘的朴素算法系数表示法与点值表示法复数的引入单位复根DFT前言FFT其实在很早的时候就已经接触到了，但是那个时候学起来有点仙，感觉这东西离实际解题的距离有点远，不如那些其他的数据结构那么直接。但是半年多下来的做题，发现FFT其实应用的十分广泛，并且很多数学题推出公式之后就可以套用FFT进行计算。所以对于FFT的理解也不...
2018-07-27 15:32:58
1077
原创 BZOJ 3065 带插入区间K小值 （树套树、替罪羊树套线段树）
BZOJ3065 带插入区间K小值题意题外话题解AC代码：BZOJ3065 带插入区间K小值题意Description 从前有nnn只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力a[i]a[i]a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间kkk小值。他每次向它的随从伏特提出这样的问题: 从左往右...
2018-07-24 20:25:57
467
原创 知识点整理：二叉（重量）平衡树——替罪羊树
知识点概要知识点详解平衡因子子树的重构基础操作复杂度分析关于替罪羊树代码（luogu3369 && BZOJ3224）知识点概要在各种二叉平衡树中，大多数的平衡树都是通过旋转来维护这棵二叉查找树的性质，并且尽量保证每次的查找的复杂度为logloglog的。然而说实话，各种情况的旋转很容易写挂，考场上一旦写挂掉就会心态爆炸，所以我们或许...
2018-07-24 08:18:41
901
原创 NOI2018 Day2 屠龙勇士（扩展孙子定理+multiset）
NOI2018 Day2 dragon题解AC代码： NOI2018 Day2 dragon题解开场开了T3之后发现T3根本不可做，于是集中精力刚T1和T2，但是机房猝不及防的断电三次，神TM整整少了半个小时做题时间。T1只码了70分，T2 15分暴力还挂成了10分。 这题的做法还是比较清真的，部分分也很多，打了简单的60分暴力之后发现有10分的部分分都是...
2018-07-21 10:08:54
540
原创 NOI2018 Day1 归程（Kruskal重构树）
题意：题解：题意：本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图（节点的编号从 1 至 n）。我们依次用 l,a 描述一条边的长度、海拔。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。 我们用...
2018-07-21 09:49:09
701
原创 codeforces DIV2 E. Garlands （离线、二维树状数组）
E. Garlands题意：解题过程：AC代码：E. Garlands题意：给出你一个n*m矩阵，矩阵中有一些灯泡，这些灯泡连成了k条互不重叠的链。每个灯泡都有一定的权值w，但是只有当灯泡打开的时候，才会产生贡献，刚开始所有的灯泡都是开着的。共有q次询问，有两种操作： ①“Switch i”——表示将编号为i的链所有的灯泡取反（即开变关，关变开）。 ...
2018-07-12 19:12:15
268
原创 CQOI2018 Day1 社交网络
Cqoi2018 Day1 社交网络题目背景：题目描述：输入输出个数：分析：Code：Cqoi2018 Day1 社交网络题目背景：当今社会，在社交网络上看朋友的消息已经成为许多人生活的一部分。通常，一个用户在社交网络上发布一条消息（例如微博、状态、Tweet等）后，他的好友们也可以看见这条消息，并可能转发。转发的消息还可以继续被人转发，进而扩散到...
2018-04-17 19:59:51
265
原创 CQOI2018 Day1 :破解D-H协议
CQOI Day1 :破解D-H协议题目背景：题目描述输入输出格式SAMPLE INPUT:SAMPLE OUTPUT:分析：Code：想了一想……emm……发现自己的博客又是好久没有更新了啊……那么既然现在机房里要求强制补题……emm，作为蒟蒻的我就顺便更新一下博客吧。CQOI Day1 :破解D-H协议题目背景：Diffie-Hellm...
2018-04-17 19:42:36
364
原创 LIGHGTOJ 1094 Farthest Nodes in a Tree （树的直径，模板）
LIGHGTOJ 1094 Farthest Nodes in a Tree题意:解题过程：AC代码：LIGHGTOJ 1094 Farthest Nodes in a Tree题目传送门题意:给出你一棵树和每条边的边权，让你找出树上的两点，满足这两点之间的路径权值和最大。求这个权值和。解题过程：这题是一道模板题，就是让你求树的直径（...
2018-03-06 17:35:12
179
原创 POJ 2424 Flo's Restaurant （模拟）
POJ 2424 Flo’s Restaurant题意：解题过程：AC代码：POJ 2424 Flo’s Restaurant题目传送门题意：你在开一个餐厅，共有三种桌子，第一种:只能坐1~2个人，第二种:只能坐3~4个人，第三种:只能做5~6个人，每种桌子分别有A、B、C张，有一些客人会来吃饭，但可能会出现客人会等待的情况。假设每桌都要吃半小时...
2018-03-05 22:25:22
172
原创 POJ 2392 Space Elevator（多重背包，排序）
POJ 2392 Space Elevator题意：解题过程：AC代码：POJ 2392 Space Elevator题目传送门题意：你需要建一个高塔，材料总共有K种，每种材料有三个属性：高度，数量，限度。限度是指该种材料只能在低于该限度的高度下被使用。问你最高能够把这个高塔建到多高。解题过程：这题中材料有高度和数量，比较容易的想到这题是...
2018-03-05 22:19:56
207
原创 POJ 2385 Apple Catching（DP）
POJ 2385 Apple Catching题意：解题过程：AC代码：POJ 2385 Apple Catching题目传送门题意：一头牛要接苹果，一共有两棵树，牛刚开始在第一棵树下，每次可以在两棵树之间移动，给出你T秒内下落苹果的树的编号（1或2），问你最多移动K次，能够接到最多的苹果是多少。解题过程：比较水的DP，本来想着用一维记录牛当前在...
2018-03-05 22:11:55
161
原创 POJ 2356 Find a multiple （数学，前缀和）
POJ 2356 Find a multiple题意:解题过程：AC代码：POJ 2356 Find a multiple题目传送门题意:给出你n个数，问你能否从这n个数中取出任意数量的数，使这些数的和是n的倍数，不行则输出0，否则输出方案。解题过程：根据抽屉原理可知这题并不存在0的情况，因为我们设前i个数的和对n取模为Si，如果出现Si...
2018-03-05 21:54:58
146
原创 POJ 2355 Railway tickets （DP）
POJ 2355 Railway tickets题意：解题过程：AC代码：POJ 2355 Railway tickets题目传送门题意：你需要从s点做车到t点，车在行驶距离不同时价格不同，如果距离比0大且比l1小，那么价格为c1如果距离比l1大且比l2小，那么价格为c2，如果距离比l2大且比l3小，那么价格为c3，但一辆车的行驶距离不能超过l3，一共有...
2018-03-05 11:27:02
353
原创 POJ 2353 Ministry（DP，前缀）
POJ 2353 Ministry题意：解题过程：AC代码：POJ 2353 Ministry题目传送门题意：给你一个n*m的矩阵，每个矩阵有一个数，表示在位置（i，j）办理手续的费用，在（i，j）办理完手续之后，你可以到（i+1，j）或者（i，j+1）或者（i，j-1）的位置继续办理手续，办完所有的手续定义为从（1，j）开始,到（n，j’）结束的整个过...
2018-03-05 11:18:01
145
原创 POJ 2346 Lucky tickets（DP，记忆化）
POJ 2346 Lucky tickets题意：解题过程：AC代码：POJ 2346 Lucky tickets题目传送门题意：定义一个位数为偶数的数为幸运数当且仅当这个数前一半的部分数字之和等于后一半的数字之和，给出一个n，求出有多少个位数小于n的数是幸运数。解题过程：我们可以比较容易的想到DP，然后我们会发现DP当中我们需要的只是前一半...
2018-03-04 21:11:45
269
原创 POJ 2329 Nearest number - 2（搜索）
POJ 2329 Nearest number - 2题意：解题过程：AC代码：POJ 2329 Nearest number - 2题目传送门题意：你有一个n*n矩阵，每个点有一个数字，可能是0~1e9的任意一个数字，现在要求你对这个矩阵进行修改，对于所有的为0的数字，要求寻找到这个点曼哈顿距离最小的非0的一个数，并把这个点改为那个数的值，如果有...
2018-03-04 21:02:33
194
原创 POJ 2192 Zipper （简单DP）
POJ 2192 Zipper题意:解题过程：AC代码：POJ 2192 Zipper题目传送门题意:给出你三个字符串，问你能否把前两个字符串混合成第三个字符串，使得每个字母在原字符串中的前后顺序不改变。解题过程：考虑DP，可以用f[i][j]表示第一个字符串枚举到第i位，第二个字符串枚举到第j位时，能否混合成前第三个字符串前i+j位。...
2018-03-04 20:53:21
310
原创 POJ 刷题进程.2
POJ 刷题进程.2-（已完结）POJ 1690 (Your)((Term)((Project)))题意：解题过程：AC代码：POJ 1699 Best Sequence题意：解题过程：AC代码：POJ 1742 Coins题意：解题过程：AC代码：POJ 1887 Testing the CATCHER题意:解题过程：AC代码：POJ 19...
2018-02-25 21:01:30
324
原创 POJ 刷题进程.1
POJ 刷题进程 1-已完结POJ 1018 Communication System题意解题过程AC代码POJ 1050 To the Max题意解题过程AC代码POJ 1083 Moving Tables题意解题过程AC代码POJ 1088 滑雪题意解题过程AC代码POJ 1125 Stockbroker Grapevine题意解题过...
2018-02-08 17:52:56
434
原创 czl的知识点整理5——单调队列
-知识点整理-单调队列-知识点讲解知识点实现->知识点整理-单调队列<-知识点讲解：既然在模板库中发了单调队列的板子，那么就顺便把单调队列讲一讲吧。（我不会说是在NOIP前一天攒一攒RP的~）单调队列和单调栈的方法差不多，而且可以算是不会线段树的OIer的福音了。所以单调栈也不会的同学也来学一学吧，反正操作也是差不多的。回归正题~单调队列的用途是维护一个区间的最值的（是不是很像线段树啊~咳咳…）
2017-11-10 15:12:40
170
原创 czl蒟蒻的模板库8——单调队列
#include <bits/stdc++.h>using namespace std;const int maxn=2000005;typedef long long ll;typedef pair<ll,int>P;#define fi first#define se secondinline void read(int &x){ x=0;int f=1;char ch=g
2017-11-10 14:04:51
193
原创 czl蒟蒻的模板库7——最长公共子序列
#include <bits/stdc++.h>using namespace std;const int maxn=1005;int f[maxn][maxn];int n;int a[maxn],b[maxn];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]
2017-11-09 18:35:42
230
1
原创 czl蒟蒻的模板库6——倍增LCA
#pragma GCC optimize (3)#include <bits/stdc++.h>using namespace std;namespace fastIO{ #define BUF_SIZE 100005 #define OUT_SIZE 100005 #define ll long long //fread->read bool IOer
2017-11-09 18:34:32
231
2
原创 czl蒟蒻的模板库5——线段树
求区间和：#include <bits/stdc++.h>using namespace std;const int maxn=100005;typedef long long ll;struct node{ ll val; ll addmark;}no[maxn*4];ll a[maxn];void build(int pos,int l,int r){ no[
2017-11-09 18:33:10
179
原创 czl蒟蒻的模板库4——Tarjan
#include <bits/stdc++.h>using namespace std;const int maxn=500005;typedef long long ll;int n,m,s;int f[maxn];bool vis[maxn];int q1[maxn],q2[maxn];int ans[maxn];vector<int >e[maxn];inline void r
2017-11-09 18:32:04
215
1
原创 czl蒟蒻的模板库3——KMP
#include<iostream>#include<cstring>#include<stdio.h>using namespace std;char s[1010];char t[2020];int p[1010];void get_p(int n){ p[0]=-1; for(int i=1,j=-1;i<=n;i++) { while(j
2017-11-09 18:31:07
175
原创 czl蒟蒻的模板库2——FASTIO
~~注：必须使用文件操作读入和输出~namespace fastIO{ #define BUF_SIZE 100005 #define OUT_SIZE 100005 #define ll long long //fread->read bool IOerror=0; inline char nc(){ static char buf[
2017-11-09 18:30:06
230
原创 czl蒟蒻的模板库1——Dijkstra
#include <bits/stdc++.h>using namespace std;const int M=500005;const int N=100005;typedef long long ll;typedef pair<int,int>P;#define fi first#define se secondstruct edge{ int to; int c
2017-11-09 18:26:58
176
原创 czl的知识点整理4——线段树
-知识点整理-线段树-知识点讲解知识点实现->知识点整理-线段树<-知识点讲解：首先对于线段树，其实与其他各种树都是一样的，都有着树形的结构。接下来让我们考虑一些问题： ~~给出一个数组，要求满足下面的操作： ~~①给定三个值x，y，z，要求吧【x，y】区间的每个数都加上z。 ~~②给定两个值x，y，要求输出【x，y】区间的最大值（or最小值or和）。如果我们用暴力做这些问题，那么对于操作
2017-11-07 19:34:29
6130
原创 czl的知识点整理3——LCA
-知识点整理3-最近公共祖先-典型题目知识点欧拉序解法Trajan解法->知识点整理3-最近公共祖先<-典型题目：HDU 2586 How far away？ 洛谷 P3379 LCA模板题知识点：首先我们先了解一下什么是祖先。学习过树的结构之后我们可以知道每一个除了根节点以外的节点都有一个父亲节点，那么父亲节点的父亲是什么呢？通常的，我们都把一个节点所有的父辈节点都称之为祖先，同时还有一
2017-10-27 20:42:50
264
原创 czl的知识点整理2——高斯消元
-知识点整理-高斯消元-典型题目知识点代码实现->知识点整理-高斯消元<-典型题目：XJOI 1822：Civilization知识点：高斯消元其实在小学初中解多元一次方程的时候已经接触过了。其实，高斯消元就是建立在方程中加减消元和乘除消元之上的。只不过，高斯消元法把这两种方法应用于矩阵之中，使得高斯消元的复杂度达到O（n³）（相比于真正的去解方程可是要快的多了，想一想你手解100000元一次方
2017-10-19 18:54:21
238
原创 czl蒟蒻的XJOI类型训练2
-XJOI类型训练2-最小生成树T1-Prim算法包含知识点-最小生成树知识点讲解代码实现T2-Kruskal算法包含知识点-最小生成树知识点讲解代码实现单源最短路问题T3-Dijkstra算法包含知识点-单源最短路知识点讲解代码实现T4-Floyed算法包含知识点-任意两点最短路知识点讲解代码实现T5-SPFA算法包含知识点-有负权的单源最短路知识点讲解
2017-10-18 21:02:53
187
原创 czl蒟蒻的XJOI类型训练1
-XJOI类型训练1-T1-基数排序包含知识点-基数排序法典型题目知识点讲解代码实现T2-哈夫曼树包含知识点-哈夫曼树的构造典型题目知识点讲解代码实现T3-无向图的连通分量包含知识点-并查集典型题目知识点讲解代码实现T4-奇数幻方包含知识点-幻方典型题目知识点讲解代码实现T5-最近点对包含知识点-分治典型题目知识点讲解代码实现T6-神奇的供水系统
2017-10-18 19:47:40
468
原创 czl蒻蒟的OI之路16
XJOI奋斗群蒻蒟群群赛17 RANK排名9T1Increasing SequenceTLE一次AC题意分析过程给出题解T2Jumping JackWA一次后AC题意分析过程给出题解T3How Many Squares 已AC题意分析过程给出题解T4Swaps in PermutationWA两次之后AC题意分析过程给出题解
2017-10-08 21:00:15
225
原创 czl蒻蒟的OI之路14、15
XJOI奋斗群蒻蒟群群赛15 RANK排名9T1Fashion in Berland 已AC题意分析过程给出题解T2s-palindrome WA四次后AC题意分析过程给出题解T3Exponential notation WA三次后AC题意分析过程给出题解T4Swaps in PermutationWA两次之后AC题意分析过程给出
2017-09-26 17:54:44
337
原创 czl蒻蒟的OI之路13
XJOI奋斗群蒻蒟群群赛10 RANK排名6T1Compote 已AC题意分析过程给出题解T2Decoding已AC题意分析过程给出题解T3Tram已AC题意分析过程给出题解T4Green and Black TeaWA三次之后AC题意分析过程给出题解T5Numbers Exchange 已AC题意分析过程给出题解T6Music in Car题意分析过程给出题解T
2017-09-24 14:16:31
294
原创 czl蒻蒟的OI之路10、11、12
好久没有发微博了表示自己也很绝望啊今天来个三连击XJOI奋斗群蒻蒟群群赛11 RANK排名11T1The Wall WA一次后AC题意分析过程给出题解T2Maximal Area Quadrilateral WA六次后AC题意分析过程给出题解T3Tourist Problem WA两次后AC题意分析过程给出题解T4Bubble Sort
2017-09-22 18:07:12
333
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人