- 博客(33)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 PAT-A 1146 Topological Order
PAT-A 1146 Topological Order判断一个序列是不是给定的有向无环图所生成的一个拓扑序列，将给定的序列从前开始遍历，当一个点为正确的拓扑序列时，遍历到他时度应该为0，然后再将它所连边度数减一。#include<bits/stdc++.h>#define maxn 4000using namespace std;int n,m;vector<int...
2019-11-20 16:59:09
172
原创 PAT-A 1147 Heaps
PAT-A 1147 Heaps输入一个堆的层序序列判断它是不是一个最大（最小）堆。众所周知，堆是个完全二叉树，它在顺序存储的时候储存序列即是层序序列。所以，在遍历的时候判断一下即可，#include<bits/stdc++.h>using namespace std;int a[2000];bool f;int sum;int t,n;void print(int...
2019-11-17 08:42:37
128
原创 PAT-A 1135 Is It A Red-Black Tree
PAT-A 1135输入数据判断是否为一棵红黑树，数据为正表示节点颜色为红，负为黑。一个小结论——一颗二叉搜索树的前序遍历顺序即是他的节点插入顺序（虽然很显然所以只需要建好树遍历判断即可判断依据：1.根节点为黑色（首先判断一下就行）。2.每个红节点的儿子都是黑的。3.从根节点到每一个叶子经过的黑节点个数相同。通过DFS遍历一遍树即可得到结果。#include<bits/s...
2019-11-17 00:19:07
122
原创 Happy第四周题解
6-1void proceed(int *a, int *b, int size, void (*fp)(int x, int y)){ for(int i=0; i<size; i++) (*fp)(*(a+i),*(b+i));}6-2void tian(int (*p)[n]) { for(int i=0;i<n;i++) { for(int ...
2019-11-07 21:49:08
682
原创 Tire树(模板)
HDU1251在HDU上交g++超内存c++就没事，，，咱也不知道为什么，咱也不敢问#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;struct tire{ int n; tire *next[26];...
2019-11-01 23:36:40
98
原创 二叉树的重建
所谓二叉树的重建就是已知前序或后序和中序遍历（必须确定中序遍历否则不能确定唯一二叉树）得到原二叉树。例：71 2 3 4 5 6 7（中序遍历）4 1 3 2 6 5 7（前序遍历）前序遍历必然是从根节点先走左子树再走右子树，这一点和递归顺序相同，所以在每一次递归的时候可以根据本子树的根节点得到本子树左右子树在中序遍历中的区间，从而递归求解#include<bits/stdc++...
2019-10-21 21:47:16
119
原创 CodeForces - 555A（思维）
CodeForces - 555A俄罗斯套娃，要想将他分开必须从最外面开始操作首先假设是完全分开的需要n-1次操作试他们连接起来，而在输入的序列中只有当1开头的一段连续序列不需要解开其余非1开头序列必须全部解开，而1开头的只需要解开尾部不连续的部分，即前面的不需要链接，只需要减去前面已连接的操作就可以了，#include<cstdio>#include<algor...
2019-10-21 00:23:09
178
原创 博弈论小结
博弈问题的特点1.博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利2.博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负3.公平博弈。即两人进行决策所遵循的规则相同博弈类问题可以分为以下几类（不完全）：1.巴什博弈问题模型：有一堆东西有n个两个人轮流取一次可以取1到m个，取完的赢。当n%(m+1)==0时先手必败,显然，如果n=m+1...
2019-10-21 00:07:57
179
原创 CodeForces - 520B（bfs+剪枝）
CodeForces - 520B直接进行bfs就行，不过如果不加剪枝的话可能会TLE，，，突然发现很长时间不写bfs都不会写了，，，剪枝只需要在n>m是剪掉n*2，在n<=1时剪掉n-1即可。#include<iostream>#include<queue>using namespace std;struct h{ int k; int s;...
2019-10-19 18:07:44
174
原创 CodeForces - 520A（思维）
CodeForces - 520A思维题，只需要判断是不是26个字母都出现过就行（不区分大小写）#include<iostream>#include<set>using namespace std;int main(){ set<int>p; int n; string a; cin>>n; cin>>a; for(...
2019-10-19 18:03:20
205
原创 POJ-3061 Subsequence(尺取)
POJ-3061#include<cstdio>#include<algorithm>using namespace std;int main(){ int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d%d",&n,&m); int a[n+2]; for(int i...
2019-10-19 14:29:03
112
原创 PAT-A 1101 Quick Sort
1101 Quick Sort (25 分)There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pi...
2019-10-18 00:33:47
86
原创 CodeForces - 574C（思维+最小表示法）
CodeForces - 574C 根据唯一分解定理每一个数都可以表示成(2p13p2~~~~~~~~~)，因为可以每次可以乘无数个二或无数个3，所以只需要将每个数中含有的2和3全部除掉，只要剩下的部分相同就可以完成了。#include<iostream>#include<vector>#include<cstdio>#include<cstri...
2019-10-16 17:56:03
191
原创 CodeForces - 574A（思维+优先队列）
CodeForces - 574A直接暴力，因为要贿赂使自己的票数最高，让比自己票数高的都小于自己，所以可以每次只贿赂票数最高的人，这样就可以以最小的次数让自己的票数最高，这一过程可以通过一优先队列来实现（每次取队首–，自己++，然后将队首加入队列）重复以上过程直到队首小于自己的票数。#include<iostream>#include<vector>#includ...
2019-10-16 17:46:05
156
原创 CodeForces - 574B（思维+暴力）
CodeForces - 574B思维题最暴力的想法是直接枚举3个点，这样复杂度为o(n^3)，对于4000的数据量肯定会挂掉，所以可以改变一下思路先枚举边，每枚举出一条边就得到了两个点，然后枚举剩下那个点找到度数最小值就行。#include<iostream>#include<vector>#include<cstdio>#include<c...
2019-10-16 17:31:37
145
原创 HDU-128 棋盘游戏（二分图匹配）
HDU-128#include<bits/stdc++.h>#define maxn 210using namespace std;int q[maxn];int p[maxn][maxn];bool vis[maxn];int n,m,k;bool dfs(int x){ for(int i=1;i<=m;i++){ if(p[x][i]&&...
2019-10-13 13:54:51
184
原创 二分图判定
所谓二分图，其最大的特点在于，可以将图里的顶点分为两个集合，且集合内的点没有直接关联（之间没有边相连）。判断二分图的常见方法是染色法：用两种颜色，对所有顶点逐个染色，且相邻顶点染不同的颜色，如果发现相邻顶点染了同一种颜色，就认为此图不为二分图。 当所有顶点都被染色，且没有发现同色的相邻顶点，就退出。bool dfs(int v, int c){ color[v] = c; //为...
2019-10-12 22:53:54
264
原创 HAPPY_国庆大礼包-D
题目链接简单差分只需要用两个差分数组来维护每个操作及每个操作执行次数即可不知道差分是什么的看这里#include<cstdio>#include<cstring>#include<algorithm>#define maxn 200000using namespace std;typedef long long ll;ll num[maxn]...
2019-10-12 16:05:40
128
原创 HAPPY_国庆大礼包-E
题目链接题意：给你两个二进制字符串，a,b，和待求值 k 问你怎样使a + b * 2 ^ k的反向后的字典序最小。对于普通的二进制加法，要使反向后的字符串字典序最小，一定是加完之后的末尾0的数量最多，对于 b * 2 ^ k操作其实质是在b字符串后面添加k个0，所以只需要计算在b后添加几个0可以使b字符串最后一个1与a字符串最后一个1对齐，添加0的数量即b向右移位的次数就是k的最小值#in...
2019-10-12 15:56:15
110
原创 数论-欧拉函数
欧拉函数在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。欧拉函数的性质：它在整数n上的值等于对n进行素因子分解后，所有的素数幂上的欧拉函数之积。欧...
2019-09-10 09:05:33
467
原创 图论-最大生成树的最小边
POJ1797#include<cstdio>#include<vector>#define maxn 2000#define inf 1<<29using namespace std;struct h{ int e; int v;};vector<h>a[maxn];bool vis[maxn];int d[maxn];i...
2019-09-02 22:50:00
192
原创 树状数组题目
树状数组POJ2352树状数组求顺序对# include <cstdio># include <cstring># include <iostream># include <algorithm># define LL long longusing namespace std ;int lowbit (int x) { r...
2019-08-11 18:52:16
104
原创 线段树题目整理
线段树题目整理HDU1166线段树单点更新，区间查询#include<iostream>#include<algorithm>#include<string>#define ls k<<1#define rs k<<1|1#define maxn 50005using namespace std;struct no...
2019-08-11 18:46:06
83
原创 线段树（模板）
**线段树（模板）**线段树是一个神奇的数据结构。对于普通的线性结构对其进行区间上的修改复杂度为O(n)，对于n特别大的情况或者修改特别多次数的话仍然会TLE,这个时候就应该使用树形数据结构，它会把单个修改的复杂度降为O(lgn)。所以就需要线段树了。。线段树可以实现单点修改，单点查询，区间修改，区间查询等功能。树的定义#define ls k<<1#define r...
2019-08-09 23:51:08
98
原创 图论-最小生成树（prim算法）
prim算法克鲁斯卡尔算法的核心是对边贪心选取，前提是要先对边进行排序，当边的数量特别大的话依然会出问题，所以当图为稠密图的时候应该使用prim算法。prim算法实质是迪杰斯特拉算法通过更新源点到各点的最小距离来得出最小的边权和。POJ1789#include <cstdio>#include <cstring>#define INF 1<<27...
2019-08-03 17:11:26
204
原创 图论-最短路问题（SPFA）
SPFA算法迪杰斯特拉算法不能解决具有负边权的问题所以就需要SPFA算法来判断负环（当有负环的时候肯定是走负环可以达到最小，，，，）POJ2240因为汇率可以大于或小于1，所以就可以把汇率大于1的交换方法看作负边权，只需要使用SPFA算法使初始点的值大于初始值就好。#include<stdio.h>#include<string.h>#include<q...
2019-08-03 16:18:24
154
原创 图论-拓扑排序
拓扑排序HDU1285#include<bits/stdc++.h>using namespace std;const int maxn=600;int n;int main(){ int a,b; int m; while(cin>>n>>m){ vector<int>p[maxn]; int in[maxn]; ...
2019-07-30 10:45:10
82
原创 图论-最小生成树（Kruskal算法）
Kruskal算法POJ1287所谓克鲁斯卡尔算法就是先将边按边权从小到大排序，然后贪心选取在算法运行时应注意避免成环（避圈法）采用并查集来完成边的合并同时避免成环#include<iostream>#include<cstring>#include<queue> #include<algorithm>#define max 500...
2019-07-29 21:08:22
178
原创 图论-最短路问题(Dijkstra算法)
最短路问题单源最短路1.Dijkstra算法POJ2387Dijkstra模板题主要注意存图方式，其实这个题数据量不大用邻接矩阵完全可以存下，我这里使用vector存图主要是保险（没看见数据量这么小，，）。然后这个是个无向图需要判断重边（我第一次就是在这里wa的，，）对于重复的边应该取最小的边权。这种裸题主要考察细节（我就wa在这上边）。对于Dijkstra算法本身不难，主要就是一...
2019-07-29 20:52:02
496
原创 莫尔斯码（Morse Code）
莫尔斯码（Morse Code）大家有木有看过带谍战剧？里面多数都有发电报的情节吧，有木有感觉滴滴答答地发报特别酷？发报的那个东西，学名叫做“电键”，如图： 电键.jpg电键按下去之后，电路接通，就会发出声音，长短不同的声音组合，就形成了不同的编码，可以表示不同的信息~汉字个数太多，所以汉字的编码是很复杂的。但是英文字母比较少，编码就容易多了我们今天来研究一种国际通用的电报编码——莫尔斯...
2019-02-19 12:14:45
5830
原创 简单购买火车票问题
购买火车票问题我们省略了很多现实中购买火车票的细节，对于一趟列车，根据输入的购票订单信息，查询余票并购票。座位是复用的，即订某段行程，只在该段行程内占据一个座位，在行程外不占座位。举个
2019-02-17 21:47:11
1748
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人