- 博客(241)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 区间dp模板
区间dp模板区间dp可以分为几类分支。环形区间dp，区间dp记录方案数，区间dp和高精度结合，二维区间dp环形区间dp1068. 环形石子合并
2022-04-10 22:15:32
1098
原创 状压dp -- 状态压缩dp
状态压缩dp状态压缩dp 分为两种，一种是棋盘式，也叫做基于连通性，基础题是291. 蒙德里安的梦想，另一种是集合形式的，基础题目是最短Hamilton路径。连通性状压dp一般讲棋盘按照行或者列分开考虑，可以先算出单行状态下的合法状态，然后下一行的合法状态受上一行的状态影响，所以可以有关系矩阵表示f(a,b)是否合法，再进行dp的转移方程。例题AcWing 1064. 小国王AcWing 327. 玉米田AcWing 292. 炮兵阵地集合覆盖例题AcWing 524. 愤怒的小鸟Ac
2022-04-09 17:09:01
316
原创 树状数组模板
树状数组模板基本原理基础功能 单点更新，区间查询快速求前缀和 O(log(n))修改某一个数字 O(log(n))下面图片来自acwing的课程：原始数据是A数组,用C(x)代表A[x-lowbit(x)+1,x]区间内的元素之和，然后用小矩形代替C(x)画图，C(x)覆盖范围就是他们的求和的范围, 下图中的数组可以形成一棵树，C(x)覆盖区间大小决定层高，红线代表上层可以由下层连线的部分求和得出。每一个点x都有儿子，儿子的数量是x-1的二进制组成中1的个数。例如16(10000)的儿子
2021-12-06 12:26:16
826
原创 并查集模板
并查集模板用处1.合并两个集合2.查询某个节点的祖宗节点优化1.路径压缩，最坏情况 log(n)2.按照秩合并，最坏log(n)使用上面的两个优化后，时间复杂度O(alpha(n))扩展1.记录集合大小集合大小绑定在根节点上，在合并的时候更新2.每个点到根节点的距离这个属性放在吗每个点上，例题：食物链（带权并查集(维护相对距离)，扩展域并查集(枚举所有可能性)）3.链表染色模板在这里插入代码片例题AcWing 1250. 格子游戏 ： 并查集的应用之一，并查集判环..
2021-12-02 16:35:43
150
原创 刷表法 和 填表法(DP)
刷表法 和 填表法在dp问题中，当我们写出了状态转移方程的时候，一般可以直接去迭代求解。但是，与此同时有一个问题：例如 状态转移方程 是dp[i][j]=F{dp[i-1][j-1],dp[i-1][j],dp[i-1][j-1]} 这样的形态时，如何进行枚举呢？是枚举dp[i][j]，由dp[i-1][j-1],dp[i-1][j],dp[i-1][j-1]更新dp[i][j]，抑或是枚举dp[i-1][j-1]，去更新dp[i+1][j+1],dp[i+1][j],dp[i][j+1]。填表法：可
2021-11-12 00:58:21
1833
原创 动态规划 背包问题 模板
背包九讲模板（部分）背包九讲pdf资源pdf下载题目题目链接第1-10题01背包 cin>>n>>m; for(int i=0;i<n;++i){ cin>>v>>w; for(int j=m;j>=v;--j){ f[j]=max(f[j],f[j-v]+w); } }完全背包 cin>>n>>m; fo
2021-11-08 16:56:47
129
原创 多重背包模板
多重背包#include<iostream>#include<cstdio>using namespace std;const int maxn=2010;int n,m;int dp[maxn];int main(void){ cin>>n>>m; int v,w,s; for(int i=0;i<n;++i){ cin>>v>>w>>s; i
2020-12-22 20:59:35
91
原创 一般哈希 字符串哈希 hash
一般哈希来源： https://www.acwing.com/blog/content/404/拉链法拉链法，类似 图的邻接链表存储，对于一个对象x，算出对应的hash值k，将x存储在h[k]链表中(1) 拉链法 int h[N], e[N], ne[N], idx; // 向哈希表中插入一个数 void insert(int x) { int k = (x % N + N) % N; e[idx] = x; ne[i
2020-12-11 21:55:17
509
原创 KMP字符串 模板
KMP参考：https://www.acwing.com/solution/content/2286/对于S中是否含有子串p这个问题, S，p起始都是1，不是0暴力 的算法同时引入了next数组简化计算，就是在对比时，如果对比失败，p数组不再是每次前进1格，而是跳跃性的前进，这其中利用了next数组的先验信息所以每次匹配失败或者完全匹配，p的起始位置不是加1，而是跳跃性的变化，具体参考 j=next[j]next数组next数组用来存模式串中每个前缀最长的能匹配前缀子串的结尾字符的下标。 ne
2020-12-09 21:56:20
70
原创 双指针 离散化 区间融合 模板
双指针for (int i = 0, j = 0; i < n; i ++ ){ while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑}常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作...
2020-12-09 11:17:45
87
原创 前缀和 差分 数组
前缀和 差分前缀和用于求解单点更新后区间的和，差分用于求解区间更新后区间内的单个元素一维前缀和将现有数组看作是数组a ,求解A的前缀和数组SS[i] = a[1] + a[2] + ... a[i]a[l] + ... + a[r] = S[r] - S[l - 1]二位前缀和S[i, j] = 第i行j列格子左上部分所有元素的和以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[
2020-12-09 01:31:58
178
原创 UVA - 1372 Log Jumpin 贪心
问题https://vjudge.net/problem/UVA-1372分析这道题我一开始一直认为时dp,最后可参考大佬的解法才发现时贪心问题参考：https://blog.csdn.net/zstu_zlj/article/details/11881015先按照起始点的大小从小到大排序，然后对于每个i，将它看作起始点，判断i+1是否可以加入进来对于开始地第一个点，也就是cnt==1时，只要求xi[i+1]-xi[i]<=k，就能将i+1加入进来，但是cnt>1，就要求xi[i+1
2020-09-08 15:37:14
108
原创 UVA - 12235 Help Bubu 概率dp 状态压缩 记忆化搜索
问题https://vjudge.net/problem/UVA-11600分析概率dp，看到了N<=30，想到了状态压缩，然后由于N比较大，而且状态中并不是所有状态都存在，所以使用map存储状态对于M条边的处理，有两种办法，一种是用并查集，将连接起来的边连成一个集合，每次到下一个城市的时候，都去查看这个点的父节点和对应的 二进制的值（对应这个集合的所有点）参考：https://www.cnblogs.com/jerryRey/p/4857941.html或者将所有的联通点看作一个点，给这
2020-08-12 12:37:42
115
原创 UVA - 1407 Caves 树形dp 多重背包
分析参考：https://www.jianshu.com/p/065cfa72e24b状态的定义比较明显，主要是状态转移部分有点复杂，差点被绕晕了，现在觉得类似于多重背包问题//0-1背包的枚举物品 for(int i=0;i<g[node].size();++i){ pair<int,int> &temp=g[node][i]; //为了放置重复计算，j从大到小进行更新 for(int j=tot[node];j>
2020-08-09 17:45:25
172
原创 UVA - 1427 Paradev单调队列
问题https://vjudge.net/problem/UVA-1427分析这道题的状态是dp[i][j]，代表走到第i,j的位置时的收入v，采用填表法，到达i，j的选择有三种，一种是dp[i][j]=dp[i-1][j]，就是直接从上一行的第j个路口走到这一行的j路口,还有就是从左往右在i行走到j，或者从右往左，转移方程分别是 从左向右dp[i][j]=max(dp[i-1][k]+sum[i][j]-sum[i][k]) , k<j ,sum[i][j]是从i行起点走到第j个路口的累计
2020-08-09 15:11:03
125
原创 UVA - 12260 Free Goodie
问题https://vjudge.net/problem/UVA-12260分析这道题的核心在于由于P采用贪婪的方法，所以它一定在前i个中至少占到一半左右的数量，所以d[i][j].value代表在J在前i个物品中占有了j个时候的最大价值，j<=(i+1)/2，然后dp[i][j].loss代表了对于P的总价值造成的损失，设n个P的value之和为sum，P每次选择，都会对sum造成损失，如果损失最小，那么P的最终收益就会最大状态转移过程有点类似于背包问题，每次都是选择或者不选最后一个物品#
2020-08-08 17:17:39
108
原创 UVA - 662 Fast Food 区间dp
问题https://vjudge.net/problem/UVA-662分析和上一题UVA607很像，记录一下最优解的状态就行了，另外 区间【l，r】之间的最优点是(l+r)/2,这一点画图就可以看出来代码#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <string>#incl
2020-08-03 21:09:23
107
原创 UVA - 607 Scheduling Lecture 线性dp
问题https://vjudge.net/problem/UVA-607分析这是一道线性dp,多出了一个需求，就是对应最少课程数的最少DI值，所以可以先求出最少课程数，顺便求对应的最少DI值，每次更新最少课程数时，或者相等时，考虑di值的变化代码#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include
2020-08-03 17:11:09
84
原创 UVA - 590 Always on the run
问题https://vjudge.net/problem/UVA-590分析类似紫书上的例题UVA1025，记得使用转移代价矩阵记录代价，可以缩短查找的时间，时间可以倒推，也可以按照时间正序推#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <string>#include <
2020-08-03 15:46:12
79
原创 UVA - 473 Raucous Rocker 多维dp
问题https://vjudge.net/problem/UVA-473分析0-1背包问题的变形，相当于有m个背包问题共存dp[i][j][k]代表前i首歌，刻录到第j个盘子的第k分钟时的最大容量，答案是dp[n][m][t]转移方程：第i首歌不存，存两种选择，存的话，有从第j个盘子开始，也可能从j-1个盘子开始dp[i][j][k]=max{dp[i-1][j-1][k],dp[i-1][j][k-time[i]]+1,dp[i-1][j-1][t]+1}这题没给数据范围，所以WA了好几次，
2020-08-03 11:35:29
136
原创 四则运算表达式求值 中缀转后缀然后求值 （有括号）
参考算法笔记，数据结构部分栈的内容计算中缀表达式，先转换成后缀表达式，再计算#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <string>#include <vector>#include <algorithm>#include <queue>
2020-08-03 00:19:08
310
原创 UVA - 10254 The Priest Mathematician 汉诺塔变形 线性dp 大数
问题https://vjudge.net/problem/UVA-10254分析汉诺塔问题有三个柱子：https://blog.csdn.net/qq_19446965/article/details/81591945http://baijiahao.baidu.com/s?id=1651515518415910066&wfr=spider&for=pc但是本题中有四个柱子，而且规则有所变化，每次可以先使用4个柱子，按照汉诺塔的移动方式将k个盘子放置在第四个柱子上，然后在移动剩下的
2020-08-02 19:11:11
111
原创 UVA - 10453 Make Palindrome 区间dp
问题https://vjudge.net/problem/UVA-10453分析这道题应该是属于区间dpdp[i][j].len表示[i,j]区间的生成回文字符串的最小代价，dp[i][j].s是生成的回文字符串。如果s[i]==s[j],dp[i][j].len=dp[i+1][j-1].len+0, dp[i][j].s=s[i]+dp[i+1][j-1].s+s[j]如果s[i]]!=s[j],dp[i][j].len=dp[i+1][j].len+1, dp[i][j].s=s[i]+
2020-08-01 11:13:16
88
原创 UVA - 1291 Dance Dance Revolution 多维dp
问题https://vjudge.net/problem/UVA-1291分析dp[i][j][k]表示时间点在i时，左脚在j,右脚在k的状态的最小花费使用了二维数组，作为代价矩阵，简化了迈步时的代价计算代码#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <string>#in
2020-07-31 15:33:43
112
原创 UVA - 1351 String Compression 区间dp
问题https://vjudge.net/problem/UVA-1351分析代码
2020-07-31 11:31:35
99
原创 UVA - 1292 Strategic gam 匈牙利算法模板
问题https://vjudge.net/problem/UVA-1351分析这道题一开始是用树形DP来做的，后来看别人博客，发现还可用二分图最小点覆盖来做，二分图最小点覆盖等于最大匹配，使用匈牙利算法来求解https://blog.csdn.net/qq_38956769/article/details/80238896#2-k%C3%B6nig%E5%AE%9A%E7%90%86%E5%8F%8A%E5%85%B6%E8%AF%81%E6%98%8E代码...
2020-07-31 09:57:38
135
原创 UVA - 10564 Paths through the Hourglass DP
问题https://vjudge.net/problem/UVA-10564分析这道题用递归dfs,从根节点到叶子，状态从前往后的方法求解比较方便，不用保存字符串，而用递推的方法就比较麻烦些重要参考：https://www.jianshu.com/p/b73bc23897fd（重要的，比较简单的解法）http://www.bubuko.com/infodetail-309480.htmlhttps://www.cnblogs.com/ember/p/4915561.html代码#includ
2020-07-29 10:25:48
182
原创 UVA - 1366 Martian Mining
问题https://vjudge.net/problem/UVA-1366分析递推DP，dp[i][j]表示右下角坐标[i，j]的矩形能够运出最多的矿物是多少状态转移： dp[i][j]=max(dp[i][j-1]+B[j][i],dp[i-1][j]+A[i][j]);B[j][i]表示从[i][j]向上运输一条线上一共能够输出的B中矿物A[i][j]是从[i][j]从右向左运输运出的A类矿物代码#include <iostream>#include <cstdio&
2020-07-28 16:12:15
296
原创 UVA - 1452 Jump 约瑟夫环
问题https://vjudge.net/problem/UVA-1452分析约瑟夫环的变种，我对于约瑟夫环的理解还是不够，理解了约瑟夫环是一个递归问题，f[1]=0，f[i]=f[i-1]+k mod i是每次重新编号，从结果往开始递归的结果后就解决问题了参见 https://baike.baidu.com/item/约瑟夫问题/3857719?fromtitle=约瑟夫环&fromid=348830&fr=aladdin代码#include <iostream>
2020-07-28 15:28:55
96
原创 Save the President UVA - 11589
问题https://vjudge.net/problem/UVA-11589分析这题目的逻辑比较明显。建立数组A[x][y][z][t],找到安全的长方体就可以了。可以暴力求解，但是时间复杂度是O(10^10)左右的，因为有8个循环。将每个不安全的地方置为1，求子长方体的元素和，就是求前缀数组，如果前缀和是0，说明安全。注意遍历时，是从1开始的左闭右闭区间，例如两个顶点是（0，0，0...
2020-04-06 21:46:09
104
原创 Subway UVA - 10691
问题https://vjudge.net/problem/UVA-10691分析这道题的思路很直接，就是区间选点问题，然后主要是有的区间会小于-pi或者大于pi，引起问题。注意：如果点到原点的距离小于d就不用往下计算了，直接continue。别人的解法是将超出pi的区间减去pi，就只剩小于-pi的区间和正常的区间，然后全部加上2*pi，重复一遍，遍历可能的初始点，找出最优解。#incl...
2020-04-06 13:13:55
153
原创 File Fragmentation UVA - 10132 暴力
问题https://vjudge.net/problem/UVA-10132有n个相同的文件，每个文件恰好分成两半，现在有2n个碎片，求原来的文件是什么？分析这题没啥思路，直接看别人的答案吧。晕，审题不仔细，没有看到每一个文件都恰好分成两个碎片。那就很明显是暴力了。所有的原文件都是相同的，那么先按照长度排序，原文件长度一定等于最长的+最短的。然后最长的和最短的依此拼接，每个拼接结果去校...
2020-04-06 00:15:39
88
原创 Soju UVA - 1511 贪心
问题https://vjudge.net/problem/UVA-1511分析两个点（x1,y1）和（x2,y2），现在x1<x2,y1和y2之间的关系未知。∣x1−x2∣+∣y1−y2∣=x2−x1+∣y1−y2∣|x1-x2|+|y1-y2|=x2-x1+|y1-y2|∣x1−x2∣+∣y1−y2∣=x2−x1+∣y1−y2∣,当y1<y2时，x2−x1+y2−y1=−(x...
2020-04-05 18:57:13
199
原创 Balancing the Scale UVA - 1381
问题https://vjudge.net/problem/UVA-1381分析一共C168C_{16}^8C168种八元组，对于每个组，计算一共有多少种排列方法使得一行平衡。但是枚举时会超时，所以先枚举所有的4元组，然后计算剩下的12个中有多少个的和和4元组相同。#include <iostream>#include <cstdio>#include <...
2020-04-05 12:35:53
117
原创 DNA Regions UVA - 1392 二分法
问题https://vjudge.net/problem/UVA-1392分析先求数组的前缀和，求出满足sum[j]−sum[i]j−1≤p\frac{sum[j]-sum[i]}{j-1}\le pj−1sum[j]−sum[i]≤p的最小i，公式可以变形得到sum[j]−pj<=sum[i]+pisum[j]-pj<=sum[i]+pisum[j]−pj<=sum[i...
2020-04-05 00:07:54
92
原创 Genome Evolution UVA - 1481
问题https://vjudge.net/problem/UVA-1481分析给出两个长度为n的集合，问有多少个相同的连续子集合。参考：https://blog.csdn.net/keshuai19940722/article/details/18882795这题主要是没读懂题目是什么意思。#include <iostream>#include <cstdio>...
2020-04-04 21:39:01
115
原创 Fire-Control System UVA - 1432
问题https://vjudge.net/problem/UVA-1432求包含至少K个点的最小面积的扇区。分析利用极坐标系，计算每个点的角度和半径大小，然后枚举l,r，注意，角度是个环形。这一题一定要先枚举半径，再角度，不能反过来。小技巧：记录半径的平方而不是半径。扇形公式S=α2r2S=\frac{\alpha}{2}r^2S=2αr2,记住要除以2注意K==0的情况#in...
2020-04-04 19:53:56
115
原创 Maximum sum on a torus UVA - 10827
问题https://vjudge.net/problem/UVA-10827分析二维数组最大子矩阵，这题中是带有循环的#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <strin...
2020-04-04 18:41:39
93
原创 Hypertransmission UVA - 1325 暴力枚举
问题https://vjudge.net/problem/UVA-1325分析
2020-04-04 13:00:20
106
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人