- 博客(85)
- 收藏
- 关注
RSS订阅原创 换根dp入门小结
换根dp释义：换根dp应该可以算作树形dp的一种。在一般的情况下我们进行树形dp的时候常常都会以一个固定的节点来作为根节点，但换根dp故名思意就是在进行树上dp操作时会需要进行换根操作的一类特殊的树形dp(个人理解）进行换根的套路操作：1、在树上自底向上进行dp操作2、在树上自顶向下进行dp操作3、根据题目要求计算答案接下来以具体的题目作为例子进行换根dp的练习：一、树的中心题目链接题意一目了然是要叫我们找到当前树中到其他节点最远距离最近的点的距离。思路：分析题意首先是要明确树中节点的
2021-07-10 20:47:19
661
1
原创 The 15th Chinese Northeast Collegiate Programming Contest D题
题目链接大致题意：给你一段含n个数字的序列，对于这段序列可以有m次操作。操作有两种类型：1、（1，L，R）表示将（L，R）区间的每个数加自身的lowbit值（若一个数为x,则其lowbit值为x&-x）.2、（2，L，R）询问区间（L，R）数字之和思路：一眼看上去知道要用线段树维护区间信息，但对于操作1对区间每个数都需要加上其lowbit值，似乎直接用单点修改来做会T得很惨，但是仔细一想加的值很特殊是该数的lowbit的值，我们仔细一想便会发现一个数最多加logn次其lowbit值后继
2021-07-07 22:18:44
854
原创 可持久化并查集 （可持久化数组+并查集）
题目链接可持久化数组相关链接利用可持久化数组进行维护每个节点的父亲节点，对于题目中给出的三种操作：第一种操作即将a所在集合的根节点的父亲节点赋值为b所在集合的根节点，直接在可持久化数组上进行单点修改操作。第二种操作直接将当前版本号赋值为第k次修改的版本号。第三种操作，直接查询两点所在集合的根节点是否相同即可，不过在可持久化数组中不支持路径压缩，所以我们只能直接递归查找当前节点的父节点，直到找到该集合的根节点，无疑直接这样查找很容易超时，所以我们可以考虑在进行合并操作的时候采用按秩合并，将深度小的集
2021-07-01 10:38:38
183
原创 可持久化线段树(主席树)相关模板题
一、可持久化数组：题目链接个人感觉可持久化数据结构的精髓就在于最大限度的使用以前的资源也就是最小的增加新的资源。对于这道题我们可以将原始数组用一个普通线段树来存，当我们需要修改的时候只需要将需要修改的元素在线段树中所在的链修改即可，其他的都可以使用原来的数据。借用别人的图分析一下：这是原始数据构成的线段树，一共有六个数据。假如我们需要在此基础上修改第二个元素：可以看出橙色部分即为我们需要修改的部分这就是修改了第二个元素以后的可持久化数组的样子，绿色为修改第二个节点后的线段树版本，在修改的
2021-06-29 17:46:35
189
原创 无向图三元环计数 (思维，图论)
题目链接思路：看完这题第一眼思路是直接枚举两条邻边(m^2)，但一看数据范围2e5便知道这个办法不可行，于是考虑将图简化。简化方法：将原图中度数小的点向度数大的点连一条有向边，如果度数相同便从编号小的向编号大的连边，可以发现这样简化完后的新图是一个DAG(因为如果要成还的话环里的边必然有一条是从度数大的连向度数小的，或者从编号大的连向编号小的，与规则矛盾)，而原图中的每个三元环(u,v,w)在新图中一定有一个(u->v,u->w,v->w)的子图与之相对应，我们只需要在新图中枚举每个
2021-06-26 10:40:34
556
原创 方格取数（dp）
题目链接大意：这题是数字三角形的进阶版，数字三角形是从左上到右下路径的最值，而这题是从左上到右下的任意两条路径的和的最值。思路：因为是两条路径每一步一定有两个点（可能重合），所以可以根据闫氏dp分析法将状态f(i1,j1,i2,j2)表示为：两条路径分别走到(i1,j1),(i2,j2)的所有路径的和的最大值，因为每条路径每一步都有两个可以前进的方向，所以可以将状态集合划分成四个部分f(i1-1,j1,i2-1,j2),f(i1-1,j1,i2,j2-1),f(i1,j1-1,i2-1,j2),f(
2021-02-22 11:24:20
137
原创 滑动窗口
题目链接思路：一眼看过去就知道是滑动窗口模板题，用单调队列来做的，当队首元素下标在滑动窗口之外则弹出队首，否则输出队首元素。ac代码：#include <iostream>#include <algorithm>using namespace std;const int maxn=1e6+5;int cnt[maxn];int f[maxn],ff[maxn];int main() { int n,k; cin>>n>>k;
2021-02-22 11:05:23
51
原创 Number of Simple Paths （拓扑找环+dfs）
题目链接题意：给一个n个节点n条无向边的无向图，需要找出图中存在多少条长度大于1的路径。思路：因为边数大于1，只比树的边数多一条边，所以图中有且仅有一个环。很明显我们可以发现环上同一个子树的两点间有且仅有一条路径，不同子树间的两点存在两条路（环的两个方向），所以我们只需要找出环上的节点和它们分别的子节点数即可通过规律找出路径数。ac代码：#include <iostream>// 拓扑+dfs#include <algorithm>#include <cstdi
2020-12-26 00:18:02
176
原创 2020icpc(上海) 重现赛
重现赛只过了两题 ，还是太菜了…补吧。B. Mine Sweeper II (思维题)如果B图与A图不同的超过（n*m）/2个直接输出A的反图，反之输出A图#include <iostream>//2020icpc上海 B 思维题#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <cmath>#include
2020-12-19 15:09:04
967
2
原创 Distinct Sub-palindromes（思维题）
题目链接题目：设一个字符串的值为其所含回问子串的个数，给你一个数字n，全由小写字母构成的长度为n的值最小的字符串由多少个。思路：分两种情况，当n小于三的时候任意字符串的值都相等，稍微想想就知道如果字符串中每个字符不同那么值就为长度，当有字符是同一字符时，虽然长度为1的回文子串少了但长度大于1的会问子串必然增加所以值还是等于1.但当n大于3时情况发生了改变，含有相同字符时子串可能不会增加如：abca,原因是因为中间含有两个不同的字符导致不回文，所以我们构造字符串时相同字符之间至少要隔两个字符，又为了使回文
2020-07-21 21:10:15
265
原创 [USACO5.4]奶牛的电信Telecowmunication（最小割点）
题目链接题意：给你一个无向图，问最少割去多少个点使源点和汇点不连通。思路：问的是割点啊，就不能直接用最大流求最小割，因为内求的是割边。所以这里需要将点拆分成由一条有向边链接的两个点（其中所有入度的边连接原点，所有出度的边连接拆出来的点，原点和拆出来的点间由一条权值为1的有向边相连，因为一个点只能够被删除一次）。那么对于每一条无向边，相当于我们要补成一个环。将点拆分完后直接跑最大流求出拆点后的最小割即可。需要注意的是源点和汇点肯定是不能删除的所以源点和汇点拆分后连接两个点的边边权赋为inf。ac代码：
2020-07-16 22:41:45
171
原创 P3376 【模板】网络最大流
题目链接存模板：最大流EK模板：#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <queue>using namespace std;#define int long longusing namespace std;const int maxn = 205;con
2020-07-14 23:31:07
117
原创 Drainage Ditches（网络流最大流入门题）
题目链接题意：很直白，就是告诉你一个图，求源点1到汇点m的最大流思路：模板题，我用的EK，就是不断地在残余网络中找增广路，直到找不出增广路为止。增广路：就是从源点到汇点能增加流量的路径。残余网络：在一个网络流图上，找到一条源到汇的路径（即找到了一个流量）后，对路径上所有的边，其容量都减去此次找到的量，对路径上所有的边，都添加一条反向边，其容量也等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”ac代码：#include <iostream>#include <a
2020-07-14 22:32:50
124
原创 2020暑假牛客多校第一场 j：Easy Integration
题意：给你一个积分公式，给你一个n，问积分公式的值取模后的结果思路：个屁的思路，直接结论这积分公式值的结论直接就是(n!)^2/(2n+1)!，求个阶乘，用费马小定理给1/（2n+1）！取个模就完了。（比赛的时候一直往杨辉三角上套，结果是个结论题？）ac代码：#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>
2020-07-12 21:59:49
177
1
原创 局域网(最小生成树思维题)
题目链接思路：根据题意要使得图中不成环，那么删去边后剩下的图肯定就是一棵树，有因为有使得删去边的权值总和最大，就意味着剩下那棵树的权值总和要尽量小，毫无疑问剩下那棵树就是这幅图的最小生成树，所以直接球最小生成树就行了。ac代码：#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <v
2020-07-10 23:18:12
238
原创 炸铁路（tarjan求割边）
题目链接思路：根据题目所说只炸一条铁路就要造成两个城市无法相互到达，换成人话就是删去一条边后两点无法连通，即连通分量增加，能造成这一效果的边无疑只有割边，所以直接tarjan求割边即可。ac代码：#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <vector>using
2020-07-09 19:24:36
189
原创 How far away ？（树上倍增查找最近公共祖先(lca)）
题目链接前言：在边看题解边wa了近20发后的状态，唉，，，感觉灵魂出窍了题意：给你一颗由n个点组成的树，再询问m次，每次两个点，问树上两点间的距离。思路：先将无根树转化为有根树，若两点为a，b，则树上两点的距离就为dist[a]+dist[b]-2*dist[lca(a,b)],其中dist为该节点到根节点的距离。树上倍增：（明天补）ac代码：#include <iostream>#include <algorithm>#include <cstdio>
2020-07-08 22:35:41
230
原创 D. Odd-Even Subsequence(二分答案+贪心)
题目链接题意：给你一个序列，从这个序列中找一段顺序子序列（元素在子序列中的先后关系和在原序列中一致），定义一个g，g=min(max(子序列中下标为奇数的元素)，max（子序列中下标为偶数的元素）)，找出k的最小值。思路：不难看出这是个二分的题，关键是check函数怎么写，分析式子我们可以发现要让式子成立只需要让子序列中下标为奇数元素最大值或下标为偶数元素最大值不大于g即可，换句话说只需要在原序列中找出一段不连续的且值不大于g的序列，再判断长度即可。ac代码：#include <iostre
2020-06-27 18:43:05
485
原创 洛谷题单——动态规划的引入
前言：好久没做dp，又变菜了。。。数字三角形 Number Triangles思路：由题很容易可以看出状态转移方程：dp[i][j]=cnt[i][j]+max(cnt[i+1][j],cnt[i+1][j+1]).ac代码：#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespac
2020-06-25 14:55:47
143
原创 呼兰河传（数论）
题目链接前言：数学问题都tm死脑细胞啊。。。。思路：其实所有数字都可以看作是多个质数累乘的乘积，比如36=2 * 2 * 3 * 3，那么要求一段序列的数字的最小公倍数最大，只需要对每个数字进行质因数分解统计每个质因数累乘次数的最大值最后相乘即可，比如要求21 36 63的最小公倍数的最大值21=3 * 7，36=2 * 2 * 3 * 3，63=7 * 3 * 3，其中2累乘次数最大为两次，3为两次，7为一次，LCM最大为2 * 2 * 3 * 3 *7=252。ac代码：#include &l
2020-06-23 12:52:28
243
原创 牛牛爱学习（二分答案+贪心）
题目链接思路：想要二分的找到最小需要看的天数的话，其实就应该要求出在一定天数间能获得的最大知识点。贪心策略就是优先看知识点数高的书。所以我们可以先将原序列按知识点从大到小排列，再按照看书天数将书分为不同集合。如：有序列为5，4，3，2，1的书要在2天看完，那么5，4就是每天看的第一本书，3，2就是每天看的第二本书，1就是第一天看的第三本书。ac代码：#include <iostream>#include <algorithm>#include <cstdio>
2020-06-22 23:23:55
238
原创 Master of GCD（差分）
题目链接题意：给你一个含n个1的序列，让你进行m个操作，每个操作要向一段区间进行乘2或3，问你最终这段序列的最小公约数为多少。思路：最终每个数肯定是有一定数量的2和3累乘得到，所以直接找每个位置2和3乘的最小次数就是整段序列的最小公约数（注：用cin，cout会t，别问为什么，问就是自己试过。。。。）ac代码：#include <algorithm>#include <cstdio>#include <cstring>#include <cmath&g
2020-06-22 21:59:14
282
原创 牛牛走迷宫（bfs最短路）
题目链接思路：从题意走的步数最小可以知道这道题肯定是求最短路（一般我用bfs），但字典序最小卡住了我，其实要求字典序最小其实我们只需要把每步走的四个方向所代表的字符按字典序最小排列即可，即“DLRU”(先向下，再向左，再向右，最后向上)，那么bfs时字典序最小的路径总会在字典序的路径之前，这样所求的最短路便是符合要求的最短路。ac代码：#include <iostream>#include <algorithm>#include <cstdio>#includ
2020-06-21 09:45:04
548
原创 Codeforces Subsequences（组合数学）
题意：就是给一个数字t，然后要你构造出一个从右到左可以找出t个codeforces的字符串。思路：看了样例我就在codeforces后加s的这条路上越走越远。。。其实计算codeforces的个数=每个字符个数的乘积，如ccoodeforces就可以从右到左找出221111111*1=4个codeforces那他也可以满足t=1到4的情况，所以我们可以逐步增加每个字符的数量，直到乘积大于t即可。ac代码：#include <iostream>#include <algorith
2020-06-19 09:39:20
582
2
原创 LuoJie学姐南朋友的求助（差分应用）
没用过差分的蒟蒻，唉。。。题目链接差分：如果有一个原数组A，那么他的差分数组B，除了第一项与A相等外，其余项B[i]=A[i]-A[i-1],其实就是存相邻两项间的差值。本题思路：我们可以先构造出原数组的差分数组，根据差分数组存相邻两项差值的特性，如果我们加减了差分数组其中一项，那么其后各项在原数组中的值也会跟着改变。如：若A数组：1 2 3 4 5，其差分数组：1 1 1 1 1，当差分数组变为：2 1 1 1 1，转换成原数组就会变成：2 3 4 5 6 .总结就是：若我们要在一段区间[l,
2020-06-18 11:32:47
96
原创 Til the Cows Come Home (dijsktra堆优化，bellman_ford)
题目链接以前用朴素dijsktra做过，由于学了几种新算法，用这道题练练朴素dij版dij堆优化：和原理当然是和朴素版的dij差不多，不过由于因为引进了优先队列，可以较快的找出当前点集中到源点举距离最短的点。ac代码：#include <iostream>//dijkstra堆优化#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#in
2020-06-15 17:15:51
154
原创 小A买彩票（dp枚举）
题目链接思路：根据题目先给出概率公式：不亏本的数量/总数量。因为每买一张彩票有4种方法，那么买n张彩票就有4的n次方种方法。因为每张票3元，所以不亏本的金额范围只能为3n——4n。ac代码：#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;#define i
2020-06-01 17:57:39
339
原创 Printer Queue（优先队列）
题意：给你n,m其中n是指打印文件的份数，m是你要打印的文件在队列中的位置，然后再给你n个数字代表每份文件的优先级，优先级越高的越先打印，如果当前队列队首文件优先级不是最高则将其放在队列最后，每份文件打印需一分钟，问打印到你的文件需多少分钟。思路：将原本序列的文件的优先级及初始位置存入一个普通队列中，然后再按优先级的大顶堆将队列优先级存入优先队列中，将普通队列队首与优先队列队首比较如果优先级不相等就排到队尾，如果相等则将分钟数加一并在两个队列中移除这分文件，如果即相等并且该元素初始位置与m相等则输出分钟
2020-05-23 21:46:53
495
原创 atcoder 168 C
题意：给出时针和分针的长度a,b,然后再给出当前小时数和分钟数，叫算出当前时针和分针两针尖的距离。思路：先算出两针的夹角，在根据余弦定理算第三边即可。难点：pi的表示方法。ac代码：#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const double pi=acos(-1.0);//pi的表示int ma
2020-05-22 18:25:19
212
原创 二分答案题型小结
二分答案类型的题在之前不经常做所以尽管训练题比较简单，但还是做起来有点吃力。二分答案顾名思义就是通过不断二分检验所有可能的答案值是否满足题目条件，直到选出我们需要的答案（个人理解。。。）个人感觉二分答案问题都是在研究的是某种意义上的最大 ，最小值问题。例题1：poj 1064——Cable master题意：给n段长度不同的电缆，要将他们均分成k段，问每段最长能分成多少。思路：首先我们可以先判断最长长度的边界是多少，显然每段最小就是0，最大不会超过所有电缆长度和。然后再二分这个区间，判断以当前长
2020-05-12 09:18:02
228
原创 平衡二叉树的判定
平衡二叉树：每个节点的左右子树高度差不大于1的二叉树。方法：递归探索每个节点的左右子树，并判断高度差是否大于一。代码：#include <iostream>#include <algorithm>using namespace std;#define int long longstruct node{ char val; node *l,*r;};int flag;node* build(){ node *T; char ch;
2020-05-11 18:03:05
153
原创 堆排序
先说说堆：首先堆是一种完全二叉树，根据特点不同分为大根堆和小根堆。大根堆呢就是树上任意非叶子节点的值都大于其左右端点（左右端点之间不在意大小），对应的小根堆就是树上任意非叶子节点值都小于其左右端点。图示：堆排序呢就是根据不同堆的特性将其整理为一个最大（小）堆后，移除根节点，并作调整的递归运算。本代码只是将乱序整理为最小堆的代码，并未真正排序（相当于进行了一次堆排序）附代码：#include <iostream>#include <cstdio>#include &
2020-05-11 17:56:37
88
原创 插入排序，希尔排序
今天刚讲的，因为学校oj某些不详的原因不能登录所以没去验证正确性先把代码贴上。直接插入排序：#include <iostream>//直接插入算法（稳定排序）O(n^2)#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#inclu...
2020-05-06 21:58:15
88
原创 最大上升子序列和（基础dp）
写这篇博客一是因为这道题比较经典，而是为了水博客。思路：和开餐馆很像（其实就是改变了一下判断条件）判断前i项的最大上升子序列和就是第i项的值加上前面i-1项最大上升子序列和中比第i项小的且和最大的序列和，如：第i项值为5，前面i-1项所代表最大和且项值小于5的是项值为3的项所代表的最大上升子序列和为4，则第i项所代表的最大上升子序列和就为5+4=9。由此的递推式：ans[i]=max(ans...
2020-04-29 20:42:26
435
原创 开餐馆（基础dp）
思路：将第i家店与前i-1家店分别比较位置如果位置合法，则判断到该店为止的前面所有店的总利润加上第i家店的利润和是否大于当前i家店所取得的利润和（因为前面有些店可能彼此间位置不合法，造成了不同位置店能取得的总利润不同），以此类推得到递推式：ans[i]=max(ans[i],p[i]+ans[j])。最后再判断出所有位置上的店能取得的最大总利润即可。ac代码：#include <io...
2020-04-29 20:21:34
429
原创 单词方阵（搜索）
题目链接思路：很直接的思路，先遍历找到单词的第一个对应字母，然后再遍历该字母的8个方向，判断第二个对应字母方向，再根据该方向判断是否能够找到其他几个对应字母即可。ac代码：#include <bits/stdc++.h>using namespace std;char A[105][105]; bool vis[105][105];int B[8][2]={0,1,0,-...
2020-04-29 15:24:29
239
原创 填涂颜色（搜索求连通块）
题目链接思路：因为数字为1的连通块一定封闭，所以如果在四条边上出现的0一定是在封闭图形外的，所以我们可以遍历四条边缘上的0标记其所在的连通块，最后没被标记的0则为在封闭图形里的0.ac代码：#include <iostream>using namespace std;#define int long longint A[65][65]; bool vis[65][65];...
2020-04-29 15:19:13
127
原创 赦免战俘（递归）
题目链接思路：将图分成四块可以发现左上角的一块全为0，然后另外三块变化相同，所以分块分别递归另外三块即可。ac代码：#include <bits/stdc++.h>using namespace std;#define int long longint A[2005][2005]; int n;void qw(int x1,int x2,int y1,int y2){...
2020-04-29 15:10:43
692
原创 大盗阿福（动态规划）
突然用动态规划的方式思考问题还不适应。。。思路：对于第i家店铺都有两个选择：盗 or not。如果不盗的话那么第i家店铺的现金其实就等于前i-1家店铺的现金，如果盗的话那么就等于前i-2（因为不能相邻）家店铺与第i家店铺的现金和。ac代码：#include <iostream>#include <cstdio>#include <cstring>#i...
2020-04-28 23:09:49
275
原创 数字组合（01背包）
就是01背包小小变形一下就不太会做了。。。。思路：当前和的方案数等于当前和减当前和当去当前正数的方案数，如：当前正数为2，和为5的方案数就等于3（5-2）的方案数，和为3的方案数又等于1（3-2）的方案数。又因为在每一种方案中每个数字只能使用一次，所以采用01背包。状态转移方程式：dp[j]+=dp[j-w[i]]。ac代码：#include <iostream>#incl...
2020-04-28 19:09:49
219
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人