- 博客(48)
- 收藏
- 关注
RSS订阅原创 斐波那契递归与非递归
斐波那契:F(0) = 0;F(1) = 1;F(n) = F(n - 1) + F(n - 2); n >= 2递归:int Fib(int n) { if (n == 0 || n == 1) { return n; } else { return Fib(n - 1) + Fib(n - 2); }...
2018-12-24 12:11:48
397
原创 排序 - 直接插入排序，二分插入排序，运行时间对比
typedef struct 可以 换成 struct，试了下也对typedef struct { int key; char *otherinfo;} Node;//顺序表的存储结构typedef struct { Node *r; //存储空间的基地址 int length; //顺序表长度} SqList; //顺序表类型-----...
2018-12-02 20:38:41
634
原创 统计一串字符中每个字符的出现次数，以及哈夫曼树的WPL
WPL：weight path length 树的带权路径长度 #include <bits/stdc++.h>using namespace std;int main() { int arr[30]; memset(arr, 0, sizeof(arr)); string s; cin >> s; for (int i...
2018-11-04 13:54:58
6166
2
原创 二叉树
二叉树的简单操作://可以输入ABC##DE#G##F####include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX 20typedef struct BTNode{ /*节点结构声明*/ char data ; /*节点数据*/ ...
2018-10-23 19:54:43
213
原创 顺序表-队列
//循环队列的基本操作#include<stdio.h>#define MaxSize 50typedef int ElemType;//定义循环队列结构体typedef struct{ ElemType data[MaxSize]; int front,rear;}SqQueue;//初始化void InitQueue(SqQueue &Q){ Q...
2018-10-14 21:49:44
194
原创 链队
#include <iostream>#include <stdlib.h>#include<stdio.h>using namespace std;struct QNode //定义队列结点的数据结构{ QNode *next; //指针域,指向下一个结点 double data; //数据域，存储队列信息};struct ...
2018-10-10 22:35:59
215
原创 链栈
#include<bits/stdc++.h>using namespace std;struct sta{ int data; sta *next;};void sta_creat(sta *&s){ //构造栈 s = NULL;}void sta_push(sta *&s,int x){ //压栈 st...
2018-10-08 13:36:19
170
原创 链表的几个基础操作
#include <stdio.h>#include <stdlib.h>#include <iostream>typedef int ElemType;typedef struct Node { ElemType data; struct Node *next;}Node,*LinkedList;LinkedList Link...
2018-09-25 20:13:07
268
原创 数据结构上机: 实验1-线性表基本操作和简单程序
实验一 线性表基本操作和简单程序 1． 实验目的一、实验目的与基本要求掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。 掌握codeblock上机调试程序的基本方法及C语...
2018-09-25 17:17:43
4132
原创 实验2-约瑟夫环--(循环链表的应用)
维基百科: 约瑟夫环问题 实验一 循环链表的应用 一、实验目的与基本要求掌握数据结构中的循环链表的一些基本概念。二．实验内容认真阅读和掌握和本实验相关的教材内容及所给的程序代码。 通过循环链表实现约瑟夫环要求：1）要求设计一个程序模拟次过程，输入总的人数n，所报的出列的数字k，计数开始的位置p; 程序所能达到的功能：构造链表；输入数据；执行报数；储存出列人的...
2018-09-23 10:31:47
761
原创 Pseudoprime numbers 快速幂+伪素数
Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a(mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) n...
2018-09-06 09:19:48
229
原创 A and B and Compilation Errors STL- vector
A and B and Compilation Errors A和B正在准备即将到来的信息学全国联赛。 B非常喜欢写程序。写完程序以后，他必须先编译代码。 最初，编译器显示有Ñ个编译错误，其中每一个被表示为一个正整数。经过一番努力，B设法解决一个错误，然后又编译了下，又改正了一个错误。 B可以完全肯定，他纠正了两个错误，但他忘记了是哪几个编译错误消失了。 ...
2018-09-05 12:58:53
135
原创 不重复数字 STL map
不重复数字给出N个数，要求把其中重复的去掉，只保留第一次出现的数。例如，给出的数为1 2 18 3 3 19 2 3 6 5 4，其中2和3有重复，去除后的结果为1 2 18 3 19 6 5 4。 Input输入第一行为正整数T，表示有T组数据。接下来每组数据包括两行，第一行为正整数N，表示有N个数。第二行为要去重的N个正整数。 Output 对于每组数据...
2018-09-04 21:14:14
279
原创 神奇的字符串-包含26个字母
PG如果一个字符串包含了所有的字符（a到z，不区分大小写），那么我们就说这是一个神奇的字符串。现在，给你一个由大写和小写字母组成的字符串，判断其是否为神奇的字符串。Input第一行包含一个整数n（1≤n≤100）表示字符串的长度。第二行包含字符串，该字符串只包含大写和小写字母。Output如果是神奇的字符串，就输出YES，否则输出NO。Sample Input输...
2018-09-04 19:29:08
2497
原创 线段树入门
传送门1传送门2维基百科：线段树区间查询(0)定义： #define lson rt<<1#define rson rt<<1|1const int maxn=1e5+5;//元素总个数int sum[maxn<<2];//Sum求和，开四倍空间int a[maxn];//原数组下标[1,n](1)建树：#include...
2018-08-21 17:22:24
232
原创 数组去重 uniuqe 的使用
普通方法 :#include<bits/stdc++.h>using namespace std;const int maxn=1e5+5;int a[maxn];int b[maxn];int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++){ ...
2018-08-21 11:15:35
472
原创 质因数分解
#include<bits/stdc++.h>using namespace std;int main(){ int n; while(cin>>n){ for(int i=2;i<=(n+1)/2;i++){ while(n!=i){ if(n%i==0){ ...
2018-08-20 20:27:05
387
原创 字符匹配-kmp
B站的KMP算法讲解:视频1视频2视频中的代码#include <stdio.h>#include <string.h>#include <stdlib.h>#include <iostream>using namespace std;void prefix_table(char pattern[], int prefi...
2018-08-18 16:30:58
190
原创 字符串hash
Crazy Search 题目链接Many people like to solve hard puzzles some of which may lead them to madness. One such puzzle could be finding a hidden prime number in a given text. Such number could be the numb...
2018-08-17 16:56:08
226
原创 并查集，最小生成树 prim算法 kruskal算法
简单例题畅通工程-杭电1232某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目...
2018-08-15 15:47:23
431
1
原创 最短路径 dj 迪杰斯特拉dijkstra
DJ直接看题：Til the Cows Come HomeBessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her ...
2018-08-14 17:08:54
576
原创 矩阵取数问题
一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。例如：3 * 3的方格。 1 3 32 1 32 2 1 能够获得的最大价值为：11。Input第1行：N，N为矩阵的大小。(2 <= N <= 500)第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值...
2018-08-11 15:18:49
385
原创 括号配对问题
南阳oj题目链接描述现在，有一行括号序列，请你检查这行括号是否配对。输入第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[", "]", "(", ")" 四种字符输出每组输入数据的输出占一行，如果该字符串中所...
2018-08-10 20:40:05
2738
3
原创 记忆化搜索
杭电1078FatMouse and CheeseFatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 &l...
2018-08-10 11:33:55
276
原创 最长公共子序列 LCS （Longest Common Subsequence）
Common SubsequenceA subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2...
2018-08-09 15:10:07
279
原创 背包问题
简单的01背包 Bone Collector涂奥最近迷上了吃鸡，房间有n个配件，每个配件有c(c<=1e3)的重量和v(v<=1e3)的价值，哇，涂奥捡了一个2级包，容量为s，所以涂奥最多当多肥的快递员呢？Input输入的第一行是T, 表示有一共要打T场比赛.每组数据由三行组成.第1行包含两个整数n和s 第2行包含n个整数, 表示每一个配件的价值. 第3行...
2018-08-08 22:49:04
306
原创 动态规划(dynamic programming)的几道简单题
传送门一只小蜜蜂有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。其中，蜂房的结构如下所示。Input输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。Output对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占...
2018-08-07 17:32:30
353
原创 疯狂的母牛-母牛4年生仔
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？Input输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。n=0表示输入数据的结束，不做处理。Output对于每个测试实例，输出在第n年的时候母牛的数量。每个输出占一行。Sampl...
2018-08-07 10:16:18
642
原创 进制转换
#include<bits/stdc++.h>using namespace std;int main(){ int x; int a[100]; while(cin>>x){ memset(a,0,sizeof a); int k=0; while(x!=0){ a...
2018-08-05 22:36:36
269
原创 拓扑排序
from now on 输入输出改成c++的格式 2018年8月4日20:44:34对一个有向无环图可以进行拓扑排序，无向图和有环的有向图没有拓扑排序确定比赛名次HDU-1285有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛...
2018-08-04 15:49:49
197
原创 分治与归并
通过先递归的分解数列，再合并数列就完成了归并排序。 感觉归并排序的名字就是这么来的吧在归并排序的基础上再加上一行代码便可以捎带把逆序数求出来归并的含义是将两个以上的有序组合合成一个新的有序表。以下是2路归并排序：初始关键字：[3] [8] [2] [4] [1] [9] [6] [5]一趟归并后：[3 8] [2 4] [1 9] [5 6]二趟归并后：[2 3 4 8] [1 5...
2018-08-03 17:13:59
399
原创 汉诺塔 + 一道简单贪心题
汉诺塔移动n层塔至少需要多少次1层 1次2层 3次3层 7次4层 15次....没错,就是2n+1的规律int han(int n){ if(n==1) return 1; else return 2*han(n-1)+1;}3层汉诺塔GIF出来混迟早要还的o(╯□╰)o汉诺塔的变形 -...
2018-08-02 22:47:26
663
原创 DFS deep first search & BFS breadth first search
Red and Black HDU-1312There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four ad...
2018-08-01 12:27:12
288
原创 暑假第二次积分赛
Problem Description有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？ Input输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。 Output对于每个测试实例，请输出不同走法的数量 Sample In...
2018-07-30 16:28:03
129
原创 暂不分类的题目
娜塔莎Natasha上火星Natasha is going to fly to Mars. She needs to build a rocket, which consists of several stages in some order. Each of the stages is defined by a lowercase Latin letter. This way, the ro...
2018-07-28 21:50:51
191
原创 栈stack 和 队列queue
STL中，sort的默认排序为less，也就是说从小到大排序；priority_queue默认是less，也就说大顶堆；map默认是less，也就说用迭代器迭代的时候默认是小的排在前面；set默认是less，也就是说用迭代器迭代的时候是从小到大排序的。 栈和队列的区别是啥? 吃多了拉就是队列，吃多了吐就是栈栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插...
2018-07-27 09:10:06
278
原创 算数基本定理+容斥原理(的应用)
算术基本定理（唯一分解定理）一句话： 任何大于１的自然数，都可以唯一分解成有限个质数的乘积一、求一个数有几个因子。比如求9有3个因子,就是1、3、9, 原因是1*9=9 3*3=9这种方法一般都会超时C语言的代码如下：//求一个数有几个因子#include<stdio.h>#include<math.h>int num(int n)...
2018-07-25 15:00:26
255
原创 【没见过的科技】
int &b=a;//声明b是整型变量a的别名 其实就是一块内存起了两个名,改变其中的一个,另一个也会改变的 清空数组有两种方法可以实现。为方便说明，定义整型数组a，并实现将a清空。int a[4] = {1,2,3,4};1、 通过数组遍历，逐个赋值为0。定义循环变量int i;for(i = 0; i < 4; i ++)a[i]=0;该程序功能为...
2018-07-24 21:02:23
224
原创 同余定理,逆元,费马小定理求逆元
逆元 Inverse element1.什么是逆元当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：设c是b的逆元，则有b*c≡1(mod m)；//(b*c-1)%9973=0 ,我们称 c 是 b 关于 m 的...
2018-07-24 15:59:30
437
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人