- 博客(189)
- 收藏
- 关注
RSS订阅原创 1133 Splitting A Linked List
题目大意：给你一个链表，要求重新排定元素顺序，规则是先把负数放在前面，然后大于等于0小于k的数放在k前，大于k的放在k后。解题思路：根据题意遍历三次链表分别处理这三种数据构建新链表即可。代码如下：#include<iostream>#include<cstdio>#include<algorithm>using namespace std;s...
2019-02-27 10:58:51
247
原创 1132 Cut Integer
题目大意：把一分偶数长度的数M切成两段a,b，如果M%（a*b）==0就输出Yes，否则输出No。解题思路：模拟即可。代码如下：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;long long ...
2019-02-27 10:53:23
284
原创 1110 Complete Binary Tree
题目大意：判断是不是完全二叉树，是则输出最后一个节点的下标，否则输出根节点下标。解题思路：一开始从输入上投机（只有右子没有左子肯定不是，只有左子没有右子但是数量超过2也不是），只拿到18分（忽略了右子树饱满没有左子树的情况）。正确的做法是维护一个下标参数（指完全二叉树结点与位置对应关系），DFS遍历树，如果最大结点的编号正好等于最大的下标证明是一个完全二叉树，否则必然有空缺的位置（该下标下...
2019-02-27 10:50:10
609
原创 1122 Hamiltonian Cycle
题目大意：给一个无向图，然后查询k个环，问是不是哈密尔顿环（一个环遍历图上所有点有始有终且不重复访问）。解题思路：用set判断是否有重复访问的节点（起点终点例外），记录起点和终点比较判断能否走出一个环，用vector记录上一个节点判断当前节点是否可以访问到（存不存在路径）。代码如下：#include<iostream>#include<map>#includ...
2019-02-26 11:13:33
410
原创 1121 Damn Single
题目大意：给出n对情侣编号，然后给m个参加聚会的人的编号，输出单身狗的编号（有CP但是CP不在聚会上也算）。解题思路：STL模拟，需要注意一下编号为0的情况，因为用map标记初始化的时候都是0。代码如下：#include<iostream>#include<cstdio>#include<set>#include<vector>#...
2019-02-26 11:05:51
248
原创 1120 Friend Numbers
题目大意：求出每一个数的各个位数相加和，去重后从小到大输出。解题思路：模拟+set代码如下：#include<iostream>#include<cstdio>#include<map>#include<set>#include<algorithm>using namespace std;map<int,in...
2019-02-26 11:00:08
181
原创 1148 Werewolf - Simple Version
题目大意：一个狼人杀游戏，已知肯定有两头狼，其中有一头说谎，然后平民里也有一个说谎，要求找出这两头狼的编号，如果存在多个解输出字典序最小的。解题思路：由于数据量并不大直接暴力枚举两头狼的编号即可，维护一个身份数组，在枚举狼时将对应的下标下的数组值变为-1，其他下标是1。然后遍历每个人说的话，如果出现矛盾（所说的人的身份和我们ID数组中对应的矛盾）说明这个人说谎，将说谎人的编号保存下来，如果...
2019-02-25 22:45:52
248
原创 1115 Counting Nodes in a BST
题目大意：数一个BST（二叉查找树）最后两层节点的数量。解题思路：维护一个深度参数，建树时记录下最大深度然后BFS遍历统计即可。代码如下：#include<iostream>#include<algorithm>#include<cstdio>#include<queue>using namespace std;int n,ma...
2019-02-25 22:34:55
265
原创 1113 Integer Set Partition
题目大意：把n个数划分成两个集合，要求两个集合内部数总和的差值最大，集合大小的差值最小。解题思路：水题，排序分两边。代码如下：#include<iostream>#include<cstdio>#include<algorithm>#include<set>using namespace std;int main(){ in...
2019-02-25 22:30:01
194
原创 1112 Stucked Keyboard
题目大意：键盘上有的键有问题，按一下在屏幕上连续显示k个，现在给你一个文本串，按照查找顺序输出有问题的按键，并且还原原始文本串。解题思路：遍历，将没有连续出现k次或是k的整数倍次的字符标记，没被标记的就是有问题的。然后再扫一遍将有问题的键存入数组，输出的时候到达有问题的键就跳过k个继续输出即可。代码如下：#include<iostream>#include<set&...
2019-02-25 22:26:05
216
原创 1117 Eddington Number
这个题真是搞了，一开始搞错了题意以为就是要求E个超过E英里的骑行天，然后只拿到18分。后来发现题目中有个“maximum”顿时懵逼了，从大到小枚举说不通啊，举例比方说如果有7天骑行超过7英里那么怎么会有6天骑行超过6英里这种情况，换句话说从小到大和从大到小理论上没区别啊。。后来百度了才知道题意是至少有E天，比方说有7天超过6英里那么E=6（并不是天数必须是6）这个答案也是对的，所以才是从大到小枚...
2019-02-24 22:09:01
212
原创 1116 Come on! Let's C
题目大意：根据排名（从一开始）的情况决定获奖的类别，第一拿神秘大奖，素数排名拿小黄人，其他拿巧克力。然后查询，输出查询结果。解题思路：水题，模拟即可。代码如下：#include<iostream>#include<map>#include<cstdio>#include<cmath>#include<algorithm>...
2019-02-24 21:52:28
210
原创 1118 Birds in Forest
题目大意：有n张照片，每张上面的鸟来自同一棵树，问有多少棵树和鸟，并且查询一对鸟是否来自同一棵树。解题思路：并查集板子题，合并每一对输入的鸟，用数组记录鸟的编号并统计鸟的数量，最后用father数组统计树的数量。代码如下：#include<iostream>#include<cstdio>#include<set>#include<alg...
2019-02-24 21:32:07
251
原创 1155 Heap Paths
题目大意：判断一个完全二叉树是不是堆，是最大堆还是最小堆，并且从右到左输出它的每一条路径。解题思路：DFS遍历+数组记录路径即可。代码如下：#include<iostream>#include<cstdio>#include<vector>#include<algorithm>using namespace std;int n,...
2019-02-24 11:38:11
265
原创 1127 ZigZagging on a Tree
题目大意：给定二叉树的中序和后序遍历，输出“层次”遍历，这个层次遍历从根节点的子节点开始，先从左到右输出，然后从右到左输出。。。循环往复。解题思路：这个题我写的复杂了一点，关于输出哪里我用了两个双端队列模拟了输出的扩展情况，即从左到右和从右到左，所以代码较难理解。维护一个度参数根据奇偶度判断是从右到左还是从左到右输出会方便很多。代码如下：#include<iostream>...
2019-02-24 11:28:36
250
原创 1125 Chain the Ropes
题目大意：两个绳子结合成一个绳子总长度会减半，现在给你n条绳子把他们连接成一条，输出最长的方案的长度。解题思路：排序，从小到大一个一个连就好了，因为从小到大连损失的长度最少。、代码如下：#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;algorithm&gt;using namespace std;int
2019-02-24 10:58:13
180
原创 1124 Raffle for Weibo Followers
题目大意：m条微博转发记录，第一个获奖者编号为s，每间隔n个就是下一个获奖者。但是没人只能拿一次奖，如果当前位置的人已经拿过了就向下顺延。解题思路：小模拟。代码如下：#include<iostream>#include<cstdio>#include<cstring>#include<map>using namespace std...
2019-02-24 10:53:52
189
原创 1138 Postorder Traversal
题目大意：给出二叉树前序遍历和中序遍历，要求输出后序遍历第一个数。解题思路：用前序和中序构建二叉树时递归返回的第一个节点就是后序遍历的第一个数。代码如下：#include<iostream> using namespace std;int in[50010],pre[50010],n;struct node{ int data; node* lchild; n...
2019-02-22 11:29:17
248
原创 1137 Final Grading
题目大意：每个学生有四个成绩，线上成绩，期中，期末，总分。现在分别给出这四门成绩下对应的学生分数情况。要求按照总分从大到小（分数相同则按照ID字典序升序）输出总分及格（>=60分）的学生成绩情况。线上成绩必须不小于200分。解题思路：用MAP给每名学生分配唯一的编号方便用结构体保存信息并排序，输入时对于线上成绩小于200的学生不保存。代码如下：#include<iostre...
2019-02-22 10:11:24
356
原创 1136 A Delayed Palindrome
题目大意：判断一个字符串是否是回文串，不是就和它的倒置字符串相加，直到结果是回文串为止。如果这样的操作进行十次后还不是回文串，那么就输出“Not found in 10 iterations.”。解题思路：用字符串模拟大整数相加即可。代码如下：#include<iostream>#include<cstdio>#include<cstring>...
2019-02-22 09:53:58
178
原创 1147 Heaps
题目大意：判断一个完全二叉树是最大堆还是最小堆还是不是堆，然后输出后序遍历的结果。解题思路：根据最大最小堆的定义一次判断父节点和子节点的关系并记录，如果记录出现冲突说明不是一个堆，否则就输出记录的结果，最后输出后序遍历。代码如下:#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;fstream&gt;#inclu
2019-02-20 11:02:00
258
原创 1144 The Missing Number
题目大意;给n个数字，找到不在这个数字列表里面的最小的正整数.解题思路：这题做法很多，我这里为了熟悉一下STl用了SET去重加vector排序，也可以直接用数组标记然后遍历就可以。代码如下：#include<iostream>#include<cstdio>#include<fstream>#include<set>#includ...
2019-02-20 10:38:38
208
原创 1146 Topological Order
题目大意：给出一个有向无环图（DAG），然后给出K个拓扑排序序列，判断哪些序列不是拓扑序列，不是拓扑排序的序列将编号输出。解题思路：拓扑排序的思想是将每个入度为0的节点所有的出边顶点的入度都减1，直到减为0就将该点加入拓扑序列中。按照这个思想反过来验证给出的序列的正确性，如果当前点的入度为0，就松弛所有出边点的入度，否则就不是拓扑序列。代码如下：#include<iostream...
2019-02-20 10:31:05
303
原创 1021 Deepest Root
题目大意：给出n个节点与N-1条边，问：它们能否形成一棵N个节点的树？如果能，则从中选出节点作为树根，使得整棵树的高度最大。输出所有满足要求的可以作为树根的节点，解题思路：DFS深搜即可，走过的点都标记上，如果一轮搜索下来还有点没有访问过，证明它不是一棵树。代码如下：#include<iostream>#include<cstdio>#include<...
2019-02-19 10:50:40
239
原创 1076 Forwards on Weibo
题目大意：在微博中，每个用户都可能被其他若干用户关注。每当该用户发布一条信息时，他的关注者就可以看到这条信息并选择是否转发它，且转发的信息也可以被转发者的关注者再次转发，但同一用户最多只转发该信息一次（信息的最初发布者不能转发该信息）。现在给出N个用户的关注情况（即他们各自关注了那些用户）以及一个转发层数上限L，并给出最初发送消息的因户编号，求在转发层数上限内消息最多会被多少用户转发——摘自《...
2019-02-19 10:31:04
203
原创 1098 Insertion or Heap Sort
题目大意：给你初始序列和一段经过部分排序后的序列，问是经过了堆排序还是插入排序，输出排序方式并输出该排序下的下一步的输出序列。解题思路：模拟堆和插入排序的步骤即可，插入用sort更方便一些。每次完成一步后和目标序列进行比较，相同就再进行一步然后返回输出即可。代码如下：#include<iostream>#include<cstdio>#include<...
2019-02-15 21:51:44
175
原创 1107 Social Clusters
题目大意：n个人，每个人都有k个兴趣，后面是兴趣种类的编号。有相同兴趣的两个人放到一个组里，两两组之间的人没有任何相同的兴趣，要求输出兴趣组数并按照非递增顺序输出兴趣小组的人数。解题思路：并查集的模板题，通过判断两个兴趣集合是否有交集判断这两个人是否属于同一组，开一个数组记录每棵树下的节点数量，在合并子节点时修改对应树的节点数量。代码如下：#include&lt;iostream&gt...
2019-02-14 22:07:22
345
原创 1099 Build A Binary Search Tree
题目大意：输入一棵二叉查找树和n个数据，把这n个数据放入这颗树中，输出层次遍历序列。解题思路：按照二叉查找树中序遍历的特点（数据从小到大）得到二叉树的中序编号序列并把数据排序后对应插入到节点相应的下标，然后BFS输出层次遍历序列结果。代码如下：#include<iostream>#include<cstdio>#include<fstream>...
2019-02-14 17:09:31
352
原创 1064 Complete Binary Search Tree
题目大意：给你n个数，这n个数可以唯一的构成一个完全二叉查找树，输出这个树的层次遍历序列。解题思路：完全二叉树的节点下标是有对应关系的，假如根节点下标为x，那么左儿子下标就是2x，右儿子就是2x+1。根据这个关系和题目中限制的结点数n可以构建一棵，根编号为1（当然0也可以）节点数为n的完全二叉树，然后得到这个二叉树的中序遍历编号序列。由于二叉查找树的中序遍历序列永远是一个从小到大的递增序列...
2019-02-14 17:01:59
157
原创 1043 Is It a Binary Search Tree
题目大意：给出二叉查找树的节点输入序列，判断这个序列是否为二叉查找树或者镜像（交换左右子节点位置）二叉查找树的先序序列，如果是，输出后序遍历序列。解题思路：按照题目要求构建二叉查找树然后先序遍历得到结果对比即可，为了方便比较两个序列采用vector方便一些，关于镜像二叉查找树只需要写遍历的时候将左右反过来即可。代码如下：#include<iostream>#include...
2019-02-14 16:52:17
160
原创 1106 Lowest Price in Supply Chain
题目大意：给出一棵销售供应的树，树根唯一。在树根处货物的价格为P，然后从根节点开始每往子节点走一层，该层货物价格将会在父亲节点的价格上增加r%。找出总价格最便宜的供应链并统计这样的链有多少条。解题思路：DFS，代码如下：#include<iostream>#include<cstdio>#include<fstream>#include<s...
2019-02-13 22:05:55
168
原创 1079 Total Sales of Supply Chain
题目大意：给出一棵销售供应的树，树根唯一。在树根处货物的价格为P，然后从根节点开始每往子节点走一层，该层货物价格将会在父亲节点的价格上增加r%。给出每个叶节点的货物量，求他们的价格之和。解题思路：DFS搜索即可，太简单了，实在不知道该啰嗦啥。代码如下：#include<iostream>#include<cstdio>#include<fstream&...
2019-02-13 22:00:37
406
原创 1094 The Largest Generation
题目大意：给出一个族谱，找出人数最多的一代，输出这代人的人数和代数编号。老祖宗代数编号为1,。解题思路：BFS遍历树赋值代数编号即可，当然DFS也可以，但是为了方便统计每一代人的人数还是用层次遍历更直观一些。代码如下：#include<iostream>#include<cstdio>#include<fstream>#include<s...
2019-02-13 18:44:48
204
原创 1090 Highest Price in Supply Chain
题目大意：给出树节点的数量，货物价格P，转手一次提高的比率r（就是从父节点到子节点，价格要在原来的基础上上涨r%），然后依次给出n的父节点编号，每个节点编号是第i个节点的父节点，如果是-1说明当前节点是树的总根节点。解题思路：很简单的DFS遍历树，递归计算当前节点价格就好，递归边界是当前节点是叶子节点，然后更新最大价格和供应链数量即可。代码如下：#include&lt;iostream...
2019-02-13 18:40:00
226
原创 1053 Path of Equal Weight
题目大意：给一棵结点数为n，非叶结点数为m的树，然后给一个权值s。接下来给出n个结点的权值（顺序就是结点ID编号），依次给出m个父节点的子节点编号，要求按照从大到小的顺序（按字典序理解）输出路径权值和为s的路径结点。解题思路：这个题用DFS或者记忆化DP都可以写，这里给出DFS的方法，用一个vectot保存路径，关于输出字典序有个小技巧，就是在给父节点输入子节点的时候，可以按照权值大小排序...
2019-02-13 10:56:04
156
原创 1102 Invert a Binary Tree
题目大意：n个节点，依次给出每个节点的左右孩子节点下标，如果没有孩子用‘-’代替，要求从右到左输出层次遍历序列，然后输出翻转二叉树后的中序遍历。解题思路：使用静态链表构建二叉树，标记每一个孩子节点从而找出总的根节点，然后BFS输出层次遍历。中序遍历可以提前交换节点并保存在节点结构体中，正常输出中序遍历即可。代码如下：#include<iostream>#include&l...
2019-02-12 17:42:13
243
原创 1086 Tree Traversals Again
题目大意：用栈的输出表示二叉树的中序遍历，要求输出二叉树的后序遍历序列。解题思路：题目隐含了入栈的顺序就是先序遍历的序列，根据这个构建出二叉树然后后序输出即可。代码如下：#include<iostream>#include<cstdio>#include<fstream>#include<set>#include<cmath...
2019-02-12 16:55:12
403
原创 1020 Tree Traversals
题目大意：给你二叉树结点数和后序，中序遍历结果，要求输出层次遍历的结果。解题思路：二叉树板子题，根据后序中序构建二叉树，然后通过BFS遍历输出层次序列即可。代码如下：#include<iostream>#include<cstdio>#include<fstream>#include<set>#include<cmath&g...
2019-02-12 16:51:01
246
原创 1068 Find More Coins
题目大意：EVa有一些面值的硬币，现在要求支付具体数额的硬币，要求输出需要支付的硬币序列，如果存在多个解就输出字典序最小的，这里的字典序就按照字符串比较时的字典序就可以。解题思路：01背包问题。这里将朴素的背包中的重量和价值合并处理。难点在于记录路径和字典序问题，可以开一个和DP数组维度相同含义的二维数组来记录选择的硬币，由于存在多个解并且要求输出字典序最小，首先将输入的数组从大到小排序，...
2019-02-11 10:33:21
310
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人