- 博客(27)
- 收藏
- 关注
RSS订阅原创 1118 Birds in Forest（25 分）【并查集】
题意：同一张图中的bird在同一棵tree上，问一共有几棵tree，并判断任意两只bird是否在同一棵tree上。#include <bits/stdc++.h>using namespace std;#define INF 0x7FFFFFint fa[10005];void Init(){ for(int i=1;i<10005;i++) ...
2018-09-04 19:33:23
286
原创 1126 Eulerian Path（25 分）【并查集/dfs】
题意：如果一个连通图的所有结点的度都是偶数，那么它就是Eulerian，如果除了两个结点的度是奇数其他都是偶数，那么它就是Semi-Eulerian，否则就是Non-Eulerian （欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路，具有欧拉回路的图称为欧拉图。欧拉图：就是从图上的一点出发，经过所有边且只能经过一次，最终回到起点的路径。欧拉通路：即可以不回...
2018-09-04 19:31:27
186
原创 L2-013 红色警报（25 分）【并查集】
并查集：判断无向图连通分量个数（或判断无向图中任何两个顶点是否连通）有一点要注意：如果一个结点被占领后，现有的连通分量个数=原连通分量个数 或者 现有的连通分量个数=原连通分量个数+1，都是说明去掉当前结点是无影响的int fa[505];int n,m;int visit[505];struct node{ int u,v;}e[5005];int Find(i...
2018-09-04 19:27:32
460
原创 1115 Counting Nodes in a BST（30 分）【二叉搜索树】
计算一颗二叉搜索树最底两层的节点数，并且求和。首先根据输入的数值建立二叉搜索树。然后用dfs/bfs的方法计算最后最底两层的节点数，最后按照题目要求输出答案。 dfs：#include <bits/stdc++.h>using namespace std;#define INF 0x7FFFFFint n;struct node{ int dat...
2018-09-04 19:22:50
268
1
原创 1138 Postorder Traversal（25 分）【树的遍历】
题意：已知前序遍历和中序遍历，输出后序遍历//超时的时候可以试试将cin、cout换成scanf、printf#include <bits/stdc++.h>using namespace std;struct node{ int data; struct node *lchild,*rchild;};int n;int pre[50005],...
2018-09-04 19:17:27
272
原创 1127 ZigZagging on a Tree（30 分）【树的遍历】
题意：已知中序遍历和后序遍历，建树，输出层序遍历，输出规则为：从左到右，再从右到左，交替输出#include <bits/stdc++.h>using namespace std;#define INF 0x7FFFFFint n;int in[31],po[31];typedef struct node{ int val; struct node...
2018-09-04 19:12:24
622
原创 1109 Group Photo（25 分）【模拟题】
模拟题题意：排序，n个人排成k排，多余的全部放在最后一排。高的要在矮的后面，由于是面向我们的，所以反过来，最高的第一排输出。对于每一排，最高的在中间，然后从高到矮，依次先排在左边，然后排在右边（就像一座山）。高度相同的，按字典序从小到大排。经常写着写着开始怀疑自己，然后思路越来越乱，其实要相信最开始时候的思路是正确的。#include <bits/stdc++.h>us...
2018-09-04 19:06:33
341
原创 1108 Finding Average（20 分）【字符串模拟题】
20分的水题，我却写了40多分钟，严重怀疑自己思路错了。A了以后看了别人的解题报告，才发现原来用两个函数就可以很轻松的解决了。。还是要多掌握一些知识呀。。两个函数：sscanf() – 从一个字符串中读进与指定格式相符的数据sprintf() – 字符串格式化命令，主要功能是把格式化的数据写入某个字符串中 别人AC的简单代码：#include <string.h>...
2018-09-04 16:33:19
376
原创 1020 Tree Traversals（25 分）【树的遍历】
题意：已知后序遍历和中序遍历，构造树，然后输出层序遍历（用bfs）#include <bits/stdc++.h>using namespace std;const int maxn=35;int n;int post[maxn];int in[maxn];typedef struct node{ int val; struct node *lchi...
2018-08-30 10:57:01
255
原创 1007 Maximum Subsequence Sum（25 分）【最大连续子序列和】
题意：求最大连续子序列和并记录该序列的头尾元素#include <bits/stdc++.h>using namespace std;int N;int main(){ cin>>N; vector<int> v(N); int l=0,r=N-1,sum=-1,temp=0,tl=0; for(int i=0;...
2018-08-30 10:46:41
908
原创 1004 Counting Leaves（30 分）【dfs/bfs】
题意：给你一个家谱树，找到没有孩子的人，即寻找每层的叶子结点数方法一：用dfs。采用vector数组作为树的存储结构，将树结点逐一输入到vector 中，每一个元素存储了该结点的子孩子信息，自动向下探索子孩子，直到vector[i].size()==0表明该结点的子孩子为零，即叶子结点。 #include <bits/stdc++.h>using namespace std...
2018-08-30 10:42:29
179
原创 1143 Lowest Common Ancestor（30 分）【最近公共祖先】
二叉搜索树的建树和寻找最近公共祖先（题目给出了BST的前序遍历，而前序遍历升序排列就是BST的中序遍历了）#include <bits/stdc++.h>using namespace std;typedef struct node *Node;typedef struct node{ int val; Node l,r;}node;Node T;...
2018-08-30 10:36:00
242
原创 1146 Topological Order（25 分）【拓扑排序】
拓扑排序的步骤： 由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。 【把顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网，简称AOV网。】(1) 选择一个入度为0的顶点并输出之； (2) 从网中删除此顶点及所有出边。*循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。 #inc...
2018-08-30 10:29:00
244
原创 1003 Emergency（25 分）【dfs/dijsktra】
题意：一张图，已知起点终点，计算起点到终点的所有最短路径，每个点上有一个数，代表这个点上的搜救队的数量，要求输出这些最短路径中你能召集到的最大的搜救队的数量。方法一：dfs#include <bits/stdc++.h>using namespace std;#define INF 0x7FFFFFint n,m,st,en;int map[501][501]...
2018-08-30 10:19:06
226
原创 hdu 1263 水果（map的使用2）
因为要按字母顺序排列，用结构会比较麻烦，而map会自动排序，用map写会方便很多#include#includeusing namespace std;map >a;int main(){ int T; cin>>T; while(T--) { a.clear(); int m; cin>>m;
2016-07-30 10:40:01
182
原创 hdu 1004 Let the Balloon Rise（map的使用1）
#include #include using namespace std;mapballoon;int main(){ string co,maxco; int n,m; while(cin>>n && n) { balloon.clear(); while(n--) { cin>>
2016-07-29 12:54:24
124
原创 hdu 5762 Teacher Bo（vector的使用1）
曼哈顿距离，两个点在标准坐标系上的绝对轴距总和。#include #include #include #include using namespace std;typedef pair PII; //pair将一对值组合成一个值，这一对值可以具有不同的数据类型（T1和T2），两个值可以分别用pair的两个公有函数first和second访问。const int maxn = 100
2016-07-27 11:46:06
174
原创 统计单词数
#include #include #include using namespace std;char s1[15],s2[10000001],c[15];int fun(char *s1,char *s2) //比较两个字符串是否相等{ int i,l1,l2; l1=strlen(s1); l2=strlen(s2); if(l1!=l2)
2016-07-25 11:47:09
186
原创 多项式系数
用杨辉三角算系数C（k,n），因为数字很大，即使是long long也会超，所以边乘边求余#include#includeusing namespace std;#define N 10007int s[1005][1005];int fun(int a,int n){ int i,t; a=a%N; t=a; for(i=0;i<n-1;i++)
2016-07-25 11:35:26
518
原创 hdu 5744 Keep On Movin
题意理解了好久，最后还是理解错了。。“He also wants to maximize the length of the shortest palindromic string.”应该是要使一组里的最小回文子串尽量大的情况下，输出那组的最小回文子串的长度比如例1，应该是在cdadc，dbd时，输出3所以就是把可以构成回文的字母（偶数的字母）平均分配给那些只有单个的字母
2016-07-22 10:50:37
146
原创 hdu 5742 It's All In The Mind
#includeusing namespace std;int gcb(int a,int b){ int c; while(b) { c=b; b=a%b; a=c; } return a;}int main(){ int T; cin>>T; while(T--)
2016-07-22 10:46:25
142
原创 L1-009. N个数求和
#include#includeusing namespace std;long long gcb(long long a,long long b){ long long c; while(b) //辗转相除法 { c=b; b=a%b; a=c; } return a;}int main(){
2016-07-15 15:17:51
176
原创 L1-003. 个位数统计
写一个函数来查找字符串中每个数字出现的次数，然后存到数组里#includeusing namespace std;int get_number_times(string& S,int number){ int count=0; for(int i=0;i<S.length();i++) { if(S[i]==char(number+48))
2016-07-15 13:48:51
145
原创 L1-002. 打印沙漏
分成上下两部分输出会比较容易一些#includeusing namespace std;int main(){ int n; char c; cin>>n>>c; int i,j,sum=1,count=0; while(sum<n) { count++; if(sum+(count*2+1)*2>n)
2016-07-15 13:46:56
127
原创 L1-006. 连续因子
就是搜索，从每个能够整除的因子开始往下连续搜索，直到不能再整除，退回以后找下一个能够整除的因子；唯一的点是素数输出其本身，个数为1；#include#includeusing namespace std;long long int length=0,ans=0,l;long long int find(long long int n,long long int fec,long l
2016-07-15 13:42:06
197
原创 ZOJ 1090-The Circumference of the Circle
需要用到数学知识。。然而我都忘了。。于是搜了解题报告在圆的内接三角形的性质中有这样一条：三角形的任何两边的乘积的等于第三边上的高于其外接圆直径的乘积求面积可以用海伦公式：S=sqrt(p*(p-a)*(p-b)*(p-c)),其中p=(a+b+c)/2#include#include#define pi 3.141592653589793double dis(double x
2016-05-29 16:45:39
195
原创 ZOJ 1078-Palindrom Numbers
不难的一道水题，但是第一次wa了，因为没考虑到字符串末尾要加‘\0’#include#includeusing namespace std;char s1[50],s2[50];int j;int fun(){ int i,k=0; for(i=j-1;i>=0;i--) s2[k++]=s1[i]; s2[k]='\0'; if(s
2016-05-29 15:58:05
207
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人