- 博客(54)
- 收藏
- 关注
RSS订阅原创 HDU-3045 Picnic Cows 【DP+斜率优化】
题目链接题意有N只奶牛，每只奶牛有一个满意度，如果把一些奶牛分到一个组内，那么这些奶牛的满意度都会下降到组中满意度的最小值。现在规定每个组至少T只奶牛，求总的满意度变化的最小值分析从这个题中我学到了斜率DP中规定了转移距离的最小值时的处理方法（也就是i必须从小于等于i-T的状态转移而来） 状态不难想出，先对奶牛的满意度排个序，设dp[i]为前i只奶牛分好组后的满意度下降最小值，显然有： dp[i
2017-03-11 16:31:12
389
原创 HDU-3480 Division 【DP+斜率优化（二维）】
题目链接题意定义一个集合的花费是这个集合中的最大值减最小值的平方。然后给定一个集合S，求对这个集合的一个覆盖，使得所有子集的花费和最小。分析本身这个题是非常简单的，只是今天看了别人的题解，我发现我以前写的二维斜率优化都写复杂了。直接外层循环用未被优化的那一维就行了，不用像我以前那样维护一个k维的单调队列……我说怎么不对劲，每次看别人的代码都那么短…… 具体见代码AC代码//HDU-3480 Div
2017-03-11 15:26:24
418
原创 POJ-1180 Batch Scheduling 【逆向DP+斜率优化】
题目链接题意一台机器有N个物品要处理，每个物品的处理时间是Ti，花费系数是Fi，可以把这N个物品分包处理，打包需要花费时间S，机器每处理完一包物品就会把当前时间显示出来（刚开始处理时时间为0），那么这包中每个物品的花费就是显示的这个时间乘以其花费系数。求处理完所有物品的最小花费。分析朴素的想法设状态为处理前i个物品的最小花费，但是单考虑前i个物品的花费是有后效性的，因为每新增一个包它的开始时间是由前
2017-03-05 15:21:20
433
原创 HDU-2829 Lawrence 【斜率优化DP】【四边形不等式优化】
题目链接题意背景故事大概是说一战时一个英国间谍Lawrence要指挥突击队去炸毁奥斯曼帝国的一些铁轨。铁轨上有n个火车站，按线性排列，每个火车站上有一个权值，最后整个铁路的价值就是每一段联通铁路段上的火车站权值两两相乘的和加起来（联通段上只有一个车站就是0）。Lawrence有m次炸毁两个车站之间铁路的机会，求Lawrence最终可以使得这段铁路价值变成的最小值。分析转移方程易想出，设状态dp[i]
2017-02-26 15:31:41
757
原创 POJ-1260 Pearls 【DP】
题目链接题意某公司需采购c种珍珠，知道每种珍珠的价格和需要的量。购买时，若要买某种珍珠，需额外支付10个该种珍珠的价钱。同时价格低的珍珠可以用价格高的珍珠代替。求最少能花多少钱完成采购。分析解决本题关键要想到这一点：若第i种珍珠可以被第j种珍珠代替（i< j且珍珠价格递增），则第i~j-1种珍珠都应当被第j种珍珠代替。证明很简单，这里省略。所以最终的采购的方式就是将整个珍珠种类的区间进行划分，每个划
2017-02-25 15:25:44
244
原创 CodeForces 449D Jzzhu and Numbers 【DP+容斥】
题意给定一个n元集，元素为aia_i，求其有多少个子集，使得其中的元素ai1,.....aika_{i1},.....a_{ik}满足 ai1&ai2&⋯&aik=0 a_{i1}\& a_{i2}\& \cdots \& a_{ik} = 0 (1⩽n,a⩽106) (1 \leqslant n,a \leqslant 10^6)分析要是n和a的范围小一些自然可以直接用01背包做，然而这里a与
2017-01-19 15:06:50
982
原创 CodeForces-450E Jzzhu and Apples 【数学+贪心构造】
题意将1到n的数分成不互质的数对，问最多能分出多少对？分析贪心构造，先打出小于等于n的所有素因子，从最大的素因子开始（因为越大的因子，在数列中的倍数越少），两两匹配其倍数。若刚好是奇数个，则将其2倍留下，因为若能匹配出至少一对，其二倍必在数列中，同时，其二倍除了其本身以外必然只有2这个因子，最后组合2的倍数时，必然可以将其考虑进去。AC代码//CodeForces 450E//AC 2017-1-
2017-01-19 10:41:22
451
原创 HDU 5800 To My Girlfriend 【DP】
题意有n个物品，每个物品的重量是aia_i，求以下式子： ∑ni=i∑nj=1∑nk=1∑nl=1∑sm=1f(i,j,k,l,m)(i≠j≠k≠l)\sum^n_{i=i} \sum^n_{j=1} \sum^n_{k=1} \sum^n_{l=1} \sum^s_{m=1} f(i,j,k,l,m) (i \neq j \neq k \neq l) 其中f(i,jk,l,m)f(i,jk,l
2017-01-19 10:04:17
560
原创 HDU 5726 GCD 【GCD】【ST表+二分】【线段树+暴力枚举】
题意给一串数列，求区间GCD和整个数列中与该区间GCD相等的区间数分析首先区间GCD易求，用能求RMQ的方法都可以，比如ST表、线段树。关键是如何求第二个问题，这里有两种做法： 方法一 利用GCD的性质，若固定区间左端点，增大右端点，区间GCD必然非递增。因此我们可以遍历区间左端点，用二分求出以该端点起始的区间的所有gcd的情况及其对应的区间个数，并用map记录。该过程复杂度可近似看做O(nlo
2017-01-17 19:35:18
359
原创 HDU 3401 Trade 【DP+单调队列优化】
题意给出接下来T天每天卖出、买入股票的价格，每天买入、卖出的上限，持有的股票的总上限，并且两次股票操作之间有时间间隔，求T天之后最多能赚多少钱。分析很容易可以写出状态转移方程： dp[i][j]↔第i天持有j的股票能获得的最大利益dp[i][j] \leftrightarrow第i天持有j的股票能获得的最大利益 dp[i][j]=max(dp[i−1][j],max(dp[pre][j+k]+B
2017-01-16 23:32:23
402
原创 POJ 3017 Cut the Sequence 【DP+单调队列优化+平衡树】
题意给定一串数列，要求把它划分成一些小段，每个小段的和不超过M，找到一种分段方法使得每一段的最大值的和最小，求这个最小值分析易得转移方程 dp[i]=min(dp[k]+max(num[k+1],⋯,num[i])) dp[i]=min(dp[k]+max(num[k+1], \cdots, num[i])) 其中∑ij=k+1num[j]<=M\sum^i_{j=k+1} num[j]<=M
2017-01-16 10:14:38
487
原创 CodeForces 342D Xenia and Dominoes 【DP+容斥】
题目链接题意在一个3*n的桌子上放一些1*2的多米诺骨牌（横竖放都可以），桌子上有一些不能放置的格子，除了这些不能放置的格子以外，还要求一个指定的格子不能被多米诺骨牌覆盖，同时这个空位可以通过移动附近的骨牌来转移到其他地方，剩下的格子要被全部覆盖，求放置的种数。分析先不管哪个预留的空位，对于一个已知的棋盘，一列一列转移状态。设状态： dp[i][maks]↔在第i列mask中的行被覆盖，并且前i−
2016-11-27 16:46:08
579
原创 HDU 4348 To the moon 【主席树+区间修改】
persistent segment tree 题目链接题意给一串初始序列An，并且初始的时间是0，定义以下操作： 1. 给一个区间内的数加上一个值，并且时间加一 2. 查询当前某区间的区间和 3. 查询过去某个时间的某个区间和 4. 回到某个时间序列大小和查询数量级为1e5分析SPOJ上也有这个题，但HDU卡内存严格一些，所以有些方法就不能过了。 首先既然有历史版本，那么就用主席树吧
2016-11-16 00:25:27
893
原创 SPOJ 3267(DQUERY) D-query 【主席树】【离线树状数组】
题目链接 persistent segment tree题意给一串数列，有q个（1e5的数量级）询问，求i到j间的不同数字的个数分析这个题有几种做法，可以用主席树、离线树状数组，还可以直接用莫队。这里写一下主席树和离线树状数组的做法主席树做法一道主席树的入门题，会了过后看很好做，但初学时还是搞了很久。建主席数的时候用一个map存当前这个数之前最近出现的地方，然后主席数中的每一棵树存的还是某个位置有
2016-10-26 19:44:56
458
原创 POJ 3225 Help with Intervals 【线段树】
题目链接 segment tree题意给定集合S，S最初是空集。现对其进行一些操作：与一个集合求交、并、补、对称差。用区间表示出最终的S分析这个题有许多注意的地方（当然可能是我写法不太好），肝了一上午…… 那么首先想到用线段树来解决这个区间覆盖的问题。虽然是实数区间，但注意到区间端点始终是整数。于是我们整体乘2，用偶数来代表整数点，用奇数来代表两整数之间的开区间。比如2就对应[1,1]，3就对应
2016-10-26 12:00:30
348
原创 HDU 4288 Coder 【线段树】
题目链接segment tree, single-point update题意维护一个集合，这个集合可进行以下操作： + 向其中添加一个数（保证之前没有这个数） + 向其中删除一个数（保证集合中有这个数） + 求所有下标%5==3的数的和（从小到大排列） 完成给定的操作，返回sum的值分析求区间和问题，尝试使用线段树。然而是求的有步长的和，怎么处理？首先，每个区间中记录下标模5相同的数的和（
2016-10-20 21:04:28
400
原创 HDU 1542 Atlantis 【线段树+扫描线】
题目链接 segment tree, scanning line题意矩形面积的并分析最基础的扫描线求矩形面积并的题，离散化后用线段树，这个思想很简单，不再赘述。记录在这里主要是这个线段树的写法，适用于区间反复覆盖，RE了很多次，记在这里方便以后查看。AC代码//HDU 1542 Atlantis//AC 2016-10-19 22:33:31//Segment tree, scan line
2016-10-19 22:41:37
480
原创 Codeforces 732D Exams【二分+贪心】
题目链接 binary search, greedy题意在接下来的n天要通过m门课程，给出每门课程需要复习的天数，然后给出每天能够参加哪门考试（0代表没有考试），每天可以选择复习任意一门课程，或者参加考试（前提是已经复习了应有的天数，可以不连续）或者什么都不做，求最短通过所有课程的时间分析当时做这题时贪心都想出来了，居然没想到用二分…… 贪心的思路： 对于一个固定的天数，要判断能不能在期间通过
2016-10-19 20:00:17
968
原创 HDU 2795 Billboard 【线段树】
题目链接 Segment Tree, single-point update题意有一块h*w的告示板，要向上面贴一些广告，每张广告都想被贴得尽量靠顶端，然后再尽量靠左。现有n块尺寸分别是1*wi的广告（高度都为1）依次贴上去，问没张广告贴得位置。分析首先实际贴得行数肯定是min(h,n)，开始没注意这个，被数据范围吓到了。然后这个问题只要记录每一行还剩下多少宽度，然后每贴一个广告就查找尽量靠左并且
2016-10-16 15:25:14
414
原创 2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest Problem J 【二分+DP+单调队列】
题目链接题意有n个地铁站，全部成线性排列，有n-1种地铁票，第i种地铁票的价格为p_i，并且能坐i站（也就是在第k个站能够到达[k-i,k+i]中的站）。现在想从起点站坐到终点站，地铁在相邻两个站之间运行花费1s（这里原文是“get from a stop to the next one in just one minute.”有歧义，坑了好久），给出在每个站出来又进去花费的时间，并且从一个站出来又
2016-09-11 15:04:47
979
原创 HDU 5521 Meeting 【拆点+最短路】
题意给m个由图中结点组成的点集，点集中的点两两连通且距离为相等的ti。现有两人分别从1和N点处同时出发吗，问能否相遇以及相遇的最短时间。分析很容易想到直接分别以点1和点N为起始点求最短路，再遍历各个点即可求得最短相遇时间。然而建图上却有问题：这个题中的边是以点集的形式给出，极端情况下可能会出现有1E12条边的稠密图。 这时就要利用点集中的点之间距离相等这个性质，拆点来建图。将点集抽象成一个点，将点
2016-08-13 10:03:24
491
原创 POJ 3255 Roadblocks 【次短路】
题意给N个节点，R条双向边求从结点1到N的次短路径分析通过这个题学习了一下次短路的求法。求K短路可以用A*+Dijkstra，有机会再学一发。 求次短路可以改进一下求最短路的Dijkstra，对每个结点不仅记录最短距离，同时也记录其严格的次短距离（不能等于最短路），同时再把松弛的条件改为满足次短的情况。具体来说，首先入队的条件有两个：小于最短距离，大于最短距离且小于次短距离。 if(dist[a
2016-08-13 09:23:57
336
原创 LightOJ 1013 Love Calculator 【DP（LCS变形）】
题目链接题意给两个字符串，求长度最短的字符串的长度以及个数，使得给出的两个串都是这个串的子串。分析LCS的变形，首先长度自然是len(s1)+len(s2)-len(LCS)。关键是有多少个这样的字符串。现在知道有两种DP的方法。方法一（三维DP）设状态： dp[i][j][k]↔由s1的前j个字符和s2的前k个字符组成的长度为i的目标串的个数dp[i][j][k] \leftrightarrow
2016-08-09 16:51:22
432
1
原创 LightOJ 1017 Brush (III) 【DP】
题目链接题意墙上有N个污点，知道它们的坐标（xi,yi）。现有一把宽度为w的刷子，将刷子固定在一个高度就可以沿着平行于x轴的方向刷除污点。总操作次数最多为k，求最多能够刷除掉多少污渍分析我们以刷子底部的y坐标来刻画刷子的位置。首先既然刷子会沿着平行x轴的方向刷出这个高度所有的污点，那么可以不管污点的x坐标。 先预处理一下，把污点高度从大到小排个序（因为我们是以刷子的下部作为刷子的位置，那么刷高处的
2016-08-09 15:31:15
650
原创 POJ 3666 Making the Grade 【DP+离散化】
题目链接题意有N个平台，它们的高度分别为Ai。先想把这些平台的高度变得非严格单调，改变一个平台的高度的花费就是高度的改变量，问最小的花费是多少。分析定义状态： dp[i][j]↔前i个平台高度变成单调递增并且第i个平台高度为j所需的最少花费dp[i][j] \leftrightarrow 前i个平台高度变成单调递增并且第i个平台高度为j所需的最少花费 所以状态转移：dp[i][j]=max(dp[
2016-08-09 14:59:42
302
原创 POJ 1065 Wooden Sticks 【贪心】
题目链接题意给n个整数对，定义数对间的大于关系是(w1,l1)≤(w2,l2)↔w1≤w2andl1≤l2(w1,l1) \leq (w2,l2) \leftrightarrow w1\leq w2 \,and\, l1\leq l2，求用这些数对最少能组成几组非递减序列分析LIS的变形，但考虑到原来给的这些数对并没有顺序，可以随便选择，因此没有必要用DP求LIS。可以倒序排序（先按第一个数排序，再
2016-08-09 14:41:44
264
原创 HDU 1058 Humble Numbers 【DP】
题目链接题意定义“Humble Numbers”是素因子只含有2,3,5,7的数，求第n个Humble Number是多少。分析显然直接求出某个范围以内所有的humble Numbers，关键是如何枚举才能保证枚举出来的数是递增的。 这里用DP来实现，记录当前没有乘以某个因子中的最大数再乘以这个因子得到的数中的最小值，这样说很抽象，看代码： while(m<=5842) {
2016-08-09 14:21:11
268
原创 LightOJ 1021 Painful Bases 【状压DP+数位DP】
题目链接题意求由一些B进制的数的全排列中能被K整除的数的个数分析题中B最高达到16，直接枚举排列显然不可能。考虑数位DP，但同时取得每个数要不同，所以需要记录用过哪些数，因此要用到状压DP状态dp[S][r]↔用了数集{S}中的数后除以K余数为r的数的个数 dp[S][r] \leftrightarrow 用了数集\{S\}中的数后除以K余数为r的数的个数转移方程dp[S][r]=∑a∈{S}dp[
2016-08-04 18:21:43
394
原创 POJ 3280 Cheapest Palindrome 【区间DP】
题目链接题意给你一串字符串，并给出添加以及删除（在任意位置）每种字符的花费，问把这个字符串变成回文串所需的最少花费分析经典的区间DP状态设 dp[i][j]⇔将子串S（i,j−1）变成回文串的最小花费dp[i][j]\Leftrightarrow 将子串S（i,j-1）变成回文串的最小花费习惯设成前闭后开区间状态转移方程如果当前子串最前面和最后面的字符本来就相同，当前的最小花费就等于里面的子串的最
2016-08-02 21:37:35
321
原创 Aizu 0513 Paint Color【离散化+BFS】
题目链接 （日语题……(:зゝ∠)）题意在直角坐标系的第一象限中有一块m*h的板子，在上面贴上了一些矩形的胶带，现在告诉每个胶带的左下坐标和右上坐标，求板子上有多少个不连通的空白区域（没有贴胶带）分析坐标范围太大，1e6左右，直接按坐标来BFS显然不可能。但考虑到胶带数量只要1e3，可以根据胶带的位置对坐标离散化处理。离散化方法x和y分开处理（因为互不影响）。把所有的x1，x2以及它们相邻的坐标（即
2016-08-02 17:09:48
388
原创 POJ 2566 Bound Found 【Two Pointers】
题目链接题意给一串数列，再给一个目标值（非负），求这个数列中最接近目标值的区间和的绝对值分析原数列中的数有正有负，用Two Pointers不能保证向左向右移动一定会使区间和变大或变小，而排序又会打乱数列的顺序。同样，如果先算出前缀和，在前缀和上移动同样不能保证向着期望的方向变化。但是，对前缀和排序不影响结果，只要记录某个前缀和对应的原下标，排序后再用Two Pointers，就可以解决这个问题AC
2016-08-01 14:56:00
225
原创 POJ 3679 Median 【二分】
题目链接题意给N（N小于等于1e6）个数，求出由它们每个数的差组成的数列的中位数（若有偶数个，取左边的一个）分析1e6的数据量，直接算是O(n2)O(n^2)的数据量，肯定T。考虑用二分来枚举中位数。然后二分中的判断有不同的方法：O(nlog2n)O(nlog^2n)做法： 用两次二分。先把原来的所有数排序，排序之后，选定一个数，其后面的数与其的差就是递增的了。于是用枚举的中位数，从头到尾遍历，
2016-08-01 11:35:59
279
原创 UVA 1616 Caravan Robbers 【二分+贪心+枚举分母】
题目链接题意给n个互不相包含的区间，求出一个长度的最大值，使得可以在每个区间中选出这样一个长度的子区间，这些子区间互不相交。结果用分数表示分析先考虑如果给定了区间长度能不能选出这样的区间。因为题中说了区间互不包含，所以可以直接把所有区间先按左端点排序再按右端点排序，每个区间都尽量取靠近左端点的子区间。（如果没有说区间不相互包含的话，就要维护优先队列） 然后用二分可以求出这个最大长度。这个题卡精度，
2016-08-01 09:32:53
396
原创 UVA 1601 POJ 3523 The Morning after Halloween 【双向BFS】【A*】 （好题）
题目链接题意问移动图上三个Ghost同时到达目标点的最短步数。三个Ghost可以同时移动，但不能重叠，不能交换位置。双向BFS做法因为状态比较多，直接BFS会T，因此用双向BFS来优化。然而直接上双向BFS还是会T，在BFS过程中枚举可以走的循环太多了，因此对图进行预处理，取出所有可以走的点进行BFS。16*16不是太多，所以没有必要hash，直接开个六维数组还方便些。其他就是一些双向BFS常规注意
2016-07-29 23:26:16
420
原创 UVA 10570 Meeting with Aliens 【枚举+结论题】
题目链接题意给一串环形序列（首尾相连），可以进行交换任意两个数的操作。问最少进行多少步这样的操作能够使得整个序列的顺序正常（即从序列中的1开始，顺时针或逆时针相邻递增）分析首先这个题有一个简单的结论，如果要通过两两交换使得一种排列变为另一种排列，最少的方式是从最左边开始扫描一遍，若当前这个数跟目标排列不一样，就把它从后面交换过来。 那么这个题就很简单了，枚举这串序列顺序正确的所有情况（比如：123
2016-07-29 23:23:01
288
原创 UVA 1614 Hell on the Markets 【贪心+结论题】
题目链接题意给一串序列，保证序列中每个数满足ai≤ia_i \leq i ，问能否给这些数每个数前面填上正负号，使得其和为0.分析先上结论 数列an{a_n}满足 ∀ai∈an,ai≤i\forall a_i \in {a_n}, a_i \leq i ，则对于任何正整数S≤sum[i] S \leq sum[i] （sum[i]为前i项和），总能从an{a_n}中的前i项中选出某些数，使其
2016-07-29 23:13:03
368
原创 UVA 10603 Fill【BFS】
题意有三个给定容量的没有刻度的杯子，其中一个杯子装满水，问量出给定水的体积需要倒多少水（倒水时水量的和）分析直接BFS，但非常容易写错AC代码//UVA 10603 Fill//AC 2016-07-19 16:11:16//BFS#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#inclu
2016-07-26 19:32:48
335
原创 Codevs 1288 埃及分数 【IDA*】
题目链接题意非常出名而基础的一道题，也是lrj紫书上讲解IDA*的例题。 今天发现了Codevs这个OJ的存在，给人耳目一新的感觉，然后就A了这个题。然而居然做的第一题的测试数据就有问题（有争议）……分析首先看这个搜索的决策，既无法确定搜索深度的下界（可以有无限个分数相加），也无法确定宽度的下界（分数可以无限小），因此考虑使用IDA* 题中最优解首先是长度最短，这就给了IDA*用武之处，不断地求
2016-07-25 22:13:34
340
原创 UVA 11212 Editing a Book 【IDA*】
题目链接题意给一个n个数的全排列，可以进行将任意连续的一段截下来插入到任意位置的操作，问至少需要多少步这样的操作能够是序列变成递增的序列。分析题中n的最大值为9，状态数为9的阶乘，不过1e6左右，看似可以直接BFS。但是每一种状态后的决策数量太多了（任意位置的任意长度再插入到任意位置） 考虑到n个数的全排列，要使之恢复递增的顺序，最多移动n-1次即可。这样层数有上限，尝试用DFS。然而直接DFS回
2016-07-25 21:49:54
639
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人