EMber _-CSDN博客

原创多重背包的优化二进制/单调队列解析

由于做题的时候老被这玩意儿卡住的我很不爽，决定写个blog来加深自己的印象以及不用到处找资料回忆。多重背包的问题的具体描述如下：给出一个体积为v的背包，有n个物品，每个物品可以选c[i]次，问最多能得到多大的代价。直接做DP的复杂度是n*v*max(c[i])，这显然无法承受正常难度的数据范围。然后我们考虑优化。首先来看稍微简单一点的二进制优化。很久以前打的就不要纠结是不是c

2017-10-25 22:32:23 628

原创优先队列重载运算符详解

由于不是很懂priority_queue的细致操作，以及不再感受被greater和重载运算符统治的恐惧，所以我觉得有必要搞这么个东西。。。首先头文件#include 然后priority_queue q,定义优先队列q。其实我们都知道，虽然这玩意儿叫做优先队列，我们都不把它看成队列，一般都是用于处理堆有关操作。。所以优先队列操作有插入，删除，查询，查找操作用来搜

2017-10-17 18:04:19 3387 5

原创一维二维树状数组区间加与区间求和

在一般的情况下，对于区间加与区间求和，我们一般使用线段树。树状数组在一般情况下，只能够单点查询，修改。但是我们可以通过差分做到区间加或者区间求和（一维）我们对于一个区间l,r，要求他们的和a[l]….a[r]。设b[i]表示相邻两点之间的差(b[i]=a[i]-a[i-1])，那么对于sum(a[l]..a[r]) 明显有sum(a[l]..a[r])=(b[1]+b[2]+….+

2017-08-15 20:44:50 1321

转载二分图大讲堂——彻底搞定最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配

文本内容框架： §1图论点、边集和二分图的相关概念和性质 §2二分图最大匹配求解匈牙利算法、Hopcroft-Karp算法 §3二分图最小覆盖集和最大独立集的构造 §4二分图最小路径覆盖求解 §5二分图带权最优匹配求解 Kuhn-Munkers算法 §6小结每章节都详细地讲解了问题介绍，算法原理和分

2017-07-31 15:50:23 909

原创易犯的错误&各种技巧（实时更新）

在要运用取模操作的题目，取模操作要打少一点，mod的好慢啊！有把握的题不要先打对拍，否则可能时间不够。博弈最好还是用dfs来求解。 long long取模的还是用黑科技1。表面上不会爆long long，如果带有符号运算的，就要考虑一下。注意long long爆空间。二分的时候要注意，如果是负数的二分那么mid=(l+r+1)/2，然后还要注意到底是该l=mid+1

2016-08-19 19:31:10 299

复健中…题目重点在求出现的次数，这个可以用SA,SAM求，讨论区有SA的解法。相对而言kmp较为简便，只要理解kmp中next数组的定义，就能轻松解决，倒着操作累计叠加即可。需要注意的是边界问题，由于未被赋值的next数组默认为0，所以如果计数的数组从0开始就会累加过多，所以将1作为初始位置,也因此做kmp的时候记得往后多做一位。不过就算位置错了也只有三个点不过。。#include<cstdio>#include<cstring>#include<algorithm

2020-09-02 14:55:36 209

原创 bzoj3341: [Ceoi2013]adriatic 记忆化搜索

题意：给你一个矩阵，上面有一些点，两个点之间能直接互相到达保证两个点的坐标一定严格遵从相同的大小性（ax<bx,ay<by)||(ax>bx,ay>by)（ax<bx,ay<by)||(ax>bx,ay>by)，输出每一个点到所有店的最短路径之和。n<=250000. 矩阵长宽<=2500. 一开始还以为是什么奇怪的扫描线之类的，或者cdq。。想了想不大可能啊，性质不是很符合，然后不大会了。。考场

2017-12-19 16:33:33 481

原创 Atcoder Regular contest 085F NRE 线段树+DP

题意：给你两个序列，a全部为0，b给出，给出一些区间，可以把a上的这些区间变为全1，要求操作以后两个序列对应位置不相同的个数最小，n<=2e5. 说实话这种区间操作很容易想到线段树，但是我没想到DP，水了水了。。主要还是题目的模型没化出来吧，直接做其实是不可做的。。把(ai,bi)看成是一个数对，那么答案其实就是(1,0)和(0,1)的数量，也就相当于(0,1)+(0/1,0)-(0,0)

2017-12-07 17:11:44 382

原创 bzoj3580 冒泡排序模拟

题意：模拟一个序列的冒泡排序，交换k次以后的序列,n<=1e6,交换次数<=10^12。感觉这题虽然是模拟，但是并不简单。。可能是我水了。就按照题目给出的代码来模拟。首先二分出外层的循环次数，然后剩下的就是内层的了，内层的由于次数<=1e6所以直接模拟即可，细节看代码吧。很久没打题啥都不会了，只能看题解。。#include<cstdio>#include<algorithm>#inc

2017-12-05 18:04:54 529

原创 NOIP2017提高组 Day2T2宝藏状压DP

题目就不说了吧。。搜索好像也能过，不过是启发式才行。。何况比赛打得也是状压。。其实不算很难吧，但是我比较菜所以挂了。总是想着如何枚举，但是这题直接枚举转移的话好像不大可做。所以预处理出两个状态之间的转移代价，即w[s1,s2]表示从s1转移到s2的代价，保证s1&s2==0，即s1与s2不相交。然后直接转移就好了，复杂度是3^n*n^2，但是用枚举子集转移的方法可以去除冗余状态，

2017-11-21 15:26:59 1381 1

原创 bzoj3706反色刷欧拉图+并查集（欧拉图性质简介）

题意：一个无向图，每条边有黑白两种颜色，要求用最少的反色刷使得所有边变为白色，注意刷子会回到出发点。明显欧拉回路，注意到欧拉回路的性质，即无向图任意点的点数不能使奇数。那么我们用并查集维护每个连通块内黑色边的数量以及他们的度数，用桶存起来。一个基本的维护。#include<cstdio>#include<algorithm>#include<cstring>#define fo(i,a,b

2017-11-10 15:17:40 463

原创 bzoj1833[ZJOI2010]count 数字计数数位DP

题意：求l,r中0-9各个数字的出现次数。好像是数位DP经典题。。设f[i][j][k]表示做到第i位，当前计算数字j，前i-1位已经出现的次数为k的总出现次数。直接记忆化搜索即可，注意一下前导0.#include<cstdio>#include<cstring>#include<algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#defi

2017-11-10 12:33:30 333

原创 51nod1232 完美数数位DP

如果一个数能够被组成它的各个非0数字整除，则称它是完美数。例如：1-9都是完美数，10,11,12,101都是完美数，但是13就不是完美数（因为13不能被数字3整除）。现在给定正整数x,y，求x和y之间（包含x和y的闭区间）共有多少完美数。一个数能整除他的所有位上的数，也就是说要整除所有位置上的数字的lcm。那么设f[i][j][k]表示做到第i位，模2520意义下数字为j，lcm为第k个的

2017-11-10 10:21:18 618

原创 Atcoder Regular Contest 084

题意:给出一个数k，求k的倍数中的一个数，使得这个数的数位和最小。k<=1e5. 感觉做这题智商被碾压了，完全想不到spfa的做法，比赛的时候打数位dp打到倦生都过不去。。先讲spfa做法：从1开始，向x+1连边，代价为数位差，也就是1，或者向x*10，代价为0，注意是在%k意义下，那么答案就是dis[0]+1,即到达k的倍数中最小的路径。#include<cstdio>#include<c

2017-11-07 22:00:38 251

原创 bzoj3192 [JLOI2013]删除物品树状数组

题意：箱子再分配问题需要解决如下问题：（1）一共有N个物品，堆成M堆。（2）所有物品都是一样的，但是它们有不同的优先级。（3）你只能够移动某堆中位于顶端的物品。（4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。（6）只是一个比较难解

2017-11-07 20:45:54 214

原创 bzoj2109 [Noi2010]Plane 航空管制贪心拓补排序

题意：定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。起飞序列还存在两类限制条件：  第一类（最晚起飞时间限制）：编号为 i的航班起飞序号不得超过 ki;  第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示航班 a的起飞时间必须早于航班 b。求每个飞机在可行的起飞序列中最小的那个数。拓补很显然，但是直接连边比较难以处理第二种限制，于是我们显然想

2017-11-06 17:21:05 358

原创 bzoj4337: BJOI2015 树的同构树hash

题意：给出n棵树，问有哪些树是同构的。注意到树很多，直接像普通的树hash是行不通的，因为哪怕是自然溢出做模数的冲突概率也极大，正确的做法是对于不同的子树使用不同的base去做hash，就可以将冲突的概率降到最低。#include<cstdio>#include<algorithm>#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i+

2017-11-06 15:38:15 340

原创 JZOJ5457. 【NOIP2017提高A组冲刺11.6】项链

题意：nodgd的粉丝太多了，每天都会有很多人排队要签名。今天有n个人排队，每个人的身高都是一个整数，且互不相同。很不巧，nodgd今天去忙别的事情去了，就只好让这些粉丝们明天再来。同时nodgd提出了一个要求，每个人都要记住自己前面与多少个比自己高的人，以便于明天恢复到今天的顺序。但是，粉丝们或多或少都是有些失望的，失望使她们晕头转向、神魂颠倒，已经分不清楚哪一边是“前面”了，于是她们可能是记

2017-11-06 15:34:54 276

原创 bzoj2258: pku2758 Checking the Text 文本校对 hash+二分

题意：给你一段文本要求比对从文本中某两个位置开始能匹配的最大长度是多少。可以插入字符。一开始不看范围感觉这题巨难，死刚SAM搞不出来，然后看看范围感觉自己被逗了。。 hash+二分，记录一下字符位置就好了，由于插入很少暴力更新hash数组即可。自然溢出。 #include<cstdio>#include<algorithm>#include<cstring>#define fo(i

2017-11-05 21:52:41 260

原创 bzoj3629[JLOI2014]聪明的燕姿搜索+筛法

题意：给出一个数n，求问有多少个数的正约数之和为n。非常好（强）的题，一开始并没有想到。注意到正约数之和，设n，那么n可以表示为: n=ap11∗ap22∗...∗apnnn=a_1^{p_1}*a_2^{p_2}*...*a_n^{p_n} 那么n的正约数之和m=(1+a11+a21+..ap11)∗(1+a12+a22+..ap22)∗...m=(1+a_1^1+a_1^2+..a_

2017-11-05 21:06:32 281

原创 JZOJ5454. 【NOIP2017提高A组冲刺11.5】仔细的检查树hash

Descriptionnodgd家里种了一棵树，有一天nodgd比较无聊，就把这棵树画在了一张纸上。另一天nodgd更无聊，就又画了一张。这时nodgd发现，两次画的顺序是不一样的，这就导致了原本的某一个节点��0在第一幅图中编号为��1，在第二副图中编号为��2。于是，nodgd决定检查一下他画出的两棵树到底是不是一样的。nodgd已经给每棵树的节点都从1到��进行了编号，即每棵树有��个

2017-11-05 16:51:05 660

原创 bzoj1567[JSOI2008]Blue Mary的战役地图二分+矩阵hash

题意：给出两个矩阵，求最大重合。做出两个矩阵的hash以后二分最大正方形的边长，基础hash。模数不好设，用自然溢出就好。#include<cstdio>#include<algorithm>#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) for(int i=a;i>=b;i--)u

2017-11-03 20:31:34 215

原创 bzoj3721PA2014 Final Bazarek 贪心

题意：有n件商品，选出其中的k个，要求它们的总价为奇数，求最大可能的总价。思路巧妙的贪心，由于判断一开始写错了导致没有1A。每次直接选取最大的k个，然后如果是偶数的话就把k个中最小的偶数替换成后面最大的奇数或者把k个中最小的奇数换成后面最大的偶数，因为只有奇数才能改变奇偶性，所以正确性显然。#include<cstdio>#include<algorithm>#include<cstring

2017-11-03 14:20:07 243

原创 JZOJ5442【NOIP2017提高A组冲刺11.1】荒诞三进制状压+欧拉序

题意：我有一个n个点，m条边的无向图，第i个点建立一个旅游站点的费用是c_i。特别地，这张图中的任意两点间不存在节点数超过10的简单路径。为了把一切都做得完善，为了使我感到不那么孤独，我想要建造一些旅游站点使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。我还希望这个建造方案总花费尽量少。请求出这个花费。 czy大爷出的好题。考场上有正解方向的想法

2017-11-01 22:17:35 305

原创 JZOJ5441. 【NOIP2017提高A组冲刺11.1】序列启发式搜索+迭代深搜

题意：给定一个1~n的排列x，每次你可以将x1~xi翻转。你需要求出将序列变为升序的最小操作次数。有多组数据。 n<=25 吃了搜索的亏，表示估价函数这玩意儿碰都没碰过，A*也是好久以前才做过的。。考试的时候打了个搜索还错了，没脸见人了。。有两个优化。第一个就是估价函数，这个必须加上，每次交换的时候，我们假设当前已经交换了x步，然后枚举答案，估价函数g为接下来要把当前序列变为升序的期望步

2017-11-01 16:46:54 600

原创 bzoj1097[POI2007]旅游景点atr spfa+状压DP

题意：给出一个图，要求一定经过一些点，而且经过顺序有要求，点的范围是2到k+1，问最短路径。这题卡常卡的我蛋都碎了都没卡过，最后懒得卡了。其实很简单的一道题目如果不卡常的话，先对于1..k+1跑spfa以后，把题目要求的遍历顺序加入状态中，直接转移就可以了，挺显然的。代码：(TLE)#include<cstdio>#include<algorithm>#include<cstring>

2017-11-01 14:32:55 200

原创 JZOJ5439. 【NOIP2017提高A组集训10.31】Calculate 乱搞

严格来说这题确实就是乱搞。。明显来说，有式子都要你化掉。这题也是一样的，设一个数x，假如有Ac1,Ac2....Ack=xA_{c_1},A_{c_2}....A_{c_k}=x 那么原来的式子就变成了那么我们考虑设g[i]=b[i]%x,即按照a[i]来分组，在设在k个数中有t个数的g要大于T%x. 那么有：然后预处理出后面那两个东西就可以了。#include<cstdio>

2017-10-31 17:03:24 276

原创 bzoj3011: [Usaco2012 Dec]Running Away From the Barn 可并堆(左偏树)

题意：给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于l的点有多少个。n<=2e5,l<=1e18随手抽了一道，以为是个水题，刷水不成反被刷。一开始觉得这题不难，然后样例老过不去，然后看zyf2000的代码。。还是错的，最后直接拿她的交了一下，结果是错的。。一怒之下删掉重写。。开始想的是倍增什么的，但是好像不好动态维护，而且复杂度好大。。然后这就只能可并堆咯，堆维护每个子树内距

2017-10-31 16:51:06 213

原创 bzoj2201彩色圆环期望DP

做了辣么多dp题，只有期望题是我一点想法也没有的题/喷血。。设f[i][0/1]表示做到第i个位置，与第一个位置颜色是否相同的期望值。那么转移的时候枚举最后一段的长度来转移，预处理p[i]表示(1/m)^(i-1)。统计答案时，枚举第1个数所在的连续段长度i，由于是环形，故包含第1个数的长度为i的连续段有i种放置方法，故ans+=i*i*f[n-i+1][0]*p[i]#include<cs

2017-10-30 21:27:35 453

原创 bzoj2083 [POI2004]PRZ 状压DP

题意：一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过. 队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.一开始没有啥想法，直接

2017-10-30 18:29:35 239

原创 JZOJ5436. 【NOIP2017提高A组集训10.30】Group DP

题意：把n个数分成若干组，要求每组的极差和不超过k的方案数。初看的时候很熟悉，应该做过（flag）但是不记得了。一个很显然的想法是设f[i][j][k]表示做完前i-1个，分了j组，和为k，发现无法转移，因为没有记录每组的最大最小值。。那么重新来，设f[i][j][k]表示做完前i-1个，还有j组没有分配最大值，极差和为k的方案数。然后我们发现好像还是不大好转移最小值，于是我们可以用

2017-10-30 14:33:07 306

原创 bzoj1226 [SDOI2009]学校食堂Dining 状压DP

题意：一个学生序列，每一个人有一个想吃的菜t和忍受程度x，如果先让紧跟他后面的人吃，不能超过x个，问最小的进餐时间。如果先做j,在做k，时间是(t[j]|t[k])-(t[j]&t[k]) = =一开始没看见那个紧跟，导致我写了个n^3*7的算法结果T了，想了老长时间不知道该咋做，然后瞄了一波题解，发现看错题目了。。这种题目套路啊，，一看贡献跟相邻的有关就要设一个结尾的状态，那么明显有： f

2017-10-29 22:13:00 248

原创 BZOJ1072[SCOI2007]排列perm 状压Dp

题意：给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。一开始看见s小于10秒想状压，然后在dp式子卡了一下才想到。。设f[i][j]表示使用了多少位的状态，余数为j的方案数。那么明显有f[i|(1<<k)][(j∗10+a[k])f[i|(1<<k)][(j*10+a[k]

2017-10-29 16:38:21 258

原创 bzoj1555KD之死贪心+堆

题意：有一些箱子，有承重和重量，最底下有一个车，有承重限制。要求最多能放多少个箱子。不能说水，也不能说难的一道题。。首先肯定知道如果bt-aw>at-bw那么a肯定要在b上面更加优秀，那么按照这个排序以后来贪心做。如果当前盒子必须要放，那么如果放上去以后超重了，那么把最重的盒子拿出来扔掉再把当前盒子加入。如果堆中没有盒子了则无解。如果当前盒子不必须要放，那么能放就放，如果这个盒子不能

2017-10-29 10:21:33 405

原创 bzoj3198 [Sdoi2013]spring 哈希表+容斥

题意：有n个六元组，给出一个数k，要求这n个组中有多少对之间有k元是相同的。/这种玩意儿一眼容斥啊。首先2^6枚举是哪k位，然后用hash求出在这种情况下有多少对是相同的，设为f[i]. 那么答案就是f[k]∗Ckk−f[k+1]∗Ckk+1....f[k]*C_{k}^{k}-f[k+1]*C_{k+1}^{k}.... 注意到容斥系数是组合数，原因是对应i和i+1会有交集，明显不能只是正

2017-10-28 10:58:18 204

原创 JZOJ5429. 【NOIP2017提高A组集训10.27】排列 DP+容斥

Description有两个长度为n的排列A和B，定义排列的价值f(A,B)为所有满足A[i]>B[i]的位置i的数量。现给出n，A，B和S，其中A和B中有一些位置的数未知，问有多少种可能的填数的方案使得f(A,B)=SInput第一行两个整数n和S 第二行n个数表示排列A 第三行n个数表示排列B 其中A和B中某些位置是0表示当前位置上的数还未确定，保证不存在一个位置i满足A[i]=0且B

2017-10-27 20:05:36 419

原创 bzoj1093[ZJOI2007]最大半连通子图 tarjan+拓补排序

这是一个看懂题目就能切的题。题意：给你个图，求最长路。怎么样，是不是被震惊到了。。。其实就这么简单。。由于原图可能有scc，我们需要tarjan处理掉，然后就是最长路了，由于并不固定起点，我们拓补排序的同时去更新最长路，也可说是DP吧，记录一下到达每个点的方法数，这个也很好记录。 1A，爽。#include<cstdio>#include<algorithm>#include<cs

2017-10-27 08:23:25 230

原创 51nod 1371 填数字 DP

题意：有n行格子，第i(1<=i<=n)行有i个格子，每行格子是左对齐。现在要在每一个格子填入一个非负整数，最后使得每一行每一列的和都不超过2。请计算有多少种方案，答案比较大，请输出对100,000,007(1e8+7)取余后的结果。这题跟bzoj1801很像，基本上就是一道题了，但是注意这个地方可以一次放2，但是那题不行，所以我们还要改一下。设f[i][j][k]表示做到了第i行，和为1的

2017-10-27 07:20:08 193

原创 51nod 1500 苹果曼和树树形DP

题意：给你一棵树，每个点只有黑色或者白色两种颜色，要求通过切割边把树分成k个树使得每个树内只有一个黑色点。原谅我菜，没有第一时间想到转移方程。弱的跟鬼一样了。设f[i][0/1]f[i][0/1]表示以i为根的块内部有一个或者0个黑色点，注意这里的块是未来最终分割而成的块，而不是现在的子树。那么我们就可以转移了，初始化状态为f[x][bz[x]]=1。对于一个状态为1的点x，他既可以

2017-10-26 21:54:35 323

原创 bzoj2141 分块套树状数组/树套树

题意：动态维护逆序对，每次会交换两个数。首先离散一波。然后这题其实很显然，分块处理先，然后对于每次交换，只有在x,y之间的才有用。那么在bl[x]+1和bl[y]-1之间的数都是整块，可以直接用bit维护。否则就是一个块内的，就可以直接暴力维护了。感觉我的实现姿势不好，写的很丑，看了po姐的感觉惭愧。。于是重新来一了几发。树套树也可以做。以后回来填坑。#include<cst

2017-10-26 16:55:11 243

空空如也

空空如也