和1089差不多……也是判断插入排序，另外一种排序是堆排序。关于插入排序，和1089判断方法相同，不过这次我没有对每个前i项单独排序，而是模拟了插入排序的过程，直到找到和输入相等的时候，再继续到第一个不同的时候。 对于堆排序也是模拟，每次deleteMax,把最大的放入堆的最后，并且把堆的size减小1，这样每次后缀都是排好顺序的，关键是实现堆排序的down函数，就是把某个位置（可能）不符合要求的下移动，维护堆的性质。比1089还是难一些，因为堆排序相对难写。 代码： #include <cstdio> #include <cstring&...

PAT的链表题，表示链表的方法很诡异，类似的表示还有1052， 1074。也不难，本题给定一个存储整数的链表，只保存每种绝对值第一次出现的节点，同一个绝对值第二次及以后的出现都扔掉，保留的节点和扔掉的节点分别组成两个小链表。 链表存放整数的绝对值不超过10000，所以可以用bool数组或者bitmap保存某个绝对值在之前是否出现过。 不知道有没有极端情况，输入的链表就是个空的…… 总之，我们可以先新建立两个表头h1, h2 和表尾t1, t2，初始都是空的，表示我们最后保留的链表和过滤掉的链表。链表的优势就是对每个节点可以单独折腾…… 我们对原始链表里每个节点...

简单题，求n的连续约数，比如n = 630 = 3 * 5 * 6 * 7,  而5,6,7是连续的，所以输出5 6 7。抽象描述是，给定n，求n % (start * (start + 1) * (start + 2) * ... * (start + len - 1)) == 0的len最长的start。如果有多个start要最小，并且1不能算。 先简单考虑一下，len最长有多长？ 给定的范围是int,我们发现12!是不超过int的最大值，所以len最大才是11,即从2乘到12。（其他的11个数乘积比这个还要大）。 如果start >= sqrt(n), 则l...

稍微有点麻烦的模拟，模拟停车场。每条记录是 时间 hh:mm:ss, 车牌号， in/out。 表示车的出入记录。查询一些时间点的车数，求停留时间最长的车（可能很多）。 关键问题是，每辆车的记录可能有问题，比如同一辆车可能有很多连续的in，或者很多连续的out。原则是一辆车很多连续的in只考虑最后一个in，然后只考虑它后面第一个out和它匹配。简单地说很多连续的in最后一个有效，很多连续的out第一个有效。 时间的处理，hh:mm:ss转变为秒数hh * 3600 + mm * 60 + ss, 因为数据都是一天的。我们把记录按照车牌号排序——因为输出停留最长时间的车也是...

简单题，给定一棵树——树是按照父子关系给出的，求节点个数最多的那层有多少个节点——保证这层是唯一的。并且认为根的层数为1。 因为数非空，并且规定了根是1号，我把id都减去1之后，就认为第0层是根。用d[]表示每个节点的层数，即深度。用num[]表示每层的节点数。别忘记初值d[0] = 1, num[1] = 1。 读入树结构的时候，我们记录每个节点x的父亲y，即f[x] = y。 则d[x] = d[y] + 1。我们dfs求出每个节点的深度——注意如果之前求过，递归可以直接返回，所以计算深度是O(n)的，相当于dfs整个树。我用了全局变量，没求过的深度暂且认为0。当然也...

我出的题——也是简单题。数PAT的个数。 如果我们知道这个A之前有多少个P，则那些P和这个A一起可以构成这么多个PA。 如果我们知道这个T之前有多少个PA，则那些PA和这个T一起就可以构成这么多个PAT。 所以就是动态统计P, PA, PAT的个数。 遇到P, 则P的个数加1。 遇到A，则PA的个数加P的个数。 遇到T，则PAT的个数加PA的个数。 注意别忘记每次加法后取余数。 代码： #include <cstdio> #include <cstring> #include <string> #i...

简单题，给定字符串1和字符串2，看一下字符串1是不是包含了字符串的全部字符——种类和个数，如果完全包含，则输出字符串1还多了几个字符，如果不完全包含，输出字符串1还需要加上几个字符才能完全包含字符串2。字符串只包含62种字符——26个大小写字母和10个数字。自然我们可以用一个数组统计字符串1里面每种字符出现的次数，数组可以直接开到256，当然开到62也够用。 然后再把字符串2中的字符减掉，如果出现负数就是不完全包含，负数绝对值（相反数）的和，就是字符串1还需要加多少个字符。如果不出现负数，所有数的和就是字符串1多余的字符——其实这时就是两个字符串的长度差。 代码： #...

给定一个脑平面图，其实是一个分层的长方体图，每一层是一个长方形，1表示有问题，0表示没问题。先求有问题的连通分量，如果size大于一个阈值就记入总的有问题的size。最后求总体有问题的size是多少。 关键是规模很大，dfs似乎会堆栈溢出或者超时，所以改用bfs，写起来没有dfs舒服——要自己搞队列。60层，每层是1286 ＊ 128的，三个维度不同。可以压入到一个int里，最后一维占8bit，中间那维我占了12bit,其实11bit就够了，我只是觉得后两维占20bit比较整……，所以还是用位运算压入一个int代替存放3个不同的int…… 代码： #include ...

和1079很像，简单地说就是根节点有个价格，孩子节点总是在父亲节点的价格上加一个比例，求最贵的节点——显然是个叶子。 题目输入给了每个节点i的父亲f[i]， 除了根节点外，那么i的价格实际上就是a[f[i]] * r  (r是一个大于1的数），因此我们只要dfs计算就可以了，当然已经计算过的结果不要重复计算，我用了-1.e6表示负无穷，然后get一下每个节点的价格选出最大的就可以了。简单题。 代码： #include <cstdio> #include <cstring> #include <string> using names...

给定一个整数数组，问当前的撞状态是插入排序造成的还是归并排序造成的。 题目给定了插入排序和归并排序的过程，特点如下： （1） 插入排序，每次一定是前m项有序。 （2） 归并排序，每次一定是长度为2^k的段有序。 因为n不大（才100），所以我没有真正模拟这两个排序过程。 对于插入排序，我每次调用sort(c, c + m) 对于归并，我每段单独调用sort，注意长度可能有尾巴。 直接暴力排序比较就好了。 注意点： 不是找到第一个相同步骤就行了，而是应该找到第一个不同的步骤，因为有时候可能目前这个状态能在某种排序下面持续不变，例如插入排序时，输...

和1081很像，多了一些运算， 仍然是直接做，通分，别忘记最大公约数。还有输出上注意负数要加括号。 代码： #include <cstdio> #include <cstring> #include <string> using namespace std; char s[111]; long long gcd(long long x,long long y) {     return y?gcd(y, x % y):x; } void print(long long x,long long y) {     if (y < ...

又是最短路，dijkstra算法的变种。 （1） 记录最短路条数， 更新的时候： 用k更新i的时候，有两种情况 如果最短路长度相等，num[i] += num[k] 如果最短路更短 num[i] = num[k] （2） happiness 和 bypass 这两个没的说，如果要更新的话 happiness[i] = b[i] + happiness[k] bypass[i] = bypass[k] + 1 所以只是在更新上做手脚，别忘记记录pre[i] = k，以方便倒着还原出路径来。 代码： #inclu...

简单题，就是排序…… 每个人有三个属性： 年龄，财富，姓名。 题目要求： 输出一个年龄段范围内财富最多的m个人。 主要是查询有多组，所以我们不能反复排序。但是m <= 100，所以我们把每个年龄财富财富最多的（至多）100个人保存下来就可以了。最多10^5人，查询最多10^3个，所以除去排序，复杂度不过是10 ^ 8 ，可以接受。 排序要排两次： 先按照 年龄、 财富、 姓名的顺序排序，这样年龄相同的人在一起，并且财富是由大到小的，我们对每个年龄的人取财富前100，存起来，因为无论怎么查询，后面的人都不会被输出——最多100人嘛。而且根据题意...

简单题，求n个字符串的最长公共后缀。 直接做就行，看一下倒数第几个字符开始不相等，注意输入n后有个回车，建议先gets掉。 #include <cstdio> #include <cstring> #include <string> using namespace std; char s[102][300]; int len[102]; int main() { int n;     scanf("%d",&n);     gets(s[0]);     for (int i = 0; i < n; ...