- 博客(126)
- 收藏
- 关注
RSS订阅
原创 HDU 6342 Expression in Memories（模拟）多校题解
题意：给你一个规则，问你写的对不对。思路：规则大概概括为：不能出现前导零，符号两边必须是合法数字。我们先把所有问号改好，再去判断现在是否合法，否则问题会变得很比不分开判断复杂。比如0?0判断到第2个0时你还要去看前一个？是什么。下面的讲解问号只改为+或1...对于（null）0？，+0？，*0？一律只能改为+，否则必是前导零，其他情况问号改为1，判断情况的时候注意一下i的范围，比如i=...
2018-08-02 11:04:45
304
原创 POJ 3259 Wormholes（最短路&spfa正权回路）题解
题意：给你m条路花费时间（双向正权路径），w个虫洞返回时间（单向负权路径），问你他能不能走一圈回到原点之后，时间倒流。思路：题意有点难看懂，我们建完边之后找一下是否存在负权回路，存在则能，反之不能。判断负权回路可以用一个cnt，这个spfa板子里有。代码：#include<cstdio>#include<set>#include<vector>...
2018-08-01 21:44:07
197
原创 POJ 1860 Currency Exchange（最短路&spfa正权回路）题解
题意：n种钱，m种汇率转换，若ab汇率p，手续费q，则b=(a-q)*p，你有第s种钱v数量，问你能不能通过转化让你的s种钱变多?思路：因为过程中可能有负权值，用spfa。求是否有正权回路，dis[s]是否增加。把dis初始化为0，然后转化，如果能增大就更新。每次都判断一下dis[s]。参考：最快最好用的——spfa算法代码：#include<cstdio>#inc...
2018-08-01 11:18:50
300
原创 POJ 1797 Heavy Transportation（最短路&Dijkstra变体）题解
题意：给你所有道路的载重，找出从1走到n的所有路径中载重最大的，即路径最小值的最大值。思路：和之前的POJ3268很像。我们用Dijkstra，在每次查找时，我们把最大的先拿出来，因为最大的不影响最小值，然后我们更新的时候，如果当前承重比我们新开辟的路的承重的能力差，那就替换成新的。注意题目所给数据有重边。代码：#include<cstdio>#include<...
2018-07-31 20:14:04
195
原创 POJ 3268 Silver Cow Party（最短路&Dijkstra）题解
题意：有n个地点，有m条路，问从所有点走到指定点x再走回去的最短路中的最长路径思路：用Floyd超时的，这里用的Dijkstra。Dijkstra感觉和Prim和Kruskal的思路很像啊。我们把所有点分为两个集合：S（和源点在同一集合），T（其余点），用dis数组表示每个点到S的最短距离，vis数组记录这个点是否在S中。我们每次找出在T的一个和S距离最短的点，加到S中，这个距离就是他到源...
2018-07-31 19:11:37
203
原创 POJ 2253 Frogger（最短路&Floyd）题解
题意：想给你公青蛙位置，再给你母青蛙位置，然后给你剩余位置，问你怎么走，公青蛙全力跳的的最远距离最小。思路：这里不是求最短路径，而是要你找一条路，青蛙走这条路时，对他跳远要求最低。这个思想还是挺好迁移的，原来我们用mp[i][j]表示i到j最短路径，那么我们现在用它表示i到j最大步伐，然后每次比较，只要最大步伐比他小，那么我们就走新的路。注意最后是mp[1][2]，一直mp[1][n]没改无限...
2018-07-31 15:39:53
189
原创 HDU 2544 最短路（最短路&Floyd）题解
思路：Floyd模板题，注意一下Floyd核心的三个循环，顺序不要变，我们不能把k放在最内层。因为Floyd是通过不断遍历查找是否有更小的两个路径拼起来能比当前小，如果k在最内层，那么我们就会提前算好ij的最小路径，但是此时还有很多其他路径没有合并，无法保证这是最小的。Floyd可以用来做多源最短路问题，复杂度O(n^3)参考：彻底弄懂最短路径问题代码：#include<c...
2018-07-31 11:19:43
184
原创 HDU 6156 Palindrome Function（数位DP）题解
思路：数位dp的操作是dfs+记忆化，我们dp开四维：位置，长度，进制，是否回文。然后每次暴搜记录下每个位置的数字是什么，搜到对称轴另一边需要检查是否符合回文。终于把友谊赛的题目都补完了...没做出来的都是学过的，做出来的都是没学过骚操作过的...学以不致用...代码：#include<cstdio>#include<set>#include<s...
2018-07-31 10:35:31
128
原创 HDU 5934 Bomb（tarjan/SCC缩点）题解
思路：建一个有向图，指向能引爆对象，把强连通分量缩成一点，只要点燃图中入度为0的点即可。因为入度为0没人能引爆，不为0可以由别人引爆。思路很简单，但是早上写的一直错，改了半天了，推倒重来才过了...#include<cstdio>#include<set>#include<stack>#include<cstring>#includ...
2018-07-30 19:00:29
128
原创 POJ 1625 Censored!（AC自动机->指针版+DP+大数）题解
题目：给你n个字母，p个模式串，要你写一个长度为m的串，要求这个串不能包含模式串，问你这样的串最多能写几个思路：dp+AC自动机应该能看出来，万万没想到这题还要加大数...orz状态转移方程dp[i + 1][j->next] += dp[i][j]，其他思路和上一题hdu2457一样的，就是在AC自动机里跑就行了，不要遇到模式串结尾，然后最后把所有结尾求和就是答案。注意下题目说...
2018-07-28 12:03:01
136
原创 HDU 2457 DNA repair（AC自动机+DP）题解
题意：给你几个模式串，问你主串最少改几个字符能够使主串不包含模式串思路：从昨天中午开始研究，研究到现在终于看懂了。既然是多模匹配，我们是要用到AC自动机的。我们把主串放到AC自动机上跑，并保证不出现模式串，这里对AC自动机的创建有所改动，我们需要修改不存在但是符合要求的节点，如果某节点的某一子节点不存在，我们就把这个子节点指向他父辈节点存在的该节点（比如k->next[1]不存在，k-&...
2018-07-28 10:00:53
251
原创 HDU 3065 病毒侵袭持续中（AC自动机）题解
题意：要你找到主串中每个模式串的个数。思路：题目都没说是多组数据，结果没while(~)直接WA了，和上一题差不多，可以用map或者开个数组储存。指针要记得回收内存，不然MLE。#include<cstdio>#include<vector>#include<set>#include<map>#include<queue>...
2018-07-27 10:35:34
199
原创 HDU 2896 病毒侵袭（AC自动机）题解
题意：给你n个模式串，再给你m个主串，问你每个主串中有多少模式串，并输出是哪些。注意一下，这里给的字符范围是可见字符0~127，所以要开130左右。思路：用字典树开的时候储存编号，匹配完成后set记录保证不重复和排序。代码：#include<cstdio>#include<vector>#include<set>#include<que...
2018-07-27 09:34:34
139
原创 HDU 2222 Keywords Search（AC自动机）题解
题意：给你几个keywords，再给你一段文章，问你keywords出现了几次。思路：这里就要用到多模匹配算法AC自动机了，AC自动机需要KMP和字典树的知识，匹配时是在字典树上，失配我们就要用到类似KMP的失配值了，如果失配，我们就沿着失配值到某个节点开始匹配，因为是多模匹配，我们每次失配移动都会从某一keyword的某部分开始匹配，这样就节省了很多时间。话说第一次听到AC自动机我竟天真...
2018-07-26 19:10:50
149
原创 HDU 6315 Naive Operations（线段树+区间维护）多校题解
题意：a数组初始全为0，b数组题目给你，有两种操作：思路：dls的思路很妙啊，我们可以将a初始化为b，加一操作改为减一，然后我们维护一个最小值，一旦最小值为0，说明至少有一个ai > bi，那么找出所有为0的给他的最终结果加上一并且重置为bi，维护一个区间和，询问时线段树求和。一开始updateMin没加判断，单个复杂度飙到nlog(n)，疯狂TLE...代码：#inclu...
2018-07-26 10:24:14
169
原创 POJ 3422 Kaka's Matrix Travels（拆点+最大费用流）题解
题意：小A从左上角走到右下角，每个格子都有一个价值，经过这个格子就把价值拿走，每次只能往下或往右走，问你走k次最多能拿多少价值的东西。思路：这里有一个限制条件就是经过之后要把东西拿走，也就是每一格的价值只能拿一次，这也能用拆点。我们把一个点拆成两个，建两条边，一条流量1费用-cost，另一条流量k-1，费用0，这样就完成了。代码：#include<cstdio>#inc...
2018-07-25 09:56:01
137
原创 LightOJ 1071 Baker Vai（拆点+最大费用流）题解
题意：给一个n*m的方格，每个格子上都有一个数字表示价值，小A在左上角，他从左上角走到右下角只能向右或向下走，然后再从右下角走上左上角，这次只能向上或向左走，这两条路绝对没有重复，问你怎样走有最大价值。思路：因为不能重复，就拆点。拆点是这样的，把一个点拆成一条边，每条边流量为1，表示只能走一次，费用为该点价值的相反数，因为要最大费用，初始和末尾两个点内的流量要设为2因为要走两次。我们把每个点和...
2018-07-24 18:38:24
110
原创 hdu 6299 Balanced Sequence（贪心）题解
题意：题意一开始不是很明白...就是他给你n个串，让你重新排列组合这n个串（每个串内部顺序不变），使得匹配的括号长度最大。注意，题目要求not necessary continuous，括号匹配不需要连续。思路：我们先把每个串里面能组合的全部抵消，比如)((()抵消完为)((。我们能知道，这样操作完只会有4种情况留下：)))))，((((((((，)((((((，))))))))(。然后排序，...
2018-07-24 15:10:47
222
原创 hdu 6301 Distinct Values（贪心）题解
题意：长为n的串，给你m个区间，这些区间内元素不重复，问这样的串字典序最小为？思路：用set保存当前能插入的元素，这样就能直接插入最小元素了。对操作按l排序，因为排过的不用排，所以两个指针L，R是一直右移的。L右移肯定是增加set中元素，R右移有两种可能：一是L在R右边，R只是负责赶路赶到操作区间；二是L在R左边，那么R右移是在扩大区间，并且对数组中元素进行插入。代码：#includ...
2018-07-24 11:59:12
177
原创 UVALive - 2927 "Shortest" pair of paths（最小费用最大流）题解
题意：有n个机器，机器之间有m条连线，我们需要判断机器0到n-1是否存在两条线路，存在输出最小费用。思路：我们把0连接超级源点，n-1连接超级汇点，两者流量都设为2，其他流量设为1，那么只要最后我们能找到超级汇点和超级源点的流量为2就说明有两条路，输出最小值。代码：#include<cstdio>#include<vector>#include<st...
2018-07-24 09:29:07
100
原创 POJ 2195 Going Home（最小费用最大流）题解
题意：给你一张图，有k个人和k个房子，每个房子只能住一个人，每个人到某一房子的花费为曼哈顿距离，问你让k个人怎么走，使他们都住房子且花费最小。思路：我们把所有人和超级源点相连，流量为1花费为0，所有房子和超级汇点相连，流量为1花费为0，然后把所有人和所有房子加边，流量为1，花费为曼哈顿距离，这样这道题目就变成了求超级源点到超级汇点的MCMF。代码：#include<cstdio...
2018-07-23 19:30:07
138
原创 POJ 2886 Who Gets the Most Candies? （线段树）题解
题意：一堆小朋友围成一个圈，规定从k开始玩，每个被选中的人都有一个数字，正数代表从他左边开始数num，负数从右边数，被选中的人继续按照上述操作，直到都退出圈子，第i个退圈的人能拿到一个点数，这个点数是i的因数个数（比如第4个人拿3点）。问：谁点数最多，一样多选第一个。思路：一道好题啊，万万没想到是线段树，想要想到感觉还是有点难度的。这道题其实就是要一直维护剩余人数，但是以前没做过线段树维护剩余...
2018-07-22 20:59:10
209
3
原创 HDU1510 White rectangles（ 乱搞 O(n^3) ）题解
思路：友谊赛的时候一直想到了，但是没想出来怎么遍历才能找到所有矩阵，卡住了。这里讲一下完整思路：我们用一个num[i][j]表示第i行第j列每一列连续的白色格子数量，然后我们定义一个MIN，并且每次都更新MIN的值（因为矩阵高度只和最小的那个有关）。代码：#include<cstdio>#include<vector>#include<stack...
2018-07-21 23:54:00
228
原创 HYSBZ 1036 树的统计Count（树链剖分）题解
思路：树链剖分，不知道说什么...我连模板都不会用代码：#include<map>#include<ctime>#include<cmath>#include<stack>#include<queue>#include<string>#include<vector>#include&am
2018-07-21 16:28:36
125
原创 HDU 5950 Recursive sequence（矩阵快速幂）题解
思路：一开始不会n^4的推导，原来是要找n和n-1的关系，这道题的MOD是long long 的，矩阵具体如下所示最近自己总是很坑啊，代码都瞎吉坝写，一个long long的输入写成%d一直判我TLE，一度怀疑矩阵快速幂地复杂度orz代码：#include<set>#include<cstring>#include<cstdio>#inc...
2018-07-21 00:28:28
129
原创 HDU 4990 Reading comprehension（矩阵快速幂）题解
思路：如图找到推导公式，然后一通乱搞就好了要开long long，否则红橙作伴代码：#include<set>#include<cstring>#include<cstdio>#include<algorithm>#define ll long longconst int maxn = 3;const int MOD...
2018-07-20 16:22:26
137
原创 CodeForces 450B Jzzhu and Sequences（矩阵快速幂）题解
思路：之前那篇完全没想清楚，给删了，下午一上班突然想明白了。讲一下这道题的大概思路，应该就明白矩阵快速幂是怎么回事了。我们首先可以推导出学过矩阵的都应该看得懂，我们把它简写成T*A(n-1)=A(n)，是不是有点像等比？然后我们得到T^(n-1)*A(1)=A(n)，所以我们可以通过矩阵快速幂快速计算左边的T^n-1这个式子，最后再和A1相乘，那么第一个数字就是答案了。代码...
2018-07-20 14:44:50
162
原创 HDU - 3068 最长回文（马拉车Manacher）题解
思路：马拉车裸题，我们用一个p[i]数组代表以i为中心的最大回文半径。这里用了一个小技巧，如果一个串是aaaa这样的，那我们插入不相干的字符使它成为#a#a#a#a#，这样无论这个串是奇数还是偶数都会变成奇数，容易处理。马拉车的效率在于，在暴力处理前面的回文时，我们可以初始化后面的p[j]，减少暴力的时间，这样复杂度就从O（n^2）变成了O（n）。这里要注意一下，我们得到的p[i]所指向的不一定是...
2018-07-18 19:58:57
245
原创 FZU 1901 Period II（KMP中的next）题解
题意：给你一串字符串，问你前后缀相同情况有几种，并输出后缀位置（？这里一直没看懂length是什么，但是这样理解答案也对，然后还要加上本身长度）思路：这里好好讲讲next的用法。我们都知道next代表前后缀匹配值，现在我们以下面这个字符串为例，讲述next的用法：len = 9,next[len] = 4，所我们找到了第一个前后缀匹配串abab，next[ next[len] ] = ...
2018-07-18 17:47:05
164
原创 HDU 3374 String Problem（最大最小表示+KMP）题解
题意：给你一个字符串，这个字符串可以这样操作：把第一个字符放到最后一个形成一个新的字符串，记原式Rank为1，每操作一步Rank+1，问你这样操作得出的最小字典序的字符串的Rank和这样的字符串有几个，最大字典序的字符串的Rank和这样的字符串有几个。思路：手动模拟操作复杂度O（n^2）果断超时，引入一种专门计算此情况的方法，复杂度O（n）。这里只说最小表示：我们先拿两个指针i，j，分...
2018-07-18 15:36:27
155
原创 HDU 4300 Clairewd’s message（扩展KMP）题解
题意：先给你一个密码本，再给你一串字符串，字符串前面是密文，后面是明文（明文可能不完成整），也就是说这个字符串由一个完整的密文和可能不完整的该密文的明文组成，要你找出最短的密文+明文。思路：我们把字符串当做全是密文然后解密成明文，这样前面密文部分就是完整的明文，后面明文部分就乱码了，要求最短密文+明文就是求最短的密文，就是求原串和解密后的串的最大公共前缀，所以用EXMP求解。坑爹了，前面没...
2018-07-18 10:56:55
174
原创 POJ 2923 Relocation（状压DP+01背包）题解
题意：给你汽车容积c1,c2，再给你n个包裹的体积，问你最少运几次能全运走思路：用2进制表示每次运送时某物在不在此次运送之中，1在0不在。我们把运送次数抽象成物品价值，把状态抽象成体积，用一个dp[ i ] 记录完成状态i的最少步数那么就转化为了01背包问题，得到状态转移方程dp[ j|state ] = min( dp[ j|state ],dp[j] + 1 )，state为运送时物品的状...
2018-07-17 15:27:13
111
原创 HDU 4272 LianLianKan （状压DP+DFS）题解
思路：用状压DP+DFS遍历查找是否可行。假设一个数为x，那么他最远可以消去的点为x+9，因为x+1~x+4都能被他前面的点消去，所以我们将2进制的范围设为2^10，用0表示已经消去，1表示没有消去。dp[i][j]表示栈顶是i当前状态为j时能不能消去栈顶，-1代表不知道，0不行，1行。所以我们只需DFS到i==n时j是否为0，就可以知道能不能消除。更新状态时，只有栈顶到栈底元素>10才...
2018-07-17 09:54:14
163
原创 POJ 1185 炮兵阵地（状压DP）题解
思路：和上一篇思路一样，但是这里要求最大能排几个，这里要开三维，记录上次和上上次的状态，再一一判定，状态转移方程为 dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][t] + num[j])代码：#include<cstdio>#include<map>#include<set>#include<queu...
2018-07-16 19:27:34
208
原创 POJ - 3254 Corn Fields（状压DP）题解
思路：参照blog，用状压DP做，和题解稍微有点不一样，我这里直接储存了状态而不是索引。这一题的问题是怎么判断相邻不能种，我们用2进制来表示每一行的种植情况。我们将每一行所能够造的所有可能都打表（即认为每一块都能种），然后将每一行不能种的地方用2进制保存下来，两者&运算聚能知道是否有重合，重合即此方法排除；上下两行同理；判断左右两块则是左移后&运算。状态DP做的时候想着...
2018-07-16 16:48:33
153
原创 HDU 1438 钥匙计数之一（状压DP）题解
思路：每个槽有4种深度，一共有2^4种状态。然后开4维来保存每一次的状态：dp[ 第几个槽 ][ 当前状态 ][ 末尾深度 ][ 是否符合要求 ]。代码：#include<cstdio>#include<map>#include<set>#include<queue>#include<cstring>#include<st...
2018-07-16 11:59:59
160
原创 SPOJ BALNUM Balanced Numbers（数位DP+状态压缩）题解
思路：把0~9的状态用3进制表示，数据量3^10代码：#include<cstdio>#include<map>#include<set>#include<queue>#include<cstring>#include<string>#include<cmath>#include<cst
2018-07-16 09:52:57
119
原创 CodeForces - 55D Beautiful numbers（数位DP+Hash）题解
题意：美丽数定义：一个正数能被所有位数整除。求给出一个范围，回答这个范围内的美丽数。思路：一个数能被所有位数整除，换句话说就是一个数能整除所有位数的LCM，所以问题就转化为一个数能否被所有位数的LCM整除。按照一般的思想，直接开三维dp[pos][num][lcm]。但是num范围很大，直接开就爆了，怎么办呢？我们可以把num%2520（即1~9的LCM）储存为mod，因为所有位数最大的LCM就是...
2018-07-14 22:49:14
91
原创 HDU 3709 Balanced Number（数位DP）题解
思路：之前想直接开左右两边的数结果爆内存...枚举每次pivot的位置，然后数位DP，如果sum<0返回0，因为已经小于零说明已经到了pivot右边，继续dfs只会越来越小，且dp数组会炸注意一下一些细节：dp开long long，注意前导零只能算一次代码：#include<iostream>#include<algorithm>#define ll long l...
2018-07-14 16:27:37
133
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人