typedef的博客

原创 06-02考场随笔

考场随笔A.多边形描述多边形是一个人玩的游戏。开始时在一含有 NN 个节点的多边形上玩，如图一所示，在此图中，N=4。每一个节点以一个整数标示；每一条边则以符号 +（加）或符号 *（乘）标示。这些边的编号从 1 到 N。下第一步时，先移除任何一边，之后的下法如下：‧任取一边，称之为 E，并令其两端的节点为 V1 及 V2‧先执行 E 与 V1,V2 之运算，并将结果标示于一个新节点，用来取代旧节点及边。当所有的边都被移除时，游戏即结束，而得分 (score) 则为最后留下之节点标示之值。输

原创 树形DP&环形和后效性处理

树形dp概念依然是O(n)O(n)O(n)类型的dp,通过dfs或bfs实现小状态向大状态的转移,本质是在树上更方便表示的线性动规例题P2014 [CTSC1997]选课是做过的题,就不详细说了树上的分组背包POJ3585从树上选取一个源点作为根,每条边都有一个容量,该树对应的叶子结点为汇点问应当选取哪个点为源点,该树的流量最大朴素算法:枚举每个点作为源点,用树形dp求出最大流量也就是从下往上取mind[x]表示以xxx为根的子树所得的最大流量d[x]=∑y∈son(x){mi

原创 啥也不是!

原创 网络流笔记

网络流持续更新中…几句话网络流的思维方式类似DP一般来说做题流程为:题意分析建图默写板子其中建图是关键,类似DP中的转态表示,状态转移概念流网络一张有向图,有两个特殊的点,源点(S)(S)(S),汇点(T)(T)(T)边权表示该边容纳流量的最大值G=(V,E)G=(V,E)G=(V,E)[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MLunYZb1-1620460456314)(C:\Users\Typedef\Pictures\截图\w

原创 莫队

莫队优雅的暴力用法在nnn\sqrt{n}nn​的时间内离线求解一段区间内不同数字的个数实现暴力做法:用一个桶记录每种颜色出现的数量随后扫描桶,进行统计显然会超时我们对询问进行排序,以便利用前一个询问的信息更新下一个询问我们建立双指针,每次移动指针加入新数这便是莫队算法的雏形(是暴力,但不优雅)很容易发现我们刚才的做法仍然是O(n)O(n)O(n)的,并没有得到优化通过调整查询的顺序,我们可以把复杂度降到O(n)O(\sqrt{n})O(n​)我们通过排序,可以使得其中一个指针

原创 数学基础知识

数学基础知识线性筛略高斯消元通过高斯消元,我们可以再O(n3)O(n^3)O(n3)的时间复杂度内求出线性方程组的解{a11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2⋮an1x1+an2x2+⋯+annxn=bn\begin{cases}a_{11} x_1+a_{12}x_2+\dots+a_{1n}x_n=b_1\\a_{21} x_1+a_{22}x_2+\dots+a_{2n}x_n=b_2\\\vdots\\a_{n1} x_1+a_{

原创 2-SAT

2-SAT引入我们有很多个变量,分别为x1,x2,…,xnx_1,x_2,\dots,x_nx1​,x2​,…,xn​每个变量有真假两种情况我们有几个条件,由几个变量或起来,可以添加非,如:x1∪x2∪x3x_1∪ x_2∪ x_3x1​∪x2​∪x3​¬x2∪¬x3∪x4\neg x_2∪\neg x_3∪ x_4¬x2​∪¬x3​∪x4​在SAT问题中,我们求出这些变量的取值,满足许多个这样的条件然而不幸的是,SAT问题是一个NPC问题,我们没有办法在多项式时间内求出解不过,对于2

原创 树链剖分

树链剖分用途将任意一条树上路径转化为不超过lognlognlogn段区间将一棵树转化成一个序列这样我们求树上路径和就和以用线段树求复杂度O(log2n)O(log^2n)O(log2n)求法&概念求出每一棵子树的节点个数其中某个点的,所在子树的节点个数最多的那个儿子,被称为该点的重儿子其余的被称为轻儿子子树大小相等时,重儿子可以任选我们预处理出每个子树的size,并求出来所有重儿子我们引入几个概念:重边:连接一个重儿子和它的父节点的边**轻边:**其余的边重链:

原创 后缀数组

后缀数组定义后缀是什么就不用说了吧…在后缀数组中,我们把从第i个下标开始的后缀称为第i个后缀(我个人比较习惯字符串下标从1开始)这样一来我们得到n个后缀通过倍增的思想,我们可以再O(nlogn)O(nlogn)O(nlogn)的时间内对这n个后缀按照字典序排序变量名:sa[i]:表示排名第i的后缀是第几个后缀rk[i]表示第i个后缀的排名是多少height[i]表示sa[i]与sa[i-1]的最长公共前缀(LCP)举个例子:字符串aababb的后缀分别是:aababbaba

原创 板子

splay/************************************************************************* > File Name: splay.cpp > Author: typedef > Mail: [email protected] > Created Time: 2021/2/13 19:55:00 *******************************************

原创 LaTeX

LaTeX\LaTeXLATE​X≤≥{1…2…3…μπσδΠΔΣ⌊⌋⌈⌉abx⟺×x12x1a+b\leq\geq\begin{cases}1\dots\\2\dots\\3\dots\\\end{cases}\mu\pi\sigma\delta\Pi\Delta\Sigma\lfloor\rfloor\lceil\rceil\frac{a}{b}\sqrt{x}\Longleftrightarrow\timesx_1^2x_{1}^{a+b}≤≥⎩⎪

原创 莫比乌斯反演

莫比乌斯反演应该比较清晰易懂吧(雾莫比乌斯函数定义x=p1α1p2α2…pkαk,其中pi是质数,αi是正整数x=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k} ,其中p_i是质数,\alpha_i是正整数x=p1α1​​p2α2​​…pkαk​​,其中pi​是质数,αi​是正整数μ(x)={case1:存在αi≥2,此时μ(x)=0.case2:所有的αi=1,此时μ(x)=(−1)k.例:μ(6)=1,μ(7)=−1,μ(8)=0.\m

原创 Tarjan

重学图论前置芝士强连通:对于点x,y,存在一条x到y,和y到x的路径强连通图:图中每两个点都强联通强联通分量:极大强联通子图都是定义在有向图中的应用:缩点我们对一张图进行DFS,可以得出一颗搜索树对于搜索树上的每一条边,我们都可以归为四类:树枝边(x,z):x是y的父节点前向边(x,y):x是y的祖先节点后向边(x,y):就是前向边反过来横叉边(y,a):连向其他树枝的边(需要注意的是,(y,b)并不是一条横叉边,因为b节点是第一次被访问到,因此就成了树枝边)

原创 _vimrc

描述适用于 Windows 环境的gVim可用于 C++ 程序编译覆盖原有的文件即可使用内容""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 显示相关 """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""winpos 5 5

原创 AcWing1321取石子

题意A(Alice)A(Alice)A(Alice)和B(Bob)B(Bob)B(Bob)在玩取石子游戏共NNN堆石子排成一排,A和B轮流进行如下操作(A是先手):从某堆石子中取走一个合并任意两堆石子无法进行操作的人输让你判断A是否有必胜策略有多组测试数据哦思路假设:我们当前所有堆得石子个数都严格大于1我们令 b=堆数+石子总数-1此时先手必胜⟺\Longleftrightarrow⟺ b是奇数为什么呢?每个操作一会使石子总数减一二每个操作二会使石子堆数减一因此b就是操作总

原创 可持久化数据结构

文章目录可持久化数据结构两句闲话可持久化 TrieTrieTrie实现例题可持久化线段树(主席树)实现例题可持久化数据结构两句闲话可持久化的前提:该数据结构本身的拓扑结构在操作时保持不变常见的可持久化:堆,线段树,树状数组,trie…trie\dotstrie…常见的不支持持久化:平衡树…那么可持久化能解决什么问题呢?保存数据结构的所有历史版本 git暴力备份?肯定不行 MLE+TLE类似于git,可持久化数据结构只会记录每一个版本和前一个版本不一样的地方以线段树为例,每次操作最多

原创 树状数组复习

文章目录树状数组复习功能原理操作初始化修改查询应用题意思路代码进阶玩法区间修改,单点查询思路代码区间修改,区间查询思路代码树状数组复习功能快速求前缀和 O(logn)O(logn)O(logn)快速修改某数 O(logn)O(logn)O(logn)原理二进制拆分x=2ik+2ik−1+⋯+2i1x=2^{i_k}+2^{i_{k-1}}+\dots+2^{i_1}x=2ik​+2ik−1​+⋯+2i1​ik≥ik−1≥⋯≥i1i_k \geq i_{k-1} \geq \dots \

原创 笔记

一.区间相关区间和：前缀和区间增减：差分+前缀和单调区间：二分查找区间可加：线段树复杂区间操作：分块数列中出现删除操作:链表二.搜索相关最优性剪枝:当前代价大于目前求得的最小代价可行性剪枝:明显不符合题意,或估算最小代价,大于已求则返回(最优性)优化搜索顺序:题目中明显指出(如用最少物品填满),进行排序后再搜索不入流剪枝:能剪就剪,但是不能牺牲正确性,也不能效率太低,会得不偿失广搜记得出队，v数组记录是否在队里，避免重复入队；深搜处理好边界，v数组记录是否访问过三.输入

原创 拓扑排序

概念“对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。”——《百度百科》上面这一段已经说得很清楚了对于一个有向图,我们需要确定他节点的顺序,使得它的所有出边指

原创 AcWing344. 观光之旅

link代码&思路/************************************************************************* > File Name: p344观光之旅.cpp > Author: typedef > Mail: [email protected] > Created Time: 2020/11/16 21:09:16 ******************************

原创 传递闭包

概念“传递闭包、即在数学中，在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。” ——《百度百科》人话 : 建立传递闭包的过程,就是给定一个有向(无向)图,对于节点 i 和节点 j ,如果他们联通但不直接相连,我们就建一个 i 到 j 的边.求法我们可以用 Floyd 算法在 O(n3)O(n^3)O(n3) 的时间内求得传递闭包我们用 d(i,j) 表示原图 , g(i,j) 表示它的传递闭包g(i,j) 是一个无权图,若从 i 出发,可以到达 j 则为 1 ,否则为 0初始

原创 P1522 [USACO2.4]牛的旅行 Cow Tours

link代码&思路#include<bits/stdc++.h>#define x first#define y second//保险起见别用defineusing namespace std;typedef pair<int,int> pii;const int N=152;const double inf=1e20;int n;char g[N][N];pii q[N];//保存坐标double d[N][N],maxd[N];//d是邻接矩阵,m

原创 P2872 [USACO07DEC]Building Roads S

link思路整理没啥难的…就一裸的最小生成树开始的时候建一个完全图然后把已有的边代价设为零跑一边Kruskal就行了注意 : 边数一定要开到N*(N-1)/2+1,因为是完全图,否则会爆RE还有就是记得开double代码/*数组没开够，爆零两行泪ll开成 int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪空间

原创 洛谷 P1040 加分二叉树

link思路整理中序遍历有一个很重要的性质,就是一颗树的中序遍历 [L,R] 的一个连续的子区间,一定对应它的一颗子树,我们用 [L,K] 表示自然,这颗二叉树的子树就是 [L,K-1],[K+1,R] (根节点 K )然后,对于每个区间我们都要枚举 k ,以便求出最大得分很容易想到,f[l][r]=max{f[l][k-1]*w[k]*f[k+1][r]}于是,难点就在于怎样求出该方案 (答案不唯一,建议SPJ)可以用 g[l][r]表示区间 [L,R] 对应的根节点,来记录每次的决策这

原创 AcWing 1069. 凸多边形的划分

link思路整理乍一看好像没什么思路,但是不难看出每次找一个点,就会把当前区间分成两半,分开求两个区间在加上断开的代价就是整个区间的代价了那就区间dp呗(见下图)我们用f[L][R]表示点L,L+1,L+2....R-1,R的划分最小代价也就是多边形(L,L+1),(L+1,L+2)...(R-1,R),(R,L)的划分代价嗯...大概就是这样低精代码:/*数组没开够，爆零两行泪ll开成 int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两

原创 P5785 [SDOI2012]任务安排

link代码还是有些问题…/*数组没开够，爆零两行泪ll开成 int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪空间开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪文件不保存，爆零两行泪文件不读入，爆零两行泪文件不输出，爆零两行泪*/#includ

原创 P2608 [ZJOI2010]任务安排

/*数组没开够，爆零两行泪longlong开成int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪线段树开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪没用freopen，爆零两行泪*/#include<bits/stdc++.h>#defin

原创 AcWing 1087. 修剪草坪

link双倍经验三倍经验/*数组没开够，爆零两行泪longlong开成int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪线段树开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪没用freopen，爆零两行泪*/#include<bits/stdc

原创 AcWing 1090. 绿色通道

link双倍经验/*数组没开够，爆零两行泪longlong开成int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪线段树开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪没用freopen，爆零两行泪*/#include<bits/stdc++.h&

原创 AcWing 1089. 烽火传递

link/*数组没开够，爆零两行泪longlong开成int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪线段树开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪没用freopen，爆零两行泪*/#include<bits/stdc++.h>u

原创 AcWing1088.旅行问题

link代码好像还有一点问题/*数组没开够，爆零两行泪longlong开成int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪线段树开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪没用freopen，爆零两行泪*/#include<bits/std

原创 AcWing135. 最大子序和

link/*数组没开够，爆零两行泪longlong开成int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪线段树开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪没用freopen，爆零两行泪*/#include<bits/stdc++.h>u

原创 Acwing1307. 牡牛和牝牛

link/*数组没开够，爆零两行泪longlong开成int，爆零两行泪多组忘清空，爆零两行泪 dp 没初值，爆零两行泪深搜没边界，爆零两行泪广搜忘出队，爆零两行泪输入没加 &，爆零两行泪模数没看见，爆零两行泪 -1 不输出，爆零两行泪越界不特判，爆零两行泪线段树开一倍，爆零两行泪无向变有向，爆零两行泪题意没审清，爆零两行泪文件名起错，爆零两行泪调试忘删除，爆零两行泪没用freopen，爆零两行泪*/#include<bits/stdc++.h>u

原创 UVA1316 Supermarket

题目描述link给定n个物品，第i件物品有如下信息：卖出去可以转p[i],物品过d[i]天过期，且过期后卖不出去。卖掉一件物品用1天，求最大收益。思路整理首先，为了维护最大收益，我们可以维护一个小根堆来找出已卖出物品的最小价值。这是一个类似于dp的思想（其实不是），即在第t天时（t是堆中元素的个数），堆中存的是已经卖出的物品的价值。非常不容易想到，对于i这一个物品，若当前是第d[i]天（马上要过期了），我们可以取出堆顶（卖出物品中价值最小的），与之同p[i]比较。如果发现p[i]更大，我们可以

原创 poj3974 最长回文子串

题目描述link输入格式多组数据，每次输入一个字符串，以"END"结尾输出格式对于每个字符串，输出它最长回文子串的长度AC代码#include<iostream>#include<algorithm>#include<cstdio>#include<cmath>#include<string>#include<cstring>using namespace std;int P=131,len;char s[