- 博客(51)
- 收藏
- 关注
RSS订阅原创 P1305 新二叉树
题目描述输入一串二叉树，用遍历前序打出。输入输出格式输入格式： 第一行为二叉树的节点数n。(n \leq 26n≤26)后面n行，每一个字母为节点，后两个字母分别为其左右儿子。空节点用*表示 输出格式： 前序排列的二叉树 输入输出样例输入样例#1： 复制6abcbdicj*d**i**j**输出样例#1： 复制ab...
2018-11-19 22:46:56
320
原创 P1087 FBI树
我们可以把由“00”和“11”组成的字符串分为三类：全“00”串称为BB串，全“11”串称为I串，既含“00”又含“11”的串则称为F串。FBIFBI树是一种二叉树，它的结点类型也包括FF结点，BB结点和I结点三种。由一个长度为2^N2N的“0101”串S可以构造出一棵FBIFBI树TT，递归的构造方法如下：1) TT的根结点为RR，其类型与串SS的类型相同；2) 若串SS的长度大于1...
2018-11-19 21:42:44
280
原创 P1030 求先序排列 #substr的用法
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度\le 8≤8）。输入输出格式输入格式： 22行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。 输出格式： 11行，表示一棵二叉树的先序。 输入输出样例输入样例#1： 复制BADCBDCA输出样例#1： 复制ABCD方法：模板...
2018-11-13 22:55:47
174
原创 delete p和delete[] p的区别
#include<bits/stdc++.h> using namespace std;class T {public: T() { cout << "constructor" << endl; } ~T() { cout << "destructor" << endl; }};int
2018-11-12 14:38:17
503
原创 归并排序(求逆序对)
https://blog.csdn.net/yuehailin/article/details/68961304#include<bits/stdc++.h>using namespace std;void merge(int a[],int first,int mid,int last,int temp[]){ int i=first,j=mid+1; int m=m...
2018-11-12 14:36:25
191
原创 P1010 幂次方（分治）
任何一个正整数都可以用22的幂次方表示。例如137=2^7+2^3+2^0137=27+23+20同时约定方次用括号来表示，即a^bab 可表示为a(b)a(b)。由此可知，137137可表示为：2(7)+2(3)+2(0)2(7)+2(3)+2(0)进一步：7= 2^2+2+2^07=22+2+20(2^1用2表示)，并且3=2+2^03=2+20所以最后1371...
2018-11-11 22:41:32
253
原创 哈夫曼树的实现
#include<bits/stdc++.h>using namespace std;typedef struct{ unsigned int weight; //用来存储各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈...
2018-11-04 20:12:03
188
原创 全排列 next_permutation() 函数的用法 全排列
#include <stdio.h>#include <algorithm>using namespace std;int main(){ int n; while(scanf("%d",&n)&&n){ int a[1000]; for(int i=0;i<n;i++){ ...
2018-10-16 22:27:54
199
原创 洛谷P1219 八皇后
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：行号 1 2 3 4 5 6列号 2 4 6 1 3 5这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的...
2018-10-16 21:53:47
124
原创 DFS板子（模板）
#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;const int maxn=100;bool vst[maxn][maxn]; // 访问标记int map[maxn][maxn]; // 坐标范围int dir[4][2]= {0,1,0,-1,1,0...
2018-10-16 20:51:00
702
原创 Manacher算法求出其最长回文子串（模板）
给定一个字符串，求出其最长回文子串。例如：s="abcd"，最长回文长度为 1； s="ababa"，最长回文长度为 5； s="abccb"，最长回文长度为 4，即bccb。来源：https://segmentfault.com/a/1190000008484167#include <iostream> #include <cstring>#incl...
2018-10-09 22:50:50
141
原创 静态邻接表
#include <iostream> #include <queue> using namespace std; const long edge_maxn = 1005; //边的最大上限 const long point_maxn = 105; //点的最大上限 struct node {/*node存储边，一个edge代表一条边*/ ...
2018-09-11 21:18:10
215
原创 有向图最短路径板子（spfa+dijkstra）
题目背景本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。题目描述如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。输入输出格式输入格式： 第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。...
2018-09-11 21:13:42
541
原创 线性筛法板子（较快速度）
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int n,m;bool su(int a){ if(a==1) return 0; if(a==2||a==3) return 1; i...
2018-09-11 19:47:16
331
原创 最小生成树板子
题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz输入输出格式输入格式： 第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi 输出格式： 输出包含一个数，即最小生成树的各边的长度之和；如...
2018-09-11 18:46:22
353
原创 线性基 xor序列
链接：https://www.nowcoder.com/acm/contest/180/D来源：牛客网 题目描述小a有n个数，他提出了一个很有意思的问题：他想知道对于任意的x, y，能否将x与这n个数中的任意多个数异或任意多次后变为y 输入描述:第一行为一个整数n，表示元素个数第二行一行包含n个整数，分别代表序列中的元素第三行为一个整数Q，表示询问次数接下来Q行，每...
2018-09-09 13:52:31
137
原创 烟花（滚动数组，期望，概率计算）
链接：https://www.nowcoder.com/acm/contest/180/B来源：牛客网 题目描述小a有个烟花，每个烟花代表着互不相同的颜色，对于第个烟花，它有的概率点燃，现在小a要去点燃它们，他想知道产生颜色的期望个数 及 产生恰好产生种颜色的概率 输入描述:第一行两个整数接下来一行个数，第个数表示第个烟花被点燃的概率输出描述:输出有两行第...
2018-09-08 21:24:00
321
原创 路径数量
链接：https://www.nowcoder.com/acm/contest/185/B来源：牛客网 题目描述给出一个 n * n 的邻接矩阵A.A是一个01矩阵 .A[i][j]=1表示i号点和j号点之间有长度为1的边直接相连.求出从 1 号点 到 n 号点长度为k的路径的数目.输入描述:第1行两个数n,k (20 ≤n ≤ 30,1 ≤ k ≤ 10)第2...
2018-09-08 20:51:59
1238
原创 打表好题
链接：https://www.nowcoder.com/acm/contest/185/F来源：牛客网 输入一个整数X，求一个整数N，使得N!恰好大于XX。 输入描述:第一行：一个整数X输出描述:第一行：一个整数N示例1输入复制7输出复制10备注:每个测试点所对应的X满足：第i个测试点输入的值为第i-1个测试点输入的...
2018-09-08 20:39:28
380
原创 括号匹配（思维）
链接：https://www.nowcoder.com/acm/contest/185/E来源：牛客网 给定括号长度N，给出一串括号（只包含小括号），计算出最少的交换（两两交换）次数，使整个括号序列匹配。我们认为一个括号匹配，即对任意一个')'，在其左侧都有一个'('与它匹配，且他们形成一一映射关系。输入描述:第一行：整数N，表示括号序列长度第二行：一个字符串，表示括号输...
2018-09-08 20:26:15
541
原创 LUOGU1316 丢瓶盖
思考： 和奶牛那道题是类似的，学到了，二分法的模板如下：void search(){ r=a[n]-a[1]; while(l<=r){ mid=(l+r)/2; if(judge(mid))l=mid+1; else r=mid-1; }}题解： #include<bits/stdc++.h&...
2018-09-06 17:46:43
129
原创 P1824 进击的奶牛 （二分）
像这种求最大最小值，最小最大值得问题都是典型的二分答案题，二分答案的主要难点在于juge（）函数，此题下面给出了两个不同思路的juge函数。要注意的是如何根据所枚举的答案来将隔间分隔，因为求的是最大的最近距离，这个距离要是每一次分隔距离中最短的。接下来分析，假设隔间的坐标没有规定在哪的话，那么什么时候最近距离最大呢？毫无疑问，是当所有的距离相同的时候，最近距离最大。但是此题每个隔间的坐标有...
2018-09-06 17:12:21
279
原创 DFS 找环
解释： 找环的过程 就是对其中的每一个点进行一次DFS，DFS的过程就是用一个ans记录成环的个数，到最后肯定是DFS到了这个点周围的一个点，故这个ans是先++的，跳出条件就是判断是这周围的四个点之一，代码如下#include<cstdio>#include<cstring>#include<algorithm>#include<iost...
2018-08-30 21:14:40
2718
原创 待补
#include<bits/stdc++.h>using namespace std;typedef long long LL;map <LL , int> mp;int main(){ int T; scanf("%d",&T); while(T--){ int n , res = 0; LL sum = 0 , num; ...
2018-08-30 20:42:47
111
原创 第一次组队赛 求无向图路径数目
#include <cstdio>#include <algorithm>#include <vector>#include <cmath>#include <cstring>using namespace std;const int MAXN = 200010;const int mod = 1e9 + 7;vecto...
2018-08-30 19:46:55
329
原创 第一次组队赛
B题目描述你有n个问题，你已经估计了第i个问题的难度为Ci,现在你想使用这些问题去构造一个问题集。比赛的问题集必须包含至少两个问题，而且比赛的总难度必须至少为l至多为r,此外最简单的问题和最难的问题之间的差异至少为x请您找出能够选择的问题集的数量。输入第一行有T组输入（1 ≤ T ≤ 10接下来一行输入n, l, r, x (1 ≤ n ≤ 10, 1 ≤ l ≤ r ≤ 1e9...
2018-08-30 18:21:11
183
原创 P1023 税收与补贴问题
题目背景每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数）对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）...
2018-08-25 16:28:05
413
原创 poj 3468 区间更新区间求和板子 *
题目：http://poj.org/problem?id=3468成段更新线段树。用mark延迟标记，在更新的时候不用每次把叶子节点全部更新，只需要把需要更新的一段所需要更新的权值标记一下，然后在下次查询的时候。如果需要更新这个被标记的子节点。那么把这个子节点的儿子节点的延迟mark加上父亲节点的mark#include<cstdio>using name...
2018-08-22 21:01:38
107
原创 HDU1166:敌兵布阵(线段树单点更新)(树状数组)
Input第一行一个整数T，表示有T组数据。 每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。 接下来每行有一条命令，命令有4种形式： (1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30） (2)Sub i j ,i和j为...
2018-08-22 21:00:00
108
原创 初学KMP ->HDU1711
题意： 给你两个数组，求子数组在木数组出现的位置Sample Input213 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 1 313 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 2 1Sample Output6-1#include<iostream>#include<algorithm>...
2018-08-18 18:03:50
198
原创 POJ-1200 Crazy Search
Crazy Search题目大意就是将一个字符串分成长度为N的字串。且不同的字符不会超过NC个。问总共有多少个不同的子串?采用的办法就是以nc作为进制，把一个子串化为这个进制下的数，再用哈希判断。由于题目说长度不会超过16，000，000...
2018-08-17 15:32:22
186
原创 第四次积分训练赛
A BallDescription 给a个黑球和b个白球，这些球除了颜色外没有别的不同，现随机的摸c个球，问至少有一个黑球的概率是多少？Input 第一行,一个整数T表示测试组数( 0 < T \leq 1000<T≤100).接下来T行，每行有三个用空格隔开的整数a,b,ca,b,c . (0 < a + b < 1e9, 0 < c ...
2018-08-15 20:03:08
361
原创 hdu 1087 Super Jumping! Jumping! Jumping!（动态规划DP）
题目大意：求解最大递增子序列和，这里要特别注意一点：这个题目不要求是连续的最大递增子序列。但是一定要注意是递增的！！题目思路：dp数组表示是包含当前这个数的最大递增子序列和。dp[i]表示的是前i个并且包含第i个的最大递增子序列和！给个数据：3 1 4 显然dp[1]=3,dp[2]=1表示两个数的最大值。因为分两种情况讨论，如果第二个数大于第一个数，就加上，即dp[2]=dp[1]+num[...
2018-08-12 11:03:58
165
原创 RMQ
RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干次询问RMQ(i,j)，返回数列A中下标在区间[i,j]中的最小/大值。本文介绍一种比较高效的ST算法解决这个问题。ST（Sparse Table）算法可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。 1）预处理设A[i]...
2018-08-11 15:40:18
160
转载 Anniversary party (hdu1520) (树状数组)
题意：有n个人，他们之间有上司和下属关系，每个人有自己的价值，现在要选一部分人使其满足上司和下属不同时被选到的情况下价值总和最大。更直接的讲就是，在一棵树中选价值总和尽量多的节点但是不能同时选到一个节点和它的直接父节点。题解：因为这里要求选的点的个数是不限定的，只需要满足价值总和尽量大。而对于每个点来说，只有选和不选两种状态，这种情况其实和01背包有一些类似，所以我们可以用背包的思想来做。...
2018-08-10 20:40:58
119
原创 杭电1203--I NEED A OFFER! 01背包
Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之...
2018-08-09 21:09:30
277
转载 hdu 1284 钱币兑换问题(动态规划)
完全背包：#include<stdio.h>#include<string.h>int dp[4][40000];int main(void){ int i,j,n; memset(dp,0,sizeof(dp)); dp[0][0]=1; for(i=1; i<=3; i++) { for(j...
2018-08-07 20:31:30
205
转载 hdu 2647 Reward【拓扑排序】
题目大意：给你n个人，m个关系，表示a比b的奖金要多。问最少分配的奖金总数是多少。思路：假如有这样一个图：（ 箭头表示1比2奖金要多，1比5奖金要多） 不难看出，标号3的那层都是888的奖金，标号2的那层都是889的奖金，标号1的那成是890的奖金，如果我们想要确定每个点权值的话，我们需要知道各个节点之间的全序关系，也就不难想到使用拓扑排序来做这个题，直接能够想到的方法就是直接拆点...
2018-08-04 20:37:01
100
原创 第二次积分赛
A 斐波那契数列在存到i=50的时候就爆炸了，没有数组能够存下，虽然会溢出，但是可以比较后边的几位，故都设置为ull类型，遍历一下也就1e5，记得输入用字符串，数据和位置的对应可以用map《数组，int》。#include<bits/stdc++.h>using namespace std; typedef long long ll;typedef unsigne...
2018-08-03 20:44:36
216
转载 BFS经典例题—迷宫问题POJ - 3984
Description定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0,};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。...
2018-08-02 15:57:30
984
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人