- 博客(56)
- 收藏
- 关注
RSS订阅原创 数据结构之二叉树的基本操作
本次实验的内容有：1、前序遍历生成二叉树；2、前序、中序、后序遍历上述生成的二叉树（使用递归）；3、使用非递归方式中序遍历二叉树；4、输出二叉树的深度、节点个数。本来写的是顺序栈，后来看栈中存的是指针，就改成链栈了。另外在创建二叉树的时候，用#代表空位置。接下里是运行图片：代码#include <bits/stdc++.h>using namespace std;...
2019-04-21 20:35:54
457
原创 HDU -2425(BFS)
题目链接： Hiking Trip思路本来以为求最短步数，美滋滋敲了一遍，后来看是求最小的花费。优先队列就是好使。#include <bits/stdc++.h>using namespace std;char a[21][21];int vis[21][21];const int inf = 0x3f3f3f3f;struct node{ int x,y,ti...
2019-04-17 21:43:20
157
原创 HDU - 2066(dijkstra)
题目链接： 一个人的旅行思路虽然只是一道普通的最短路，但是还是有可以借鉴的点。一个是原来的做法就是跑多次最短路，但是今晚上翻了翻别人的做法，发现其实可以跑一次dijkstra,就是把家设为0点，然后家到车站的距离设置为0，然后我们只要求家到每个点的最短路径就可以了。第二点是又强化了dijkstra的堆优化，一次过了好激动。#include <bits/stdc++.h>usi...
2019-04-15 22:07:31
142
原创 ZOJ - 3946- Highway Project（最短路）
题目链接： Highway Project题意让你跑一段最短路，而且是从0点跑到其余的每个点，但是要求在最短时间的情况下的最小金钱cost, 输出的第一个值代表dist[1] + dist[2] + … dist[n] ,第二个值代表在最短路这个图中你走过的边的总的花费的金钱。思路用spfa，最短路径好求，主要是求最小的金钱花费。我们知道每个点他的前面都有一条边，我们记录的就只是他前面...
2019-04-15 16:44:50
197
原创 URAL-1004(floyd)
题目链接： Sightseeing Trip 题意求图的最小环，并且输出路径。思路POJ 崩了一晚上，只能用其他网站提交了。floyd不仅可以求出两点之间的最短路径，并且稍加变形也可以求最小环。在K点还没更新任意两点距离之前，我们正好就以K为中间节点来作为环的另一边的中间节点。比如说我们已经在K - 1次循环中求的了 i -> j 的最短路径，当我们进行第K 次循环时，发现 i ...
2019-04-12 21:19:03
131
原创 POJ -2375(强联通)
题目链接 Cow Ski Area题意好吧，还是看了各种翻译才看懂的。说的是一个人要自己建滑雪场 ，每个滑雪场都是一个一个方格，在输入中也就是一个数字（这个数字也就是这个滑雪场的高度），现在告诉你，每两个相邻的滑雪场可以直接从高的滑雪场通向低的滑雪场，低的不能通向高的滑雪场。除此之外没有别的通路。为了使得最后能从某任意一个滑雪场通向任意一个滑雪场，这个人会建一些路，这样才能使得低高度的滑雪场通...
2019-04-11 23:04:49
125
原创 POJ -2472(乘积最短路)
题目链接： 106 miles to Chicago题意现在一个逃犯想要逃脱警察的追捕，他有很多路可以走，告诉你了他走这条路不被抓住的概率，现在让你求他从1点走出N点不被抓住的最大概率。思路首先概率应该是乘积，所以初始化就会有一些变动，权值代表的是概率，权值为0就代表一定会被抓住，所以一开始的初始化就是都赋值为0，dist[1] = 1，代表到自身一定不会被抓住。然后就是dijkstra了...
2019-04-10 16:50:04
476
原创 HDU - 2855（规律+矩阵快速幂）
题目链接： Fibonacci Check-up思路我们应该已经会了基本的求斐波那契这种递推式很简单的矩阵快速幂了，问题是本题没让你求斐波那契，只不过求和的公式里用到一部分而已。我们可以看看S（n）和F（n）之间有没有什么联系，可以先打个表。(如果只是用公式推，网上有详细过程，非人类的推导过程)F1F2F3F4F5F6112358S1S...
2019-04-09 22:09:43
155
原创 HDU -2680(反向建图dijkstra)
题目链接：Choose the best route题意有个小孩要到他朋友家，但他只能做与他家相邻的车站的车，问他从某个车站坐车到他朋友家的最短时间是多少。思路由于车站的数量很多，但是朋友家就只有一个，如果我们以车站为源点不断求此车站到朋友家的距离的话会超时。所以可以以朋友家为源点反向建图，注意此题为单源路径。#include <stdio.h>#include <i...
2019-04-09 20:16:23
185
原创 数据结构之串
感悟主要是串的初始化，连接函数，赋值函数，求串的长度。还有BF算法，但是是求所有可能出现的位置，由于我是从下标0开始存的，所以与书上的不太一样。要注意一下，当获得第一个位置之后，i和j应该怎么移动。#include <bits/stdc++.h>using namespace std;vector<int>V;typedef struct { char ...
2019-04-08 18:40:08
156
原创 HDU- 2807(矩阵运算 + floyd)
题目链接： The Shortest Path题意有N个城市，每个城市用一个矩阵表示，如果A * B = C 也就是说A 矩阵 乘以B矩阵 == C 矩阵，就代表从A 到C 城市有一条权值为1的路，而且是单向的。之后有Q次询问，问从X到Y城市有没有最短路径，有就输出最小的权值，否则输出-1.思路N的范围才80 ，可以用Floyd。先把所有的矩阵运算算出来，看看哪两个城市之间有路，这里我也...
2019-04-07 23:29:54
180
原创 POJ - 1679（判断MST是否唯一）
题目链接： The Unique MST题意给你一个图，让你判断这个图中的最小生成树是不是唯一的。思路这题看起来挺简单的，就是删边，我们先把最小生成树求出来，再逐个删掉其中的边，看看删边之后的最小生成树是不是还是那个值。但是细节很多，收获颇丰。首先这个题可能会有不连通的状态。再就是用Kruskal删边的时候，假若说有一条边的边权为0，那么如果我们此时恰好删这条边，那么删边后的图时可能是不连...
2019-04-07 20:09:57
208
原创 POJ - 3625(prim)
题目链接： Building Roads题意需要把每个农场联结起来，输入每个农场的坐标，以及告诉你哪些农场之间已经连起来了，需要你计算最小的还需要修的路程。思路只是简单的最小生成树，但是需要注意精度问题，可以用double 存 农场的坐标。 还要注意G++ 里double的输出是printf("%.2f"),而不是%.2lf。#include <stdio.h>#inclu...
2019-04-07 18:51:04
87
原创 HDU -1598(枚举 + 并查集)
题目链接： find the most comfortable road思路一开始完全想不到并查集上面，后来看这种方法很巧妙。我们先把所有的边按权值从小到大排列，然后我们枚举每条边，以这条边为起边，再枚举这条边后边的权值比它大的边（同时要合并这条边联结的两个点），直到枚举到了一条边之后，起点和终点联通了，说明这两条边可以联通这条路，就可以用后面的权值大的边-权值小的边了。#include &...
2019-04-07 10:55:44
120
原创 HDU - 1811(并查集 + 拓扑排序)
题目链接: Rank of Tetris思路我们先处理=的情况，把相等关系的两个数字合并，最终只用他们的根来代表他们。然后再处理> < 的情况，我们需要先找到每个数字的根，再进行边的连接。我们还需要记录缩点后最终有几个数字，以及进行topo的时候，放进队列的条件是in[] == 0 && find[i] == i(因为有些数字没有边连接，它们被我们合并了，就是=的情...
2019-04-06 16:49:49
139
原创 数据结构之舞伴配对问题
题目及思路有多个男生和女生，要求为男女生进行选舞伴的配对，输出的结果根据自己的设计而定，我制定的问题是，输入一个数字（代表第几支舞曲），然后输出在此曲中跳舞的男女生的配对情况。没有用循环队列，用的链队。#include <bits/stdc++.h>using namespace std;typedef struct{ string name; char sex...
2019-04-05 13:42:45
2588
原创 POJ -2139(floyd)
题目链接： Six Degrees of Cowvin Bacon题意有N头牛，分成M个团体，每个团体的牛之间的距离是1，每头牛到自己的距离是0，如果A 和B是一个团体，B和C是一个难题，但是A和C不同属一个团体，那么A和C的距离是2.求每头牛与其他牛的距离的总和/其他牛的头数的最小值。思路标准的floyd，我们需要求出任意两头牛之间的距离，最后再累加。我们在开始处理的时候，需要把一个团体...
2019-04-04 19:35:34
200
原创 POJ -3734(矩阵快速幂)
题目链接： Blocks题意有N个方块，依次给每个块涂颜色，有红蓝绿黄四种颜色可选，问最后涂完，使得红色和绿色块均为偶数的涂法总共有几种，最终答案mod10007思路N可以达到很大，我们需要找到递推关系式子。我们假设到第i个块的时候，a[i]代表红绿块均为偶数的涂法数目。b[i]代表红绿块有一种块为偶数的情况数目。c[i]代表红绿块均为奇数的情况数目。那么到第i + 1个块时：...
2019-04-02 20:52:03
209
原创 HDU -4686 (矩阵快速幂)
题目链接： Arc of Dream题意给你f[n]和g[n]的递推关系，和你说明了一些原始量的大小，让你推Arc[n].题意最近好长时间一直在WA，本想放弃一段时间，奈何功夫不负有心人，终于找出了诸多漏洞所在。 本题的大数会爆Long long , 需要不断取余。主要的错误还是在于我的代码的细节问题，赋值字母竟然输错了。而且还有个重大发现，以前发现数组开小了会TLE，没想到这次开大了还...
2019-04-02 19:26:55
214
原创 Codeforces 846 D(线段树)
题目链接： D. Monitor题意求K*K格子的最大值。初始值都为inf.思路简单的线段树求区间最大值。#include <bits/stdc++.h>using namespace std;int tree[3200][3200];const int inf = 0x3f3f3f3f;void update_y(int xnode,int ynode,int xb...
2019-04-01 22:04:01
161
原创 codeforces 771 A
题目链接： A. Bear and Friendship Condition题意如果A和B是朋友，B和C是朋友，那么A和C是朋友。现在给你一些关系，问你这些关系构成的图是否合理。我们必须把所有的关系都写出来。思路用并查集，先求联通块，把联通子图求出来，这个联通块要想合理，边数必须为n*(n-1）/2，（n为联通快节点的个数），我们将这个边数和这个联通快实际的边数比较，看是否相等，不相等该联...
2019-04-01 19:46:58
814
原创 Excting Secret Chamber at Mount Rushmor(Floyd)
题意告诉你一些字母的转换，然后再给你一些字符串，问你第一个字符串能不能转换到第二个。感悟比赛时候的一道题，队友宝乐各种模拟一顿操作，始终WE，TLE，不得不说，宝乐的模拟太骚了。到了临近比赛结束大约半小时把，我想到用floyd,毕竟只有26个字母。 带着窃喜的心情开敲，嗯本来想看看模板的，但是想想这个还用模板么，就是三重循环，然后开始半小时WE的专场，QWQ，就是因为三重循环的顺序错了。敲...
2019-03-30 21:10:01
104
原创 POJ -3233，HDU-5015(矩阵快速幂)
题目链接： POJ-3233思路利用矩阵快速幂推出转移矩阵。注意什么时候取模，同时用printf一定要注意格式的问题，与类型要匹配。这次的转移矩阵是由一些子矩阵构成，不再是一些普通的常数了。#include<cstdio>#include <iostream>#include <algorithm>#include <cstring>...
2019-03-29 21:50:23
111
原创 UVA-11992(线段树)
题意对矩阵有三种操作，第一是让矩阵的每个元素加上某个数，第二是让矩阵得每个元素变成某个数，第三是输出某个子矩阵的数字总和，最大值和最小值。开始时，矩阵得每个元素为0.思路因为最多只有20行，所以可以每行都建立一个线段树，问题是注意set操作和add操作之间的联系，set是优先于add的。我在pushdown函数中就因为没注意这个问题，WA到怀疑人生。#include<bits/std...
2019-03-25 19:32:14
158
原创 HDU-1896（优先队列+模拟）
题目链接： HDU-1896题意给你一些石子所在的位置，上面可能会有多个石子，你可以从该位置向远处扔，距离就是D[i],但是你只会扔奇数的石头，他是奇数还是偶数怎么看呢，就是看你排的序，同一位置上D[i]小的排在前面。思路用优先队列模拟即可。#include <bits/stdc++.h>using namespace std;struct node { int p...
2019-03-24 19:40:30
234
原创 HDU-6470，HDU-1575, HDU-1757（矩阵快速幂）
== 题目链接：== HDU-6470思路根据题意有 f[n] = f[n-1] + 2f[n-2] +n^3,构造转移矩阵。#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef l...
2019-03-23 21:12:56
147
原创 山东省第七届ACM省赛C题(Proxy)
题目链接： Proxy题意比赛前期读题不顺，不知道是最小生成树还是最短路径，好吧，其实我们最开始想的连最短路径都不是到了后期终于知道了题意。就是给你一个图，让你求0节点到n+1节点的最短路径，但不是让你输出最小权值，而是输出在这个路径上的最接近源点的那个节点。如果0到n+1的最短路上中间没有其他节点了就输出0，或者说如果0节点到n+1节点的距离为无穷大，就输出-1；思路比赛中想的是根据输...
2019-03-19 20:23:50
161
原创 HDU -5057(分块法)
题目链接： Argestes and Sequence题意询问你很多区间，问你这一段区间内总共有几个第D位是P的数字。思路比赛的时候用三维线段树超内存了，恰逢最近在学习莫队，正好这个题目也是分块的思想，不得不说好嗨哦。看下数据范围，我们开一个sqrt（N）大小的block,每个块也就几百个元素，我们把这个块内所有的信息都收集到block[i][D][P],代表第i块第D位是P 的数字个总...
2019-03-16 20:02:58
312
原创 数据结构之单链表
#include &amp;amp;lt;bits/stdc++.h&amp;amp;gt;using namespace std;typedef struct LNode{ int date; struct LNode *next;}LNode,*LinkList;void createList(LinkList &amp;amp;amp;L,int n) //头插法{ LNode *r,*p;
2019-03-16 19:28:16
121
原创 HDU-5213，洛谷-P1494 (莫队算法)
题目链接： 小Z的袜子思路莫队算法用于解决离线处理问题，即先把所有询问记录一遍，对询问的进行排序操作后，最终一起输出答案。对于区间询问，其实我们就是设置了两个指针L,R，我们其实可以在O(1)的时间内完成从【L,R】的询问到【L+1，R】或者是【L，R+1】的询问，因此排序的原因就是使得指针跳来跳去的次数能够减少一些。#include &lt;bits/stdc++.h&gt;usin...
2019-03-16 15:29:47
127
原创 POJ-1236 ,POJ-2186,POJ-2762（Tarjan 强联通子图+缩点）
题目链接: Network of Schools题意本题就是说给你一个有向图，然后告诉你每个点与哪些点相连，然后问你需要多少个点才能从这个点出发遍历另外的全部的点。需要增加多少条有向路，才能使得两个点之间可以任意联通成为一个强联通图。思路利用tarjan缩点之后，我们可以很容易求出来有n个点的入度为0，有m个点的出度为0.（这些点是缩后的点）那么需要的点数为n,需要增加的有向路的条数为ma...
2019-03-09 15:50:56
106
原创 POJ-3974 , HDU-3294, Hdu-3613(manacher)
题目链接： Palindrome思路简单的manacher模板，不多说.#include &lt;cstring&gt;#include &lt;iostream&gt;#include &lt;algorithm&gt;using namespace std;char s[2010001];int P[2010001];int id,miner;int manacher(
2019-03-09 15:49:36
100
原创 数据结构之顺序表
下周就要上数据结构实验课，提前写写熟悉一下。顺序表还是比较简单了，和数组差不多。#include <bits/stdc++.h>using namespace std;const int INIT_SIZE = 1001;typedef struct node{ int *elem; int length;}Sqlist;int a[1001];void...
2019-03-09 09:44:04
99
原创 HDU-1556(线段树或树状数组)
题目链接： Color the ball思路已经写过一次类似前缀和的题解了，这次再写一遍线段树或树状数组的解法。这题是区间更新和单点查询，线段树的单点查询不过是区间查询的特殊形式，代码是一样的。但是树状数组的区间更新和单点查询却不同于区间更新和区间查询。不过此处就不详细说了，树状数组本身就是个神奇的东西。1.线段树#include <iostream>#include &l...
2019-03-02 21:29:17
159
原创 POJ-2155(二维线段树)
题目链接： Matrix题意给你一个N*N矩阵，初始都为0，有两种操作，是C操作的话就是把左上角坐标为（X1,Y1），右下角坐标为（X2,Y2）的矩阵的元素变一下，原来是1就变成0，是0就变成1；是Q 操作的话就是 询问坐标为（X1,Y1）的元素是多少。思路相比较一维，二维变成了树套树，我们的思路是每次更新，先找一维坐标的相应区间，找到后再到二维区间中找对应的，找到区间后，把此区间的tr...
2019-02-28 18:22:55
258
原创 POJ-2299(线段树或树状数组或归并排序)
题目链接： Ultra-QuickSort思路刚刚学线性代数学到的逆序数，用多重循环果然超时，刚开始的时候完全没有线段树的思路，后来看了别人的思路，发现真的妙啊，开心的飞起来，虽然我后面又因为把小括号写成中括号的问题WA了一晚上。比如说9 1 0 5 4这个序列，我们记录一下他们的序号位置，然后再排个序：01459在原序列中的位置32541开始我...
2019-02-28 09:53:45
1516
1
原创 POJ -1019 （数学）
题目链接： Number Sequence题意给定一个特殊序列，1 12 123 1234 12345 123456…问你第N个数字等于多少。思路我们利用两个数组a[i]和s[i]，a[i]储存第i组的数字位数。s[i]储存前i组总共的数字位数。我们首先找出来N大致在第几组，也就是第一个while循环那里，然后就可以求出N在第i组中的位置pos,我们从第i组的第一个数也就是1开始查找，直到...
2019-02-25 22:11:36
241
原创 HDU-5124，POJ-2528(线段树+离散化)
题目链接： lines题意求相交区间的最大的相交次数。思路先离散化处理，再用线段树求每段区间的相交次数，这个线段树的每个节点代表这段区间的总相交次数，最后再比较每个小区间的相交次数，找最大值。#include &lt;bits/stdc++.h&gt;using namespace std;const int maxn=100001;int addmark[maxn&lt;&lt;...
2019-02-25 19:11:21
161
原创 HDU-3823，LightOJ-1259(素数筛)
题目链接： Prime Friend思路先把所有的素数保存起来，然后枚举两个相邻的素数，看看他们的差与输入的两个数的差是否相等，相等就输出（小的素数-小的输入的数），注意maxn的取值问题，以及flag的初始化。我WA了几次是因为忘记0也是一个合法的答案了。#include <bits/stdc++.h>using namespace std;const int maxn...
2019-02-24 14:27:03
112
原创 HDU-1022(栈)
题目链接： Train Problem I思路这是比赛遇到的一道题，因为思路过于简单，WA到哭，再次想这道题的时候，发现其实思路还是挺简单。我们把string1中的元素逐个的push进栈中，如果遇到string2中的元素，就把这个元素从s栈中pop出来（可能这个pop是一连串的pop）,不过在这个过程中我们需要记录进出的先后。#include <bits/stdc++.h>u...
2019-02-24 10:58:46
349
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人