- 博客(75)
- 收藏
- 关注
RSS订阅
转载 Vim简明教程【CoolShell】
vim的学习曲线相当的大（参看各种文本编辑器的学习曲线），所以，如果你一开始看到的是一大堆VIM的命令分类，你一定会对这个编辑器失去兴趣的。下面的文章翻译自《Learn Vim Progressively》，我觉得这是给新手最好的VIM的升级教程了，没有列举所有的命令，只是列举了那些最有用的命令。非常不错。——————————正文开始——————————你想以最快的速度学习人类史上最好
2013-07-06 20:12:05
619
原创 hdu 3514 Queen’s Case
题意：在一个格子图当中，每一个回合皇后先走，然后是士兵走，现在怎么定义我们的胜负呢，如果一个回合结束后，那么如果皇后和士兵在一个格子之内，就是士兵赢，如果皇皇后在出口处而士兵不在同一个格子里面，那么就是皇后赢，否则进行下一回合，每一个人物可以向周围4格走，或者不走，总共5种选择。解法：最后的结果会有三种，皇后赢还是士兵赢，还是平局就是双方都不能赢，普通的dag上面的转移博弈就是规定了无环，同时
2013-12-03 22:15:41
1308
原创 hdu 4807 Lunch Time
题意：在一个有向图当中，现在每一条边带有一个容量，现在有K个人在起点，需要到终点去吃饭，询问这K个人最后一个人到达食堂的最小时间是多少。想法：联想到普通的网络流，那么我们网络流可以很轻松的求出两个点之间的最大容量是多少，但是现在的问题就是刚开始在起步的时候那么最开始的容量是不可能到达最大的，因为人还在途中，假设我们从时间角度来分析这个问题，再联想到我们网络流求法，费用流当中，求出来的就是当然费
2013-12-03 19:03:39
1820
原创 uva 12534 Binary Matrix 2
题意：在一个40*40的矩阵中，仅存在两种元素，0 和1，现在的要求就是需要改变最小的次数（01互换），使得每一行之间1的个数相同， 并且每一列1的个数相同，12年泰国的一个赛区，现场过的人比较少。解法：费用流，不会搞，看了ac代码，发现是这样的，先枚举台面上最后总共1的数目，然后建成二分图，每行建成一排，每列也建成一排，那么具体的费用就是ones-now + costones就是图中所有
2013-12-02 22:25:33
2061
原创 sgu 525 Revolutionary Roads
题意：在一个1000个点中的有向图中，现在可以进行的操作就是将一条有向边修改成无向边，那个图中的最大的强连通分量的点数是多少。分析：很显然的分析就是那么修改的那一条边一定不是强连通分量之内的边，否则那么就是没有效果的，如果能产生效果的一定是修改后可以将多个强连通分量融合起来，那么现在的问题就是如果转变一条边之后，能够连通多少个点，如果每次去算的话会比较麻烦，这个问题可以进行n^2的预处理，预处
2013-12-02 19:36:43
1319
原创 uva 12544 Beehives
题意：无向图中所有的边权都是1,现在这道题目的意思就是要找出图中最小的一个环。解法：之间做过一道类似的题目，今天被坑惨了，floyd的做法，严格n^3，普通的floyd里面加了一个枚举环的部分，但是这道题目数据比较大，n=500，然后就无情的tle了。更高级的做法是从每一个点开始bfs一下，然后记录每个点来自的前驱，然后如果一个另外一个点没访问过，那么就加入队列，如果已经访问过，必定构成一
2013-11-27 21:18:05
921
原创 ural 1905 Travel in Time
题意：最短路的变形，10万个点，10万条边的有向图，对于每条路径描述4个信息，就是出发点，抵达点，出发时间，抵达时间，然后告诉我们现在所在的星球和时间，还有需要到达的目标星球和截止时间，现在的要求就是询问一种能够到达目标星球在规定的时间内的方式， 其中几点要注意的是，可能时间倒流，并且一个人不能重复呆在一个请求上在同一时刻。分析：假如，我们如果删去一个人看见自己的这个约束，那么怎么做，直接bf
2013-11-26 22:08:10
806
原创 hdu 3732 Graph Reconstruction
题意:长沙现场赛的一道题目，现在的要求是给定一个n个点的无向图的度序列，现在的要求是构造出图，hdu上面有一题是要求给定一个度序列，那就很简单了，根据havel定理直接可以得出解，但是这道题目问题在于要判断是能产生一组解 还是多组解，如果能够产生多组解的话要输出两个解。解法：先根据havel定理构造出一个解，那么另外一个怎么搞出来，一种比较暴力的方法就是就是删去每一条存在的边，然后再次现在进行
2013-11-24 22:21:28
1087
原创 sgu 544 Chess Championship
绝好的一道题目，以前没做到过，要不是队友想到这个dp，要我还真不会搞。题意：现在有两个比赛队伍，每个队伍的个数都在500之内，现在两个队伍之间的能力不会重复，要全排列安排比赛，问存在多少种排列使得 A的得分减去B的得分为K，得分的定义是本队的能力值大于对面的那个人。解法：刚开始模型很混乱，根本没法搞，最后的解法是这样的，将所有的能力值进行从小到大的排序，然后dp[pos][a][b
2013-11-22 22:47:49
863
原创 uva 12616 - Gymman vs Fila
题意：这道题是在20000个点中选出有多少三元组 （a, b, c ) 满足 在图中割去c之后a和b之间不连通。解法：如果要删去一个点一些点不连通，那么这个点一定是割点，那么就对于每一个割点进行统计，统计出每一个割点删去之后，会形成几个联通块，并且统计出里面的数目，这样就可以算出来了，怎么统计呢，在做完点双连通之后， 这个时候我们就统计出了每一个极大双连通分量，简单的分析之后，每一个极大点双连
2013-11-21 21:36:38
1126
原创 uva 12618 - I Puzzle You
题意：题意还是非常简单的，就是一个三阶魔方18种方法改变，跟普通玩魔方一样，题目要求搜出七步之内的解，想到了IDA*，18^7还是稍微有一些大的，大约有6亿的状态，需要 一个比较可靠地估价函数。解法：刚开始以为旋转一个面之后最多改变12个格子，就用与当前中心点不同的格子数除12，这样返回wa，检查了很久想不到，后来才想起来其实旋转中间这个面可以改变24个面，一下子就tle了，这个估价函数的作用
2013-11-21 20:09:24
953
原创 hdu 3097 The Partition of A Graph uva 11396 Claw Decomposition
这两道题比较像，就放在一起写吧。题意：第一道题，在1000个点的无向图中，现在要把所有的边分成一对一对的，要求这一对边必须要在图中相邻，询问存不存在这样的一种划分方法。第二道题，在400个点的图中，保证每个点的度都是3，那么现在要分成爪子的形状，就是中间一个点度为3，其他外面连接了三个点，询问能不能将图中划分成一些爪子。想法：第一题中，如果这样考虑这个问题，将原图中的点看成边看
2013-11-20 21:06:32
992
原创 hdu 4780 Candy Factory
题意：M个工厂生产N个糖果，现场过的人很少，但这道费用流本身并不是很难。建图：我的建图是，每个糖果要么从初始状态转移过来，要么从其他糖果生产完的状态转移过来，同时拆点保证每个糖果只能生产一次。另外看了杨神的建图，复杂度一样，但是他的抽象的更好，直接就是选择来源，这也是一般费用流的想法。贴一下他的代码#include #include #include #include
2013-11-19 20:12:13
1441
原创 13成都A Assignment For Princess
题意：在一个80个点的有向图中，现在已经知道了这个图的点数和边数，边的权值是从1-M,现在需要构造一张图，满足以下三个限制(1) 从每一个点开始都可以到达另外任意一个点。（2）从图中每一个点开始都可以回到自己。（3） 图中的任意一个环上的权值和必须是3的倍数。解法：这道构造题，在赛后听到了威哥他们说的解法，今天自己也是差不多这么写的，但是总是觉得怪怪的，就是刚开始我们先放一个大环罩
2013-11-16 20:24:53
833
原创 uvalive 6206 Reduce the Maintenance Cost
题意：在10000个点的一个无向图中，定义P = 删除某条边之后有多少点对因此不连通，那么给每一条边定义一个val值，val = P*len，len 就是本身这条边自己的长度，每一条边的val就是维护费用要求连接这条边的两个点中的一个点来承担，现在每个城市最初有一个 初始的维护费用，问 怎么样的一个分配方案能取到 每个城市的维护费用最大值最小。解法： 很明显桥边具有val值，其他边是
2013-11-13 16:27:47
868
原创 博弈搜索中的记忆化
先看下面几道题目 uva 11884 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23316hdu 4778 http://acm.hdu.edu.cn/showproblem.php?pid=4778hdu 4753 http://acm.hdu.edu.cn/showproblem.php?pid=
2013-11-10 19:33:26
755
原创 hdu 3762 K-Graph Oddity
题意：在一个10000个奇数点的无向图中，现在选出最大度为k，然后 如果k是偶数，k++， 现在需要使用k种颜色去将所有的点 进行染色，要求任意相邻的两个点不能相同。询问一种染色方案。解法：刚开始的想法是安排一种染色序列，然后如果有矛盾，然后就去调整点的染色，后来发现这样实在搞不出。看了别人ac的代码，可以这样说，从任意一个点开始任意得到一个遍历序列（包括bfs和dfs），然后开始按照这个序列
2013-11-07 16:05:06
1319
原创 URAL 1979 Resources Distribution
题意：一个6面的魔方，每个面的阶数在1-100 之间，那么总共有6 * n * n个面，现在需要将1-6*n*n 这些数字填到魔方的格子中去，使得现在魔方三个维度上面总共有 3*n个环，使得保证每个环的和都相等。构造方法：因为所有的点都被计算了两次，所以总和是确定的，那么每一个环的总和就是确定的，等于2*n * (6*n*n +１) ,所以只要满足 一个点和他对面的那个点一定是在两个个环之中的
2013-11-05 20:05:12
721
原创 hdu 4118 Holiday's Accommodation
题意：在一棵树中有n个点，然后有n个人在每个节点上，现在要给每一个人在树上找到一个新的位置安排，相当于一个置换群，询问如何使得每个人的距离 之和 达到最大。刚开始不好想，觉得没法处理，后来渐渐的想到了一个简单的模型，就是所有的距离可以分为树上的每条边来贡献的，所以就是如果看每一条边，它的两个节点左右都是一棵树，那么最后的置换群中，有一些左边的点会进入右边，那么假如有K个，那么这条边贡献的距离就
2013-11-02 18:53:42
725
原创 aizu 1318 Long Distance Taxi
题意：在一个无向图中，现在指定起点和终点，出租车在开，但是因为油箱的油有限制，所以只能行驶一定的距离，现在在一些特定的城市中会存在加油站，其他城市不能加油，询问存在一条最短的路径，从起点到终点的合法路径，城市数上限6000.解法：因为有存在油量的限制，所以既然到了一个城市之后肯定是加满油，那么到达下一个加油站之间的最短路一定是在限制之内的，所以先对所有的加油城市进行一个预处理，处理处能
2013-11-01 21:33:50
666
原创 13 成都 F
在成都的时候跪舔这道题目，确实让人不甘心，唯一能做的只是希望下一场能正常发挥吧。这道题目因为陈题的关系吧，现场一血来的特别快，而且还成为了最水的一道题目。题目大意：在10万个点的一个无向图中，所有的边不是黑边就是白边，现在给定所有边的属性，问判断是否能形成一颗生成树其中包括了斐波那契条白边。解法：做法就是求一次最小生成树和最大生成树，那么所有生成树中能包含的白边就是 最小和最大之间的所
2013-10-29 20:48:21
778
原创 小白入门C语言
该如何快速的学习C语言1.程序的工作原来是怎么样的？我们写出来的程序最终都是交与CPU进行执行，但是计算机的体系之中只有0和1，所以我们写出来的字节码程序必须要翻译成一种cpu能读懂的语言。这一步就叫编译。通过编译，就可以将我们写好的程序转变成一个二进制程序，就能在cpu上运行。2.如何写出第一个C语言程序？c语言程序的后缀名都是.c ，所以我们在桌面建立一个test.c 文件，建
2013-10-29 10:57:01
1202
原创 ural 1752 Tree 2
题目大意：在一棵20000个节点的树中，有50000个点的询问，对于每个询问，要求求出距离某点固定距离的任意一个点。比赛的时候跪舔整场，算法确实不是很难，想不到 怎么破？先求出整个树的直径，从直径的两个端点开始进行dfs，可以证明，对于任意一个点的询问，要不就是在该点到直径上的根上的某点，否则就是在直径上的点。所以在这两次dfs中必定能找到解，否则就无解。
2013-10-05 22:46:32
735
原创 hdu 4765 Tsp
题目大意：在100个点中的图中，要求现在选择一条路径遍历所有点，而且，加了很多限制条件。分析：在比赛的时候以为是图论，然后看了一下，比赛的时候以为这么多条件，才100个点，那么我们就爆搜一下吧，赛后一看别人的tle代码，都是爆搜，幸亏比赛的时候被其他题目卡着没时间写这道题目，额解法：赛后看了清华的代码，终于给我找到一份比较简洁的代码，发现做法是区间dp。分析一下题目中的条件，可以得出几
2013-09-29 22:33:36
1506
2
原创 codeforces 160D - Edges in MST
题目大意：给定一个10万个点的无向图，求出任意一条边是在3种属性，（1）存在于任意一个mst上 （2）存在至少一个mst上 (3)不存在任意一个mst上。发现不写题解不长记性啊仔细分析后发现，如果按照最小生成树的解法，先把边按照边权进行排序，那么这个时候，如果这个边不是存在于所有的mst上面，等价的条件就是和他长度相等的那些边可以和他进行互换。（1）将边按照边权进行排序，一次取出所有长
2013-09-25 17:36:44
1302
原创 hdu 4685 Prince and Princess
2013年长沙区域赛网赛I题 当时看到题就发现这题和hdu4685是一模一样的，但是很遗憾在比赛的时候居然没能过。深深的自责。写错一句代码题意：20000个点的二分图，冗余边的定义就是如果这条边进入匹配之后，总匹配数无论如何怎么选择都无法达到最大匹配。解法：先求出一次二分匹配，先考虑王子和公主都进入完美匹配的情况，那么对于任意一个王子，对公主建图，从他匹配到的公主连一条边到他剩余喜欢的公主
2013-09-23 22:27:10
1230
1
原创 hdu 4650 Minimum Average Weight Path
在最优比例生成树问题中，对于01分数规划采用的是二分法来解决01分数规划的问题，白书上有一道题目，问50个点的无向图，平均权值的最小的环是多少。 联想到这道题，这道题目求的是全源平均最短路径，当然想当然地想到了枚举任意两个点然后二分求出值，虽然能出sample，TLE了，确实全源的情况下，这样枚举+二分的复杂度太高了。
2013-09-22 16:36:03
697
原创 完全极大极小搜索与alpha-beta剪枝
这个东西属于博弈的范畴了，虽然在去年就听白爷讲过这个东西，后来就一直放着，觉得出现的概率不大，前一段时间非常想学这个东西，可惜总是在做其他事情，终于连续两场比赛遇到了极大极小搜索。 这个东西听起来玄乎，其实非常有趣。 组合博弈中的几个条件就是每轮双方操作一步，在有限步操作之后进入最终状态不包含平局。但是最终的状态仅含有必胜和必败。如果对于整个局面需要求出最优解是
2013-09-22 16:17:18
1203
原创 hdu 4337 King Arthur's Knights
有些构造题确实挺有趣的，好难题目大意：有150个骑士，每个骑士拥有至少半数的人是朋友，要求一条哈密尔顿回路。分析：判断哈密尔顿回路是没有充要条件的，好像也没有多项式算法来判断，幸亏离散里面有这样的一个定理，如果其中每个点的度大于(点数+1)/2，那么一定存在一条哈密尔顿回路，借助这个性质。这道题能够通过o(N^2)的算法构造出来。算法： 中等题，构造一个特殊图的Hamilto
2013-09-13 22:30:12
678
原创 hdu 4700 Flow
题目大意：100个点之内的一个无向图，现在已经得到了全源最小割矩阵，那么能不能求出一个满足这个最小割矩阵的图。解法：题解的意思如果存在解，那么一定可以构成一棵树，Gomory-Hu tree ，至于为什么是一棵树无法理解。现在的目标就是构造一棵树，特殊性在于这是一颗树，任意两个点之间的路径是唯一确定的，采用递归的策略去构造这棵树，路径确定下来之后所以先找到流量最小的那条边，这样子A = (
2013-09-13 14:41:18
1123
原创 hdu 4712 Hamming Distance
题目大意：给定10万个01字符串，对于任意两个字符串异或之后求出剩下1的个数的最小值分析：这道题很难进行预处理或者动态规划。但是这道题经过分析之后有几个特点，总长度很小，才10，最后的答案在20之内。做法1:可以进行ID，可以保证随机数据情况下如果串比较多，那么最后的答案肯定会比较小，然后对每个串进行搜索。我们还可以想到 因为总长度才20，所以总的状态才2^20，100万，那么如果采用
2013-09-13 14:30:07
777
原创 dag图中顶点覆盖问题
dag值得就是有向无环图，所以我们特别的针对无环这个特性。问题（1）最小路径覆盖问题，用最少的条数的链去覆盖掉我们所有的点，其中每一个点覆盖且仅能覆盖一次。因为无环，所以这里存在一类高效的解法，就是将原图中的点进行拆点， 然后进行二分匹配。完美解决。问题（2）如果还是在一个dag图中，我们采用链去覆盖掉所有的点，这样子前面的二分匹配肯定是没有办法解决了。首先联想到一种土办法。就
2013-08-03 20:29:22
1239
原创 叉姐专场小记 (scu 4290-4299)
4290 Xor :题意：给定A集合和B集合，集合中的个数都是奇数个，询问是否存在x使得A集合中的每个数字异或后 使得和B集合相同。刚开始没看懂是集合，坑了很久。刚开始不会做，被点播了，因为异或，所以a1^x ^a2^x .... ^b1 ^ b2 = 0;又因为x奇数个，所以可以直接计算出x的数字，当然这个是计算出来的，然后再一遍，验证这个x是否成立。4291
2013-07-21 16:42:59
1855
原创 Ural 1548 Sakura and Statistics
这道题就是在一个50*50的方格内存在一些0和1，同时每一列中的1全部是连续的，问存在至少多少个矩形去覆盖掉所有的1，同时注意矩形只能覆盖到所有的1。 想法很简单 就是dlx重复覆盖，居然hust上面都没有人做，其实做完发现没有想象的那么神，昨天的做法对于所有的矩形都建成一行，超时了，今天突然意识到其实在内部的矩形是没有必要的，就判断每一个矩形是不是必须的，也就是是不
2013-07-19 00:46:05
1282
原创 spoj 13041 The Black Riders
这道题目真的很难吗？可能是这种建图之间没有遇到过吧，比赛的时候脑子里也想不清楚，真是应了蒋神的话，不会做都是因为没做过，这么一道题目卡全场，真是不想说了。题目大意：有100个以内的霍比特人，有100个以内的洞，现在每个霍比特人需要逃到一个洞当中，在逃到一个洞中之后，花费c时间可以在挖一个洞，这样子可以再容纳一个霍比特人，但是一个洞穴最多只能容纳两个霍比特人。问最少多少时间可以使得至少K个霍比特
2013-07-18 20:48:13
777
原创 Ural 1544 Classmates 3
这道题目看似很经典的一题，之前肿么就是没有做到过呢？ 题意就是在一个50个点之内的无向图中，每个顶点有一种颜色，每一次操作可以将我们该点和周围所有通过该种颜色相邻的点都转变为另外一种颜色，最少需要几次可以将图中所有的点转变为同一种颜色，并且输出操作。 解法：将相邻的同一种颜色缩成一个点，那么然后枚举每一个顶点，从这个点开始进行最短路，距离最远的那个点的距离就是需
2013-07-17 00:19:45
630
原创 hdu 3551
这道题目的意思是给定一个顶点至多为50的无向图中，删去一些边，使得子图的度符合给定的度序列。 题意真的非常简单，就是要选择一个边集去删除。具体怎么实现呢。联想一下，是不是想到了二分匹配，其中选择一些边集，使得我们的左右的两个边只能覆盖一次，而这道题目当中我们的每个顶点不仅仅是可以覆盖一次，可以覆盖多次，怎么办，没错 ，将我们的每个顶点进行拆点，将每个顶点拆成需要减少的数量个，然后
2013-07-16 19:56:38
1547
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人