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

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), 则len = 1，因...

稍微有点麻烦的模拟，模拟停车场。每条记录是 时间 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。当然也可以从根直接d...

我出的题——也是简单题。数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> #include &lt...

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

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

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

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

和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 < 0) {   ...

又是最短路，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，以方便倒着还原出路径来。      代码：  #include <cstdio&g...

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

简单题，求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; ++i) {...