csx0987-CSDN博客

原创 pat1151 LCA in a Binary Tree

题意：输入一颗二叉树的中序，先序，q个询问，每次询问两个节点的lca。思路：求dfs序，st表维护dfs序中的高度，map映射一下每个值对应的节点序号，rmq求lca。预处理查询代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>...

2018-09-10 10:27:26 602

原创 pat1150 Travelling Salesman Problem

题意：输入一个图，输入q条路径，判断每条路是否是简单TS环，TS环，还是不是TS环。思路：遍历ifelse就好。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include &...

2018-09-10 08:11:50 452

原创 pat1149 Dangerous Goods Packaging

题意：给出n对不能放在一起的货物，q个询问，每次询问一些货物是否能放在一起。思路：用set存一下不能放在一起的货物，然后遍历即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#...

2018-09-10 07:09:59 461

原创 pat1148 Werewolf - Simple Version

题意：2个狼人，其它都是好人，一个好人说谎，一个狼人说谎，求两个狼人。思路：枚举狼人，最后求说谎的两个人是否一个是好人一个是狼人。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>...

2018-09-10 06:58:50 1517

原创 pat1049 Counting Ones

题意：给一个数N，计算从0到N的所有数中数位1的个数，。思路：数位dp，定义dp[i][j]表示从0到以i为首位长度为j后位全是0的区间有多少数位1。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algor...

2018-09-07 12:52:38 172

原创 pat1095 Cars on Campus

题意：有一些车的停放记录，给出K个询问时间，每个询问查询当前时刻有多少车停放，停放记录只有相邻两个进出记录有效，最后输出停放时间最长的车以及停放时间。思路：先把停放记录排序，选出相邻的合法记录，遍历一遍即可得出最长的停放时间及车辆，询问按照从小到大，所以也只要遍历一遍就能得到。代码#include <iostream>#include <cstdio>#i...

2018-09-06 11:27:53 168

原创 pat1094 The Largest Generation

题意：输入一颗树，问那个高度的节点数量最多，并输出节点数以及高度。思路：dfs计算高度，计数一下即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <ve...

2018-09-06 09:47:09 153

原创 pat1093 Count PAT's

题意：给一个字符串问这里面有多少'PAT'的子串。思路：扫一遍记录P的数量，PA数量和PAT数量。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace ...

2018-09-06 09:20:26 163

原创 pat1092 To Buy or Not to Buy

题意：Eva想要一串珠子，每个珠子有一个颜色，现在有一串珠子问Eva想要的珠子颜色在这串上是否都有，缺少则输出缺少多少个，多余则输出多余多少个。思路：map计数即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include &...

2018-09-06 08:53:25 120

原创 pat1099 Build A Binary Search Tree

题意：输入一颗排序二叉树的结构，再输入一个序列，把序列中的值放到二叉树里，最后层序输出。思路：建树，排序，中序，层序。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#includ...

2018-09-05 14:03:16 172

原创 pat1098 Insertion or Heap Sort

题意：输入一个序列，输入它排序过程中的一个样子，判断用的是插入排序还是堆排序。并输出下一步。思路：如果是插入排序的话，那前部分就是有序的，找到第一个无序的位置，从该位置到结尾应该和原本的序列保持一致。否则为堆排序，堆排序的话，那从尾端开始的一部分应该是完全排序好的状态，找到第一个错误的位置，就能找到堆调整的区间，调整一下就好。代码#include <iostream>#...

2018-09-05 13:50:49 183

原创 pat1097Deduplication on a Linked List

题意：把链表中的重复部分拆分出来，相对位置不变。思路：链表的基本操作。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include &...

2018-09-05 11:40:45 245

原创 pat1103 Integer Factorization

题意：输入N，K，P，问是否存在K个数使得每个数的P次方之和等于N，多种可能输出，所有数的和最大的一种，若还有多种输出非降序的最大的一种。思路：dfs，减枝。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <a...

2018-09-05 03:55:42 214

原创 pat1102 Invert a Binary Tree

题意：写出反转二叉树的层序和中序。思路：直接写。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <set>#include <queue&gt

2018-09-05 02:49:41 142

原创 pat1101 Quick Sort

题意：给一个序列，输出可以在快排中作为中轴的点。思路：预处理每一个位置之前的最大值，之后的最小值。ps：样例应该是能作为中轴的点为0，如果在输出点的数量后不多输出一行空行就会错。该题的对拍没做好。代码#include <iostream>#include <cstdio>#include <cstring>#include <alg...

2018-09-05 02:33:51 147

原创 pat1107 Social Clusters

题意：n个人，每个人有个兴趣列表，有同样的至少一个兴趣的人在一个圈子里，求有多少个圈子，并把圈子按照人数从大到小输出人数。思路：并查集维护即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmat...

2018-09-04 21:33:22 212

原创 pat1106 Lowest Price in Supply Chain

题意：给出一个供应链，一个根，·每经过一个节点售价增加百分之r，求最少要花多少钱从零售商得到商品，并求出有多少个零售商提供最低的价格。思路：bfs。代码#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstr...

2018-09-04 20:18:18 158

原创 pat1105 Spiral Matrix

题意：输入一些数把他们放到m*n的矩阵里，按照环形从大到小排放。思路：for一下求出插值最小且m大于等于n的矩阵，然后优先队列维护输入的树即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorith...

2018-09-04 18:52:38 183

原创 pat1104 Sum of Number Segments

题意：题意看不懂，根据样例猜了一下，给一个序列，算出所有子序列的和。思路：第i个数的贡献为i * (n - i + 1) * a[i]。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm&gt...

2018-09-04 18:20:11 113

原创 pat1111 Online Map

题意：输入一个图，边权包括路径长度，要消耗的时间。输出最短路径，多条则输出耗时最短的，输出耗时最多的路径，多条则输出经过点最少的。思路：spfa跑两下就好。代码#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <...

2018-09-03 13:07:55 949

原创 pat1110 Complete Binary Tree

题意：输入一颗二叉树，判断是否是完全二叉树，是输出最后一个节点，不是输出根。思路：建树，层序遍历。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <set&...

2018-09-03 11:13:19 221

原创 pat1109 Group Photo

题意：输入N，K，N代表N个人，K代表排成K行，输入一些人的名字和身高，每行按照中间最高，先左后右两边依次非增。思路：普通模拟。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>u...

2018-09-03 10:44:38 144

原创 pat1108 Finding Average

题意：输入n个字符串，选出合法的数字字符串，求平均值。思路：ifelse判断一下合法字符就好。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace st...

2018-09-03 10:00:46 274

原创 pat1115 Counting Nodes in a BST

题意：输入一颗bst，输出最后两层的节点数，及其节点数的和。思路：建树，dfs求深度，层序求节点数。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <que...

2018-09-02 15:45:37 123

原创 pat1114 Family Property

题意：输入n条信息，每一条表示一个人的id，父母id，孩子id，多少套房产，总面积。按照家庭平均房产从大到小输出一个家庭的最小id编号，人数，平局房产套数，平均房产面积。思路：并查集维护家庭关系，最后扫一下，排个序就好。代码#include <iostream>#include <cstdio>#include <cstring>#inclu...

2018-09-02 15:23:17 152

原创 pat1113 Integer Set Partition

题意：给n个数，把这个数列划分成两个不相交集合，要求两个集合元素数之差的绝对值最小，两个集合元素和之差的绝对值最大。思路：排序，从中间划分即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorith...

2018-09-02 13:17:47 114

原创 pat1112 Stucked Keyboard

题意：输入k，代表坏的键会连续输入k次，输入一个字符串s，问哪些键坏了，并输出正确的字符。思路：只要之前或之后出现的字符次数不会被k整除就好。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath...

2018-09-02 13:00:31 175

原创 pat1119 Pre- and Post-order Traversals

题意：给出先序，后序，问二叉树是否唯一，输出中序。思路：根据先序确定当前树的根，若二叉树唯一，则可以根据先序把后序划分成两个部分，第一部分为右子树，第二部分为左子树。若不唯一，怎只能划分成一个部分，作为左子树或右子树都行。代码#include <iostream>#include <cstdio>#include <cstring>#incl...

2018-09-01 11:49:37 162

原创 pat1118 Birds in Forest

题意：N张画，每张画里面有些小鸟，认为在同一张画里的小鸟在同一颗树上，问有多少颗树，判断两只小鸟是否在一颗树上。思路：并查集裸题。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>...

2018-09-01 09:31:00 251 2

原创 pat1117 Eddington Number

题意：定义“Eddington number”为最大的N满足，所有数中超过N的数有N个。思路：从小到大排序，从后向前扫就好。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>usi...

2018-09-01 09:15:10 167

原创 pat1116 Come on! Let's C

题意：给出游戏排名，第一名得到神秘礼物，素数名得到小黄人，其它得到巧克力，给出K个询问，输出对应的礼物。思路：map维护名次，素数打个表，set维护是否询问过。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include ...

2018-09-01 08:55:12 171

原创 pat1123 Is It a Complete AVL Tree

题意：输入一个插入顺序，构造avl树，层序遍历输出avl树，并判断该树是否是一颗完全二叉树。思路：avl树的构造，递归计算高度，子树高度大于等于2旋转，旋转分zig,zag,zig-zag,zag-zig，可以统一由祖先，父亲，儿子的关系写出，判断完全二叉树根据定义，按层序遍历的时候出现了空节点再出现非空节点就不是完全二叉树。ps：记错了完全二叉树的定义，还以为是每个节点只有两个孩子或者没...

2018-08-31 11:54:28 155

原创 pat1122 Hamiltonian Cycle

题意：输入一个图，输入q个询问，每个询问给出一条路径，问这条路径是否是哈密顿回路。思路：记录边，把给的路径走一遍就好。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#includ...

2018-08-31 09:22:25 232

原创 pat1121 Damn Single

题意：给出一些cp，给出参加派对的人，问在派对中谁是没有cp的。思路：存储cp，用set维护参加派对的人，遍历cp对，把同时在派对的人删除。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath...

2018-08-31 09:01:11 169

原创 pat1035 Password

题意：输入名称和密码，用'@'代替'1',‘%’代替‘0’，‘L’代替‘l’，‘O’代替‘o’。思路：直接做。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using name...

2018-08-30 09:49:08 95

原创 pat1127 ZigZagging on a Tree

题意：输入一颗树的中序遍历和后序遍历，按层按照一层从左到右一层从右到左交替输出。思路：建树，得到层序，每个点记录一下层次，遍历层序交替倒置序列即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cm...

2018-08-30 09:32:53 180

原创 pat1126 Eulerian Path

题意：给一个无向图，判断这个图是欧拉图还是半欧拉图还是不是欧拉图。思路：并查集判断是否只有一个联通分量，记录每个点的度数。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>usin...

2018-08-30 08:47:54 159

原创 pat1125 Chain the Ropes

题意：n条绳子，现在每次取两条连起来再对折看作一条新绳子，不断重复知道最后剩下一条绳子，求这个绳子的长度。思路：和哈夫曼编码差不多，每次选当前最小的两个合并，用优先队列维护。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#i...

2018-08-30 08:29:10 165

原创 pat1124 Raffle for Weibo Followers

题意：微博抽奖，列出follow的人，给出起始点，以及每隔多少人抽一个，抽到重复的依次向后。思路：模拟即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include &lt...

2018-08-30 08:18:08 128

原创 pat1131 Subway Map

题意：给出N条地铁线路，Q个询问，每个询问输入起点和终点，求最短路径，若有多条输出换乘最少的一条。思路：最短路径的题目，就是输出麻烦点，跑一下dijkstra即可，每次维护的出了当前最短路还要维护当前最短换乘，更新的时候记录前驱以及当前站在哪条线路上。代码#include <iostream>#include <cstdio>#include <cs...

2018-08-29 10:34:37 206

空空如也

空空如也