- 博客(123)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 人生中第一篇论文，虽然是二作，也记录一下
人生中的第一篇论文是关于信息加密的，二作，在大学时完成的，不是水过去的哦，自己付出了很大努力滴虽然和研究生方面的研究工作方向不同，但是也很开心，在此感谢一作的师姐带我飞。论文传送门：点击打开链接
2016-01-24 18:46:00
2051
原创 opencv小练习：哈尔小波(Haar)
首先说一下一维haar小波的原理。 例如我们有一个一维的图像[2,4,6,8,10,12,14,16].求均值：我们求相邻像素的均值[3,7,11,15]。这个新的图像分辨率就成了原来的一半(8/2=4)。求差值。上面的均值我们存储了图像的整体信息。但是很多细节信息我们丢掉了，所以我们同时要记录图像的细节信息，这样在重构时能够恢复图像的全部信息。下面是求第m个差值的公式：b[m]=(a[2m]
2016-01-10 20:22:36
27425
14
原创 九度 1140 - 回溯 - 八皇后
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉x=row(在纵向不能有两个皇后)y=col（横向）col + row = y+x;（斜向正方向） col - row
2015-08-25 20:31:03
911
原创 九度 1138 - 大数除余 - 进制转换
其实基本的十进制转二进制方法我们都知道，就是循环模2，除2这两个过程。下面是一个大概的方法代码。while(n>0){ binary[count++] = n%2; n = n/2;}这道题目就是把除和余的过程变成了大数上的除余。这里我从网上找到了一个博主的博客点击打开链接，他的大数除余写的很简洁，也算学习借鉴了。这个博主大数的其他算法写的也很不错。#include#inclu
2015-08-24 15:29:30
1037
原创 九度 1105 - 字符串处理 - 字符串的反码
这道题目最大的难度（我觉得题目本身也没说清楚....）就是输入的字符串会有空格，所以我们不能用scanf和cin，而是改用gets和puts。gets可以接受空格，而scanf不能。用这道题目记录一下。#include#includechar a[100];int main(){ int i; while( gets(a)){ if(strcmp(a,"!")==0)
2015-08-23 10:03:41
1389
原创 九度 1101 - 字符串处理 - 计算表达式
根据我的通过来看，首先这道题里面没有小数，如果存在除不尽的情况，也是按取整来算。本题建立了两个栈，一个存储数字的数字栈，一个存储加减乘除的符号栈。在处理字符串的时候，每次找到一个数字时，放进一个string的临时变量里，因为会存在十位以上的情况；每次找到一个符号时，首先将string变量转int放入数字栈，然后检查符号栈的栈顶符号是否为乘或者除，如果是就从符号栈弹出顶，从数字栈弹出两个数，计算
2015-08-20 18:12:37
1051
原创 九度 1107 - 霍夫曼树 - 搬水果
这道题目一开始我用排序来做，每次选择最小的两个，相当于构建了霍夫曼树，最后统计所有非叶子结点之和。但是因为每次排序的基数太大，所以会一直超时。所以我们用优先队列模拟一个堆，利用最小堆的特征来快速得到最小的两个数。STL带有优先队列-priority_queue。priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数:priority_queue
2015-08-20 16:23:09
877
原创 九度 1201 -二叉排序数遍历- 二叉排序树
这个是道正统的树构建和遍历题，一开始还想用数组构建代替一下水过去，但是发现不行，只好老老实实的用指针了。二叉排序树和遍历方法如果不清楚定义的话，最好去看看数据结构书复习下。#includestruct node{ node *l; node *r; int val; node(int a):val(a),l(NULL),r(NULL){};};node
2015-06-26 21:15:55
996
原创 九度 1411 -图最短路径 - 转圈
这道题目检查对于dijkstra算法的掌握，如果对于这个算法有疑问的，可以看看这个博客点击打开链接，基本上已经讲得很清楚了。这道题目的细节有:1：在给的有向图中，一条边会重复，所以我们要选最小的那条覆盖 2:有s-s的边。大家做的时候要小心这两个细节。dijkstra算法代码整体模板就是这个博客点击打开链接的。#include#include#define MAX 100000
2015-06-26 15:21:29
833
原创 九度 1341 -图最短路径 - 艾薇儿的演唱会
这道题目检查对于dijkstra算法的掌握，如果对于这个算法有疑问的，可以看看这个博客点击打开链接，基本上已经讲得很清楚了。其实这种题目最难的不是这个算法，而是一些小细节。他的提示里有说：火车能从城市x到城市y，就能从城市y到城市x，并且同一列火车来回所花费的时间是一样的。如果在x和y之间有不止一辆火车通行，则不同火车从x到y或者从y到x所花费的时间可能不相同。 说明一个路线可能会出现两次
2015-06-26 15:12:41
960
原创 九度1475 - IP数据包解析（北邮）
这题目就是一个处理字符串的简单题目，但是一开始我没有用到IHL，还是考验了一些计网的知识的。我看到有一个人写的很简洁，所以贴他的代码，给大家看看。#include#includeint num(char *c){ // 字符转换为数字 if(*c>='0'&&*c<='9') return *c-'0'; else return *c-'a'+
2015-06-20 18:15:11
1025
原创 九度1027 - 数学 - 欧拉回路
欧拉回路是指每条边恰好只走一次，并能回到出发点的路径。我们如何判断一个图有欧拉回路？一、无向图每个顶点的度数都是偶数，则存在欧拉回路。二、有向图（所有边都是单向的）每个节顶点的入度都等于出度，则存在欧拉回路。知道了这些，我们只要判断每个边的度数即可。#include#includeint du[1010];int main(){ int m,n,x,
2015-06-20 16:48:18
1230
原创 九度1029 -map - 魔咒词典
这个题目就是为了练习map，因为有可能从key查找value，由value查找key两个情况，所以需要两个map，因为map只能从key查找value。同时也考验了字符串的处理。#include#include#include#includeusing namespace std; int main(){ mapmaps; mapmaps1; m
2015-06-18 20:11:36
969
原创 九度1022 -栈 - 游船出租
这题目我想到的是栈，当然感觉也是想多了，，#include#include#includeusing namespace std;double round(double r){ return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);}stackdata[100];int sum;int num;int pre;void
2015-06-18 18:09:42
759
原创 九度1035 -树 - 找出直系亲属
这道题目一开始我还以为是并查集，后来发现比并查集简单的多，就是一个家谱树，然后找到两个节点之间的深度差。#includeint data[30]; void make_set(){ for(int i=0;i<30;i++) data[i]=-1;} int find(int a,int b){ int re=1; while(data[
2015-06-18 11:59:48
2114
1
原创 各种排序代码集合笔记
#include//直接插入排序void InsertSort(int *datatemp,int n){ int *data = new int[n]; for(int i=0;i<n;i++){ data[i]=datatemp[i]; } int temp,j; for(int i=2;i<n;i++){ temp = data[i]; if(data[i]<da
2015-06-10 20:38:24
712
原创 HDU 丑数 - 1058 Humble Numbers
这一题是讲了一个名叫丑数的概念（为啥叫丑数，，）。概念：因子中仅仅包含2、3、5，7的数，称为丑数。但其实我百度网上时，发现正常的丑数应该是因子中仅仅包含2、3、5，不过基本都一样。我们可以通过不断mod2,3,5,7，直到无法在摸，验证此时是否为1来判断该数是否为丑数，但是这样的方法太过浪费时间，所以介绍一种新的方法，下面方法摘自这里点击打开链接。根据丑数的定义，丑数应该是另
2015-06-10 20:06:12
1380
原创 人脸识别算法-特征脸方法（Eigenface）及python实现
这几天无聊，正好想起来以前谁说有同学做人脸识别，感觉好高大上，所以找来一些基础的人脸识别算法来自己实现一下，正好锻炼一下numpy的使用。特征脸方法基本是将人脸识别推向真正可用的第一种方法，了解一下还是很有必要的。特征脸用到的理论基础PCA我在这里就不说了，百度一大堆，主要讲一下实现步骤和自己在用python实现是发现的问题。这里我所使用的训练图片是YALE的人脸数据库点击打开链接，这里面有1
2015-06-08 20:15:20
36904
25
原创 人脸识别算法-LBP算法及python实现
上一次我们说了人脸识别算法-特征脸方法（Eigenface）及python实现，在这一次，我们来看一看LBP算法。相比于特征脸方法，LBP的识别率已经有了很大的提升。在这里，我们用的数据库和上次一样，都是UCI的YALE的人脸数据库。因为我也是一边学一边写代码，所以害怕有人说我博文是抄袭的，所以在这里说明，我这里的算法思想主要是来自点击打开链接（不过大家都是学习，应该不会这么计较吧），我主
2015-06-08 20:12:40
30116
12
原创 HDU DP - 1024 Max Sum Plus Plus
给出n个数，求其m个子段和的最大值。原始状态转移方程：dp[i][j]=max(dp[i][j-1]+a[j]，dp[i-1][k]+a[j]) (i-1第1种情况是直接将第j个元素加在第i个子段之后，第2种情况是将第j个元素单独作为一个子段，那么前面必须是i-1个子段。但是因为二维数组太大，而且三层循环时间过长，所以我们要进行优化，优化方法借鉴
2015-05-29 14:19:38
567
原创 HDU 大数加 - 1250 Hat's Fibonacci
一个新的斐波那契数列，F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)没什么可说的，大数加上，注意为了节省空间，我们使用滚动数组，一开始我还以为能一开始算出所有可能来节省时间，后来发现空间真是hold不住啊。。#include#include#define MAX 20
2015-05-22 20:17:42
470
原创 HDU 并查集 - 3172 Virtual Friends
并查集题目，并的意思就是将两个不同类别的集合合并到一起，类似于两棵树合并；查的意思就是找到这个点所属集合的根节点。基本上并查集题目都是在大体架构上面加一些东西即可。并查集代码模板在这里点击打开链接。这一题为了找到输入的两个人组成的社交网络人数，也就是统计这两个人与前面的人组成的集合中有多少元素。我们加一个辅助数组sum，当两个集合并时，我们将父节点对应下标的sum值加上子节点的sum值，表达这
2015-05-22 19:05:21
526
原创 HDU 大数乘 - 1042 N!
这道题目训练的就是大数乘法。下面是从一位博主那摘抄而来。其核心思想就是把计算结果每一位上的数字保存到一个数组成员中，例如：把124保存至数组中，保存结果应该是result[0] =4；result[1] =2；result[2] =1把整个数组看成一个数字，这个数字和一个数相乘的时候，需要每一位都和这个乘数进行相乘运算还需要把前一位的进位加上。写法如下：int 结果 =
2015-05-22 15:06:44
693
原创 最小生成树 - Prim 和Kruskal
最近有些忙，先把最小生成树的代码挂上，有时间将讲解补上。在这里两个函数：Prim和Kruskal函数，分别是这两个算法的主算法代码。使用的图存储方式是邻接矩阵。#include#include#includeusing namespace std;#define MAX 100#define INT_MAX 10000#define min(x,y)(x<y?x:y)typ
2015-05-18 16:13:07
669
原创 最短路径 - Dijkstra和Floyd
今天来看看图的最短路径。最短路径在许多方面都有广泛的应用，最短路径中的路径一般不再是路径上边的数目，而是路径边上的权值之和。所以最短路径都是用在带权有向图上面的。在最短路径方面，有两个著名的算法，Dijkstra算法和Floyd算法。1.Dijkstra算法-从某个点到其余各点的最短路径Dijkstra算法使用了贪心算法思想，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。但是注意该算法要
2015-05-13 15:05:41
1980
原创 图的遍历-深搜(DFS)和广搜(BFS)
最近为了保研在复习数据结构和算法，想来可以用博客记录一些，以后或许能用的上。首先说一下图的定义。 图是一种数据结构，图和树一样可以用二元组表示。它可定义为Graph=(V,R)其中，V＝{x|x∈datatype},R={VR}，VR={(x,y)|P(x,y)∧（x,y∈V）}。在图中，数据元素常称为顶点（Vertex），V是顶点的非空有穷集合；R是边（弧）的有穷集合。也就是说，图就是记录一
2015-05-12 19:07:42
9359
原创 poj 杂题 - 2081 Recaman's Sequence
这道题目一开始就能知道考点在如何缩短查找时间。所以加快查找是我们的重点。但是在大数据面前，查找算法都不够快，所以我们用简单的hash思想来做。我们开一个数组a，当出现了一个数b时，把该数作为下标调整值，即a[b] = -1，下一次出现该值的时候直接去找这个值作为下标的a值是否为-1即可。#include#include#define MAX 5000010int p[MAX]={0}
2015-05-11 15:38:38
717
原创 poj 大数 - 2602 Superlong sums
这应该算是最简单的大数题了。。。目的就是为了让你知道char的输入输出比int快很多，还学会了getchar()，putchar()。#include#define MAX 1000002char num[MAX],num1[MAX];int main(){ int n,i; scanf("%d",&n); getchar(); for(i=1;i<=n;i++){ num
2015-05-09 10:45:12
913
1
原创 poj 杂题 - 2231 Moo Volume
一开始以为是long long输入，后来发现用int就行，，，反正也是一个挺简单的题目，直接贴代码了。#include#includeint cows[10005]={0};int main(){ int n,i,j; long long res = 0,temp; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&cows[i
2015-05-09 09:34:19
854
原创 poj 动态规划DP - 2392 Space Elevator
背包九讲里面的多重背包问题。每一块积木有高度和数量，也有最大能到的高度位置限制。我们DP前首先要对高度限制进行排序，因为从直观角度说，我们也需要先处理较小的能到高度的积木，这样才能取到最大值。例如第一个高度是11，限制高度是100，第二个的限制高度是10，那如果直接处理，第二个不会被处理到。#include#include#include#define max(x,y)(x>y?x:y
2015-05-08 09:59:46
624
原创 poj 杂题 - 1147 Binary codes
N位的二进制串连续N次循环移位，得到N个二进制串。对其按照字典序排列，得到一个N*N的矩阵。告诉矩阵最后一列，求矩阵第一行。拿这个题目例子讲解吧。0 0 0 1 10 0 1 1 00 1 1 0 01 0 0 0 11 1 0 0 0我们看到最后一列是10010，因为是按照字典序排列，也就是0在1前面，那这个每一行的第一个数字肯定是从0到1的，因为是最高位嘛，所以我们将最
2015-05-06 18:56:11
669
原创 poj 动态规划DP - 2063 Investment
富二代继承遗产不知道怎么花问题，就是一个完全背包问题。虽然每一年的起始金额不同，但是内容都是一样的，就是在n种债券中随意选择，注意因为为了简化计算和开辟空间，而且题目告诉我们了债券金额是1000倍数，所以我们将金额除1000，每次处理前起始钱数都除1000.完全背包问题：把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^kO(VN)的算
2015-05-05 21:27:39
658
原创 poj 动态规划DP - 2018 Best Cow Fences
这道题目我一开始的思路是用二维DP，结果TLE了。后来换了个思路，终于AC了。不需要判断所有的情况，我们用dp[i]表示前i个牛圈中最大的牛数，而这个i首先必须>=限制的牛圈树f。用num[i]表示dp[i]中包含了多少牛圈。我们可以知道，dp[i] = sum[i] - sum[i-f])/f or dp[i-1] + data[i]， 前一个代表到i为止前f个牛圈的牛数，后一个代表
2015-05-05 16:22:36
952
原创 poj 杂题 - 1013 Counterfeit Dollar
判断硬币题。这道题目没咋知道怎么做，看了其他人的discuss才有了思路。一，EVEN时，两边都是真币二，非EVEN时，没上天平的都是真币三，曾经被认为可能偏重，又出现在偏轻的一方的是真币。我们可以用一个数组zeros存储一定是真币，即出现在even情况内的那些；另一个数组sus存储对可能是假币的怀疑情况，当出现在up时，左边的硬币sus--，右边的++。down时反过来，这样
2015-05-04 20:50:52
659
原创 poj 杂题 - 1959 Darts
这一题放在杂题里，是因为我没有用DP，而是使用的枚举，当然是受到了discuss里面的启发。因为我们只能有三次机会，每一次只可以是固定的63个数，所以枚举感觉更加直观，但是不知道是不是没有DP快。#include#includeint n;int Darts[63];int main(){ int t,c=1,i,j,k,res; scanf("%d",&t); for(i
2015-05-04 18:37:45
831
原创 poj 动态规划DP - 1953 World Cup Noise
这一题其实就是斐波那契数列，但是我一开始用的是DP，不过应该思想差不多。一数组dp[i][2],dp[i][0]代表前i个数里面最后一个数字为0的数量，dp[i][1]代表前i个数里面最后一个数字为1的数量，可知dp[i][1]+dp[i][0]就是前i个数能组成序列的数量。这里因为不能2个1在一起，所以：dp[i][0] = dp[i-1][0]+dp[i-1][1]dp[i][
2015-05-04 15:23:49
781
原创 poj 动态规划DP - 1664 BUY LOW, BUY LOWER
最大下降子序列，变相的最大上升子序列题目。主要是多了一个判断最大序列的个数。一般递推式是dp[x] = max(dp[x],dp[y]+1），这里多了一个count用来计算序列个数。在内部循环剩下的序列时，我们从尾向头部循环，因为显然，目前最大的下降子序列一般在后面，这样的话，我们能迅速找到最大子序列，并且往前找与这个序列长度相同的结点，计算序列个数。# include#include
2015-05-04 14:12:41
624
原创 poj 杂题 - 1083 Moving Tables
这道题最主要的是看懂题目即可。我们需要算出搬动桌子的最短时间，根据这个图可以知道不同房间占用同一走廊。这道题里1-4，2 -3显然占用同一走廊，但是2-3 和 4-5也占用了房间4和房间3的那个走廊，所以注意这个数据的最短时间是20，不是10。搞清楚这个就好做了，我们可以将房间偶数/2，奇数/2+1，这样2-3变成了1-2,4-5变成了2-3，自然占用了走廊。#include#i
2015-05-03 10:27:02
698
原创 poj 模拟 - 1690 (Your)((Term)((Project)))
这一题主要是需要考虑的情况考虑到了即可，我们需要去掉对这个式子无用的括号。把每对括号，满足以下任意一个条件的就可以去掉：1，最外面的括号2，前面不是 减号 的括号3，前面是减号，但左右括号之间仅有变量，而没有 加减号 的括号。我利用栈和数组存储了右括号对应左括号的下标，大家也可以试试其他方法。这里给一个测试数据。5(A-B + C) -
2015-05-02 13:27:35
526
原创 poj 动态规划DP - 1664 放苹果
dp[m][n]表示m个苹果放n个盘子里面.此问题可分为两个子问题：当m所以m当m>=n时，可分为两种放法，一种为至少有一个盘子为空，则有dp[m][n-1]种放法。另外为n个盘子都不为空，则先将n个苹果一个一个放入n的盘子中，剩下的m-n个苹果再放入n个盘子中。此放法就相当于m-n个苹果放n个盘子里面,有dp[m-n][n]种放法。所以状态转移方程为dp[i][j]:if(i
2015-04-30 19:41:51
1457
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人