算法：UVa 11536 - Smallest Sub-Array

2017年02月05日 55 阅读

算法：UVa 11536 - Smallest Sub-Array2014-03-17 csdn博客 shuangde800题目大意：给一个序列X1 = 1X2 = 2X3 = 3Xi = （Xi-1 + Xi-2 + Xi-3） % M + 1 for i = 4 to N求一段最短的连续子序 列，使得这个子序列包含正整数【1，k】思路：扫描一遍即可，用一个队列记录下【1， k】区间内的数的位置，再用一个变量count维护【1，k】内不重复数的个...

算法：UVa 11572 - Unique Snowflakes （好题）

2017年02月05日 58 阅读

算法：UVa 11572 - Unique Snowflakes （好题）2014-03-17 csdn博客 shuangde800题目大意：给n个数， n<=100W，求一个连续子序列，这个子序列中没有重复的数，问这个子序列最长是多少？思路：开一个数组pos， pos[ x ] 表示x出现的位置， 这个数组初始化为-1用一个变量start来记录当前枚举序列的起点，初始为0然后枚举这个序列，依次记录每个数的位置，假设当前枚举到i， 在记录这个位置之前...

算法：uva 10730 - Antiarithmetic

2017年02月05日 58 阅读

算法：uva 10730 - Antiarithmetic2014-03-17 csdn博客 shuangde800题目大意：给n个数组成的序列，他们是0~n-1， 问序列中是否有按顺序的3个数，是等差数 列。思路：用一个数组记录每个数在序列中的位置，然后枚举3个数中最小的一个，再枚 举等差数列的增量，最后看着三个数的位置是不是连续的即可。n最大为1W，但这个算法的复杂 度看起来好像是O（n^2），怎么速度还挺快的呢？粗略的分析一下复杂度吧。第一层for循...

hdu 4527 小明系列故事之玩转十滴水

2017年02月05日 57 阅读

hdu 4527 小明系列故事之玩转十滴水2014-03-17 csdn博客 shuangde800小明最近喜欢上了一个名为十滴水的游戏。游戏是在一个6*6的方格 内进行的，每个格子上有一滴水或者没有水滴。水滴分为四个等级1~4。初始时你有十滴水，通过把水加 入格子内的水滴，会让水滴升1级。你也可以把水放到空格子内，这样会在这个格子里面产生一个1级的 水滴。当水滴等级大于4时则会爆裂为四个小水滴，并向四个方向飞溅。每个飞溅的小水滴碰到其他水滴 后会融入其中...

算法题：uva 10535 - Shooter

2017年02月05日 53 阅读

算法题：uva 10535 - Shooter2014-03-17 csdn博客 shuangde800题目大意：一个人拿着激光枪站在坐标（x,y）处，周围有N个墙，墙的两端点坐标为（x0, y0, x1, y2）。这个人朝着某个方向开枪，激光可以穿过任意数量个墙。求最多一枪能够穿过几个墙？注意 ，如果激光正好在墙的一端擦边而过，也算穿过。思路：看下图，把人站的坐标看做是坐标的原点，人的正东西向为x轴，南北为y轴，正东向为0度。然 后就可以分别计算每一个墙...

算法题：uva 1398 - Meteor

2017年02月05日 54 阅读

算法题：uva 1398 - Meteor2014-03-17 csdn博客 shuangde800题目链接：http://uva.onlinejudge.org/index.php？ option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4144先存代码，睡觉去了 睡觉代码：#include<iostream>#includ...

算法题：uva 1326 Jurassic Remains（中途相遇法）

2017年02月05日 54 阅读

算法题：uva 1326 Jurassic Remains（中途相遇法）2014-03-17 csdn博客 shuangde800题目大意：给n个大写字母组成的字符串，选择尽量多的串，使得每个大写字母都能出现偶数 次。思路：一看到Time limit: 18.000 seconds， 很high地无任何优化直接暴力写了一 个，9s多过了，估计是自己有史以来耗时最久的一次AC 尴尬然后想着怎样优化一下，发现所有 字母出现的次数可以用二进制来表示，0表示偶数，...

算法题：uva 10755 - Garbage Heap（三维最大子矩阵）

2017年02月05日 55 阅读

算法题：uva 10755 - Garbage Heap（三维最大子矩阵）2014-03-17 csdn博客 shuangde800题目链接:http://uva.onlinejudge.org/index.php？ option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=1696和二维的最大子矩阵的思想是一样的，只是变成了三维的。枚举层数...

算法题：uva 1382 - Distant Galaxy

2017年02月05日 50 阅读

算法题：uva 1382 - Distant Galaxy2014-03-17 csdn博客 shuangde800题目链接1. 坐标值比较大，所以离散化坐标2. 坐标的绝对值不超过10^9，说明可能有负数，所以把 全部坐标移动转换为正数（加上10^9）3. mat[i][j] ，表示（0,0） （i, j）为对顶点矩形之 内包括边界上有多少个点。4. 枚举矩形的上下界，然后选择左右边界。 对于确定的左边界left 和右边界right， 假设是下图的R3是...

算法题：uva 1330 - City Game

2017年02月05日 55 阅读

算法题：uva 1330 - City Game2014-03-17 csdn博客 shuangde800题目链接:http://uva.onlinejudge.org/index.php？ option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076以前做过一道一维的，这题只是变成了二维的，其他方法都一样。HDU 1506 Large...

算法题：uva 11549 - Calculator Conundrum （Floyd判圈法）

2017年02月05日 55 阅读

算法题：uva 11549 - Calculator Conundrum （Floyd判圈法）2014-03-17 csdn shuangde800题目链接直接模拟计算过程。 可以看出计算器显示出来的数是循环的，关键在于模拟的过 程中，怎样判断是否循环了。可以采用STL中的map或set，不过效率较低。hash的话耗很大的空 间。从大白上可以知道还有一种叫做“Floyd判圈法”的东西。就是假设有两个小孩子在一个圆 圈跑道上赛跑，同时...

算法题：uva 10318 - Security Panel

2017年02月05日 55 阅读

算法题：uva 10318 - Security Panel2014-03-17 csdn博客 shuangde800题目链接:首先，可以确定每个格子只能选一次，因为选任何大于0的偶数次，等于没有效果 一样。然后，就可以把这题理解成从r*c的矩阵中选择一些格子进行“点亮”操作，使得最终所 有格子都是“亮”的状态。那么，每个格子要么有点亮操作，要么没有，总共复杂度为2^25，显然必须 进行减枝。假设从第一行第一...

hdu 4531吉哥系列故事之乾坤大挪移

2017年02月05日 55 阅读

hdu 4531吉哥系列故事之乾坤大挪移2014-03-17 csdn博客 shuangde800题目链接：http://acm.hdu.edu.cn/showproblem.php？pid=4531这道搜索题挺恶心的。。。比赛时没有写出来。首先要解决的问题是怎样判断符合条件的状 态，即所有一样的颜色是连在一起的。我是采用最简单也最搓的方法，按上下左右顺序给每一个小三角 形标号1～36，然后建立一张邻接矩阵图，然后bfs判断。然后就是主要的暴力枚举部分，每...

算法题：uva 1312 - Cricket Field.

2017年02月05日 58 阅读

算法题：uva 1312 - Cricket Field.2014-03-17 csdn博客 shuangde800题目大意：在w*h的坐标上给n个点， 然后求一个最大的矩形，使得这个矩形内（不包括边界 ）没有点，注意边界上是可以有点的。首先要把这些坐标进行离散化，离散话时要注意一点，如 果有两个点原来坐标不是相邻的，但是离散化以后却变成相邻了，这时候要在它们之间加上一个点。预处理后，枚举矩形上下界，然后再用O（n）的复杂度找出左右边界。代码：#inclu...

算法题：HDU 4300 Clairewd’s message（拓展KMP）

2017年02月05日 57 阅读

算法题：HDU 4300 Clairewd’s message（拓展KMP）2014-03-17 csdn博客 shuangde800链接：http://acm.hdu.edu.cn/showproblem.php？pid=4300题目大意：发送一个密文，为字符串S。这段密文的前半部份是加密过的，后半部分是没有加 密过的。现在这段密文被截获，但是密文的尾部的一部份损失了。例如，假设密文是xxxxzzzz, xxxx是 加密过的，zzzz是没加密的，因为损失...

算法题：HDU 2594 Simpsons’ Hidden Talents（KMP）

2017年02月05日 55 阅读

算法题：HDU 2594 Simpsons’ Hidden Talents（KMP）2014-03-17 csdn博客 shuangde800链接：http://acm.hdu.edu.cn/showproblem.php？pid=2594题目大意：给两个字符串s1和s2, 求出是s1的前缀并且是s2的后缀的最长的字符串。分析与总结：真正理解好KMP算法，这题就是水题。首先求出s1的失配函数，然后在s2中 寻找s1字符串。在寻找字符串过程中，会有一个状态值...

算法题：HDU 3336 Count the string（经典，KMP+DP）

2017年02月05日 57 阅读

算法题：HDU 3336 Count the string（经典，KMP+DP）2014-03-17 csdn博客 shuangde800链接：http://acm.hdu.edu.cn/showproblem.php？pid=3336题目大意：给一个字符串，求出这个字符串的所有前缀出现的次数之和。分析与总结 ：运用到了dp的思想，dp弱逼一个表示压力很大。。。向这位博主大人学习了： http://www.cnblogs.com/yuelingzhi/ar...

算法题：poj 2541 Binary Witch（KMP水过，逆序转换）

2017年02月05日 56 阅读

算法题：poj 2541 Binary Witch（KMP水过，逆序转换）2014-03-17 csdn博客 shuangde800链接：http://poj.org/problem？id=2541分析与总结：做这题估算了下复杂度，觉得无论KMP再怎么快，这题暴力也肯定要超时的。想了很久也没想出个好办法，于是决定暴力之，但是TLE了....于是就放了几天。之后看了下discuss ，这题的正解应该是状态压缩dp，不过目前我还不懂，跪了。之后百度发现也可以用...

算法题：poj 2752 Seek the Name, Seek the Fame（理解KMP的失配函数！）

2017年02月05日 61 阅读

算法题：poj 2752 Seek the Name, Seek the Fame（理解KMP的失配函数！）2014-03-17 csdn博客 shuangde800链接：http://poj.org/problem？id=2752题目大意：给一个字符串S， 求出所有前缀pre，使得这个前缀也正好是S的后缀。 输出所有前缀的结束位置。例如 “ababcababababcabab”， 以下这些前缀也同时是S的后缀ab ： 位置2aba...

算法题：poj 3080 Blue Jeans（KMP匹配，枚举子串）

2017年02月05日 71 阅读

算法题：poj 3080 Blue Jeans（KMP匹配，枚举子串）2014-03-17 csdn博客 shuangde800链接：http://poj.org/problem？id=3080题目大意：给出m（2<=m<=10）个DNA序列， 求出这m个序列中最长的公共字串。如果有多个相同长度的， 输出字典序最小的。分析与总结:依次枚举所有的子串， 然后再看是否在所有序列中都能够匹配。保存下长度最大且字典序最小的序 列。代码：#include...