x_1023-CSDN博客

原创洛谷 P3941 入阵曲 - 前缀和

为啥这么一道弱题难了我好久。。。考虑一维的情况，维护前缀和，其中余数用一个桶来维护，前缀和相等的其差的余数一定相等，于是在桶里搜就好。二维把每一个竖列的线段区间压成一维即可。一维转二维啊#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>#include<set>#include<algorithm

2017-11-03 10:18:34 320

原创 BZOJ 1880 [Sdoi2009]Elaxia的路线 - SPFA+拓扑排序

大家都说这是一道大水题。。。想打dyx应该了解到拓扑排序的功能，类比于食物链那道题，拓扑排序可以dp求出最长链。而在这道题只需求出可以重复的部分搞一个拓扑排序即可。而怎样求重复的部分呢？有一个思想很好：将一条线路拆分成起点到此的距离和终点到此的距离，跑两遍单源最短路，然后类似地枚举求出一些可以重复的路径，Topo一下就好了（尝试新代码风格2333，bz会卡空间，实测将边的数量开小一半就可以过了）#i

2017-10-30 14:25:01 302

原创 BZOJ 4027 [HEOI2015]兔子与樱花 - 贪心

可能做了假题。。。一开始想二维树形dp，结果发现nm乘起来肯定会挂，然后继续膜hzwer学长的代码，发现是道瓜题。。。考虑这样一个结论，下面删点肯定不上面删点优：如果一个节点x其子节点可以被删去，那么至少可以删去一个点，贡献至少为1，而对于x的父节点毫无影响；而若删去x节点，从对答案的贡献上来讲也是1，不会更优，而会让父节点的剩余空间更小，一定不如删去x子节点优。由是从下向上贪心，每次将子节

2017-10-30 10:55:25 252

原创 BZOJ 1875 [SDOI2009]HH去散步 - 矩阵快速幂

大概是矩阵快速幂的一道裸题。。。然后做着做着发现不对。。。好像条件还有限制，两次边不能重。然后苦思冥想好一阵决定抄题解。发现是把点的转移改为了边的转移，思路还是一样的。其实这道题莫名其妙给出m的范围就已经很可疑了，下次应该注意…#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<vector

2017-10-30 10:48:25 355

原创 BZOJ 1999 [Noip2007]树网的核（2282 [Sdoi2011]消防） - 树的直径+单调队列

首先贴出一篇我认为讲的最好的： http://blog.csdn.net/vmurder/article/details/44627469首先证明结论：证明一：树的核必在直径上 1.选定的核与直径无交集显然选的核在直径的一个分支上，如图，肯定不如核与直径相接的那段直径优 2.选定的核与直径有一部分交集如图若选红色部分为核，那么不在直径的一部分相当于优化了BC段的长度，然而如

2017-10-29 23:59:28 296

原创 BZOJ 1079 [SCOI2008]着色方案 - 花式DP

从未见过DP还可以这样玩的，一开始以为是数学，C+容斥，后来觉得不对，哪有数学题长成这个样的，然后各种dp，15维的dp实在是没敢写，于是膜了hzwer的代码。。。真长见识。考虑到c[i]的范围不超过5，其中必有玄机，于是可以用5维表示还可以涂i块木块的颜色种数。因为对于两种均可以涂i块的颜色，除了考虑与上一状态不能重复以外，是完全等价的。排除上一状态影响，则将当前状态的转移的贡献减去一份即可。考虑

2017-10-29 00:28:17 245

原创 POJ 3613 Cow Relays - 倍增Floyd（矩阵加速幂）

大概是倍增Floyd的模板题。Floyd的原理是一个一个点向图中加，k表示已经加了k个点，并且加点可以累加。（可以参考上篇博文）而这道题恰是强制加入T个点，那么我们可以将T利用一种类似于加速幂的思想向其中加点。而需要注意的是，两个数组的合并需要第三个辅助数组维护，辅助数组初值应设为无限大，用已知的两个数组去更新辅助数组，最后将辅助数组中的值赋给答案数组。还需要注意，答案数组一开始除了自己到自己，

2017-10-28 22:58:05 210

原创 BZOJ 1491 [NOI2007]社交网络 - Floyd(相关的DP思想)

首先关于Floyd的理解，有一篇博客讲的很详细： http://www.cnblogs.com/chenying99/p/3932877.htmlFloyd从本质上来讲是一种DP+滚动数组优化，省去了一维k，即对于已用几条边的讨论，而在这道题中，所求的是两点之间经过k点的最短路径条数，那么在dp时加上用乘法原理实现的路径条数统计即可。最后经过k点的条数统计一下即可。这道题还要注意一个问题，最后统计

2017-10-28 14:30:22 213

原创 BZOJ 1307 [ZJOI2008]生日聚会Party - DP

为啥机房的巨佬都说这是一个水题。。。绝望ing /一个尴尬而不失友好的微笑想到解法了，关键不知如何递推，其实很好递推啊，是我太愚蠢了。。。开始想法：dp[i][j][k][l]其中i为男生数，j为女生数，k为所有后缀中女生-男生的最大值，l为所有后缀中男生-女生的最大值。后来发现一件事情就是，设男生人数和女生人数的话循环变量不好写，dp方程中同时出现i-1和j-1，得写记忆化搜索（原谅我的菜）

2017-10-27 16:28:31 227

原创 BZOJ 2763 [JLOI2011]飞行路线 - Dijkstra+分层图/DP

一道分层图的水题，觉得分层图这个玩意非常妙，于是就水了一波。。。记记好是无向图。。。向图。。。图。。。#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<queue>#include<algorithm>using namespace std;const int maxn=1000005;

2017-10-27 09:43:51 187

原创 BZOJ 1912 [Apio2010]patrol 巡逻 - 树形DP(树的直径)

一眼看出了是求树的直径，然而没学过可怎么破。。。然后百度自学了一波 http://www.cnblogs.com/wuyiqi/archive/2012/04/08/2437424.html大概方法就是任找一个点，找离他最远的点，此点必为直径的端点，然后以此为基准再找一个离他最远的点，连成的链即树的直径。（证明见上地址）k=0，观察到每条边必走两遍，无关于出发点k=1即一个裸的树的直径，原因是图中

2017-10-27 00:58:28 213

原创 BZOJ 1922 [Sdoi2010]大陆争霸 - Dijkstra

一遇到图论就一脸懵逼，二脸惶恐，三脸放弃。。。Dijkstra都不会写了，还是退役好了大概就是就是类似于拓扑排序那样，对于有限制的点，其父节点遍历完成后，该节点入度–，等到入度为0即可扔进队列。需要维护两个东西，一个是实际路程，另一个是其父节点的限制，二者取个max即可。图省事用pair一定要设为小顶堆啊啊啊，调了一个小时。。。为什么会这么菜。。。#include<iostream>#incl

2017-10-27 00:39:58 235

原创 BZOJ 1177 [Apio2009]Oil - 花式枚举+乱搞

原来以为是什么神题。。。结果。。。我的三观。。。大概是一道码农题，所有三种情况的分类如下（图源Galaxies：http://www.cnblogs.com/galaxies/p/bzoj1177.html）先前缀和乱搞，然后计算一个点的四个方位的k*k的正方形中的总贡献，左上右上左下右下分别为abcd，然后大力枚举讨论每种情况就好了。。。（真是一道练习写数组下标的码农好题）#inclu

2017-10-25 11:22:01 223

原创 BZOJ 2004 [Hnoi2010]Bus 公交线路 - 状压DP+矩阵快速幂

看数据范围，算法一目了然，然而。。。并不会啊由于p位的限制，所有车一定在p位的限制内转移，于是考虑这样的状压：设一个p位的二进制码，以第一辆车作为视角向后p位，要求p位之内有k辆车。而且由于是以第一辆车作为视角，于是第一位一定是1。设立dp数组dp i j，表示第一辆车在坐标i处，其后的状态为j，dp转移方程为：dp[i][S]=∑dp[i−1][S′]⋅r[S′][S]dp[i][S]=\su

2017-10-25 08:05:37 237

原创 BZOJ 1025 [SCOI2009]游戏 - 筛法+DP

一眼就能看出来这道题的规律，找循环节的lcm，然后。。。然后就不会了。。。这道题已经转化为了：求一堆和比n小的数，且构成的不同lcm的个数lcm(a1,...,an)=px11⋅px22⋅...⋅pxnn其中∑i=1nai<=nlcm(a_1,...,a_n)=p_1^{x_1}·p_2^{x_2}·...·p_n^{x_n}其中\sum_{i=1}^{n}a_i<=n 题意中求的是lcm的可

2017-10-24 20:50:31 278

原创 BZOJ 1084 [SCOI2005]最大子矩阵 - DP

一开始被这道题吓到了，k个是什么操作。。。然后看到数据范围。。。发现就是一道暴力讨论题（当然我是这么想的） m=1很简单对于m=2，每行设了5个状态： 0：此行不选 1：只选左边格子 2：只选右边格子 3：左右均选，且左右均与其上下构成矩形 4：左右均选，且左右横着构成矩形恶心死我了，是怎样的一种勇气支持我写完的它，还在WA了无数次之后依然坚持调试。。。然后暴力讨论。。。注意赋初

2017-10-24 10:00:34 177

原创 BZOJ 2186 [Sdoi2008]沙拉公主的困惑 - 筛法+线性求逆元

首先有一个很好玩的线性递推求逆元的方法： http://blog.csdn.net/whyorwhnt/article/details/19169035对于这道题，若设gcd(a,b)=1，则必然有gcd(a+kb,b)=1，因在mod b系中，加b对于余数无影响。下面需要对此题证明一个结论，即：在1~n!中有phi(m!)n!m!phi(m!)\frac {n!}{m!}个数与m!互质。

2017-10-23 21:53:22 461 1

原创 BZOJ 1296 [SCOI2009]粉刷匠 - DP

一开始看错数据范围，搞了一个O(Tn2m2)O(Tn^2m^2)的，然后就GG了。这种做法的思路是，枚举当前状态，可以继续涂此层剩余，也可以涂他层，一分类讨论即可。后来发现这种做法肯定有大量重复，而且每行之间独立，不必将每行的状态混在一起，于是每行dp搞用cost最多的得分，然后行与行之间分组dp就好了。TLE：#include<iostream>#include<cstdlib>#incl

2017-10-23 19:47:28 245

原创 BZOJ 1042 [HAOI2008]硬币购物 - 容斥+DP

首先假设每种硬币没有个数限制，每种硬币都dp搞一搞，算出来一种币值有多少种组成方式，然后考虑这样一个思路：答案是总数减去不合法情况，而不合法有四种硬币可以选择，于容斥搞一搞就好了。。。我连容斥都不会了。。。真是菜。。。#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>u

2017-10-23 19:38:29 156

原创树状数组的玄学功效

坑1.单点修改区间最值详情请见 ->blog.csdn.net/u010598215/article/details/48206959裸题模板：HDU1745#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>using namespace std;const int

2017-10-23 00:21:20 191

原创 BZOJ 1047 [HAOI2007]理想的正方形 - 单调队列

拆成二维搞一搞就好了撒，还是蛮好想的。先对于row来一波滑动窗口，记录每个节点在n范围内的最值，然后colomn再搞一遍，求个最值一减ans就出来了（注意colomn搞的时候，>=n才记为有效值，反例是左上角的(1,1)相减答案肯定为0）#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<a

2017-10-22 23:06:41 190

原创 BZOJ 1012 [JSOI2008]最大数maxnumber - 单调队列/单调栈

看了hzw学长的博客才发现自己这么多年一直把单调栈误作单调队列/摔单调栈很好写啊，大概就是维护一个单调递减的栈，且元素id单调递增，每次二分查pos即可。单调栈除了直接维护的值外，一般还有一个单调递增的id的值，且id越大越有优的趋势。#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<al

2017-10-22 22:01:53 154

原创 BZOJ 3072 Two Cakes - 记忆化搜索（dp状态优化）

首先基础dp方程很好写： 1.若a[i]==b[j] dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1 2.若a[i]!=b[j] dp[i][j]=dp[i-1][j-1]时间复杂度O(n2)O(n^2)，肯定是过不了，然后优化第二个状态-1操作，若有连续一段不等的序列，那么可以直接跳到下一个相等的节点。考虑一下这个跳的操作怎么维护。由于i与j的差值在跳的过程中不变，

2017-10-21 22:42:51 334

原创 BZOJ 2654 tree - 二分+最小生成树

先给出一种方案：首先二分一个权值mid，然后给白边每一个边加上mid，求一个最小生成树，观察白边使用的个数，二分到白边等于need，ans=val-mid*need。下面给出证明：白边数是一定的，二分权值，mid大，显然选的白边数会减少，具有可二分性。在研究ans的单调性：假设现在有两种情况，白边数均为need，且mid1<mid2现mid_1<mid_2现在假设给情况1的白色边权值

2017-10-21 11:42:01 237

原创 BZOJ 1263 [SCOI2006]整数划分 - 高精度乘法

考虑不是划分成整数，而是划分成任意实数设我们将n划分成了x个正实数之和易知当这x个数相等时答案是最优的那么每个数都是nx\frac n{x}，答案是(nx)x(\frac n{x})^x 设y=(nx)xy=(\frac n{x})^x 则有lny=x[lnn−lnx]lny=x[lnn-lnx] 两侧求导可得y′=(n/x)x∗(lnn−lnx−1)y'

2017-10-21 09:17:55 235 1

原创 UOJ 117 欧拉回路 - 欧拉回路

一道裸题，WA了两屏。。。先贴出基本概念： http://www.cnblogs.com/luyingfeng/p/3877338.html · 无向图欧拉通路：有两个或者没有奇度数的节点的连通图；若有则一定是一个奇节点到另一个的连通图欧拉回路：没有奇度数节点的连通图，那么可以从任意一个节点出发回到该节点 · 有向图欧拉通路：所有节点入度=出度的连通图；或者仅存在两个节点，其入度-

2017-10-21 08:31:42 380

原创 BZOJ 1997 [Hnoi2010]Planar - 2-sat

由欧拉公式：n-m+r=2，n个顶点，m条边，r个面对于简单极大平面图，3r=2m （每个面由3条边组成,一边被2个面共享）代入得 m=3n-6通过m<=3n-6减枝，将m控制在1000以内。平面图，即没有线段交叉，而此题已经给出了一个环，于是每一条非环上的线段只有两种情况，一是在环外，二是在环内，若有两线段相交则不为平面图。确定两个线段的关系，若其坐标交叉，则必然不能同时取外

2017-10-20 19:51:45 192

原创 BZOJ 1823 [JSOI2010]满汉全席 - 2-sat

好裸的一道题。建边的思路，对于一个评委来说，设一个材料A选h，B选m，那么若A选m的话，B必须选m，B选h的话，A必须选h（因为两者之一要满足被选）2-sat的关键思路就是找出一个被选，另一个必须被选的这样的约束关系。#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm

2017-10-20 09:49:17 231

原创 BZOJ 1430 小猴打架 - prufer编码

prufer编码和无根树的转化问题：树化prufer：在叶子节点中寻找编号最小的节点，将与之相连的父节点加入prufer队列里，然后删去该叶子节点，直至图中只剩下2个节点，于是prufer数列共有n-2位prufer化树：将不在编码内的最小编号的节点和队列的首元素相连边，然后删去首元素，直至队列中只剩下两个节点，相连边即可。于是对于一个完全图求生成树的个数，他的prufer序列里有(n-2)位，每一

2017-10-20 08:08:39 171

原创 BZOJ 1856 [Scoi2010]字符串 - 卡特兰数推广

先mark一下别人博客：卡特兰数的推导（用01序列推导的，过于抽象）： http://blog.csdn.net/youwuwei2012/article/details/38904839 （好像还有严格证明，只不过看不懂QAQ）然后以这种推导的思路进行更易于理解的证明： referring to: http://www.cnblogs.com/jianglangcai

2017-10-19 23:14:38 412

原创 BZOJ 1996 合唱队 - 区间DP（以及DP注意事项）

很快看出来是区间dp，搞了个O(n^3)的dp方程，0/1状态表示当前区间的首/尾作为末尾，然后搞记忆化搜索半天没搞出来，还得搞个RMQ，于是百度了题解（为毛题解都长的一样，还都是WA的。。。这群人抄也不抄仔细点。。。）题解大概就是通过一个个数插入将区间向两边扩大，而且只能放在两头，条件就是上一个放的数值和这个数的数值满足题意。讨论一下就好了，dp方程写出来还是很简单的。（其实就是将我的思路改

2017-10-16 22:27:12 272 1

原创 BZOJ 2330 [SCOI2011]糖果 - 差分约束

发现篇博文讲差分约束讲的挺好 http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html照着文章自学了一遍，发现这道题就是一道裸题嘛。设一个超级源，表示基础的0，要求所有的值均严格大于0，spfa一下，将距离数组相加就是答案，若存在负环，则不存在一个合理解。关于差分约束的建图，还想mark一下： 1.若求一个变量xix_

2017-10-16 20:31:34 158

原创 BZOJ 1907 树的路径覆盖 - 树形DP/贪心

树形DP的做法显然：对于任意一个节点，它可以连接两个节点，那么设0状态为不能再连接节点，1为还可以再连接一个节点，伸出一条手臂可以再搭上别的节点。 0/1状态初值均设为1。那么合并子树的过程中有如下的转移方式：1.父节点和子树相连，则两个状态必须都为1，由于连接即为路径的延长，相当于取消子节点那一条连接着的路径的独立性，合并到父节点路径上，则可以消除那一条子节点路径的代价。 2.父节点不

2017-10-15 17:51:58 279 1

原创 BZOJ 3155 [Hnoi2013]数列 - 树状数组/线段树区间加

如果用线段树的话，做法很好想。以i为下标记录SiS_i，那么aia_i被SiS_i到SnS_n所含，每次修改则将SiS_i到SnS_n的每一个S减去修改的差值即可。时间：624 ms#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>using namespace s

2017-10-15 14:56:17 153

原创 BZOJ 4236 JOIOJI - 玄学乱搞

推出个公式就成了大水题了，关键这个公式对于蒟蒻来说太难想了。 sum为前缀中各个字母个数，假设一段区间[j,i]满足条件，则有： sumO[i]-sumO[j-1]=sumI[i]-sumI[j-1]=sumJ[i]-sumJ[j-1] \\ 等价于： {sumO[i]−sumI[i]=sumO[j−1]−sumI[j−1]sumO[i]−sumJ[i]=sumO[j−1]−sum

2017-10-14 21:44:55 172

原创 BZOJ 1485 [HNOI2009]有趣的数列 - 卡特兰数

关于卡特兰数的介绍 ->http://blog.csdn.net/hackbuteer1/article/details/7450250 (其中第一道题就是这道题的翻版）首先将2n个数排列为序列A，从前向后选出n个作为奇数项，剩下的作为偶数项，而且选定的数组成的有趣的数列只能有一种（选出的奇数项数字和偶数项数字要升序插入数列，排列只有一种）。要保证奇数项小于偶数项，那么对于每一位A中的数，其前选

2017-10-14 21:35:38 206

原创 UVa 1471 Defense Line 防线 - LIS变形

前面的博文有写过LIS O(nlogn)的做法，今天再复习一下。戳这里->http://blog.csdn.net/x_1023/article/details/70259967首先考虑一个潜能数组c的作用： c[i]表示长度为i的最优上升子序列的末尾值（即末尾值的最小值，这样决策一定最优，因前面部分没有后效性）。于是每次统计答案并更新c数组即可，以下为一个更方便写的板子，运用了lower

2017-10-13 00:39:40 196

原创 BZOJ 2789 Letters - 贪心+树状数组

坑首先考虑这样一个结论：对于第二个串的一个字母（这个字母X是第num次出现），要保证交换最小次数，那么第一个串一定是第num个

2017-10-12 19:08:05 236

原创 UVa 11134 Fabled Rooks 虚拟的车 - 贪心+思维

给一个n x n的棋盘，要求在上面放n个车且相互不攻击，而且对于第i个车要求必须在给定的矩形中（每个车所对应的矩形已给出），求一组满足的解，无满足的情况输出”IMPOSSIBLE”## 坑 ##首先考虑拆点，将二维坐标拆成x轴和y轴的两组，对于每一个轴要求在给定的n个线段上选出一个1~n的排列。如果考虑每条线段只能选择一个数，每个数的选择只能取一次，满足二分图的性质，可以考虑拿最大匹配写（写了个H

2017-10-11 15:48:12 144

空空如也

空空如也