给定一些喜欢的颜色（整数）还有一些颜色的布条，布条是有顺序的。选择布条必须按照布条自己的顺序，排列布条需要按照喜欢颜色的顺序来排列，也就是说对每个布条选择要还是不要，最后按照原来布条的把要的布条连接起来形成每种要的布条的先后顺序必须符合原来喜欢布条的顺序，求最后最长能拥有多少个布条。 一个显然的动态规划。喜欢的颜色可以自己重新编号，表示喜欢的第i种颜色。dp[x]表示目前以喜欢的第x种颜色结尾的最长选择的布条数。  当然第i块布条恰好是第x种颜色时，我们可以倒推之前选出的是哪种颜色布条结尾。注意之前结尾的必须是y <= x, 所以dp[x] = max(max(d...

给定二叉搜索树或者其镜像的前序遍历序列，先判断是否可能，如果可能，求它的后序遍历序列。 简单题，就是个二叉树还原问题。我们从前序遍历开始还原出整个树，还原方法是递归的—— 就是对当前节点，根据左右子树信息，可以确定它的值应该在一个范围内。我写的函数make1, make2就是从二叉搜索树，或者其镜像还原出它本身,参数p1,p2的值决定了当前这个节点应该在它父亲的左边还是右边，递归下去就好了。 我们可以用数组代替指针，尽管节点left right仍然是指针（地址），但它指向的是一个真正存在的位置，而不是我们new出来的空间，这样就不用 delete了。make1和ma...

简单题，给定54张牌，每个数代表一张牌，然后有一种操作关系，每次操作告诉你把现在第i张牌放在第j=p[i]个位置,这样不断操作k次，问最终结果。直接模拟即可，注意点主要就是最后要把数字还原成牌的表示。而且k不大，直接循环操作即可。 代码： #include <cstdio> #include <string> #include <cstring> using namespace std; const char *c = "SHCD"; char temp[54][4], card[54][4]; int a[54]; ...

简单题，找到第一个只出现一次的数，因为数据范围不大[1-10000]，所以可以直接放到数组下标里。本质就是用数组代替hash，或者叫做计数排序。 代码： #include <cstdio> #include <cstring> #include <string> using namespace std; int have[10004]; int a[100005]; int main() {     int n;     scanf("%d",&n);     for (int i = 0; i < ...

最长回文子串。 长度不大，1000，可以采用暴力方法解决。时间复杂度O(n2)——即选取中心位置——可能是一个字符，也可能是两个字符之间，看向左和右能延伸的最大长度。相当于枚举所有长度位奇数和偶数的回文串。 还有注意字符串有空白，如果用C输入的话要用gets，不能用scanf。 代码： #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; char s[1024]; int main...

题目本身不难，给定一些课程，还有哪些学生选了这个课，最后查询某些学生上了哪些课。 本来就是一个图的邻接表输出的问题，但是PAT在这个问题上卡时间和卡内存非常紧——所以用了一些诡异的技巧。 （1） 学生id是3个大写字母加一个数字。所以我们可以把这4个字符作一个26进制数。 （2） 2500门课程，每个课程id在1-2500以内，所以我可以用12bit（0-4095）表示这个课程。把（1）的数左移动12位，低12位表示这门课程。 （3） 于是((1) << 12) | (2) 这个整数表示一条边，也就是(1)这个学生选了（2）这门课程。 （4） 把（...

简单题， 每个人有id, name, grade 三个指标，输入一个维度(1-3)，按照这个指标排序。id肯定不同，如果发现要排序的那一维相同，就让id小的在前。 C++ STL algorithm库里的sort函数，只要给定cmp函数，就能按照它排序（返回true表示小于），所以这个题无非就是实现3个cmp函数而已，id的最简单，其他两个需要在相等的时候靠id区分。 建议使用C的scanf , printf，否则会超时。 代码： #include <cstdio> #include <cstring> #include <s...

超级麻烦的模拟题。 有乒乓球桌子，每个人来了要说玩多长时间。桌子有普通桌子和VIP桌子。可以认为普通人和VIP在两个不同的队列里，有空桌的话VIP优先，并且VIP优先进入VIP的桌子。还有一些限制每个人不能玩超过两个小时而且没有VIP的时候，普通人也可以用VIP的桌子，VIP如果没有VIP桌子可以用普通人的桌子——总之很多规则，最后看一下每个人玩多久，每个桌子支持了多少人。 我们用事件驱动的方法。 事件包括 ： （1） 时间 （2） 人的id或者桌子的id （3） 人的id表示人来了，桌子的id表示桌子腾空 我们看一下如何处理这些事件 ...

简单题，给一些人的性别和成绩，求男生最低分和女生最高分的成绩差。 直接循环找最大值和最小值就可以了——注意不存在的时候的输出: Absent还有NA。 #include <algorithm> #include <cstring> #include <string> #include <cstdio> using namespace std; string name[2], id[2]; int score[2] = {1000,-1000}; char s[100],p[100]; int main() { int n;...

    给定一个无向图，一个点表示有无穷多自行车的车管所，每个点有一定的车，每个点的容量都相同，如果有的点车辆少于容量的一半的话，旧需要从车管所运送自行车过去，顺便把经过点多余的车运回去。给定缺车的节点，需要考虑几个指标： （1）最短路 （2）需要的运过去车最少 （3）需要运回来的车最少 分析 ： 图的节点不多，可以直接用临接矩阵。求最短路可以同时记录路径，关键是最短路有多条，每条都得记录，我用的vector数组表示每个点的前一个节点的可能性——求出最短路在枚举所有最短路，这个就dfs了，好在数据不大，暴力枚举能过。我求最短路是正着求的，其实可以只求到目的地就行...

给定一个数n和一个b，问n在b进制下是否是回文数。 分析： 没什么好说的——就是用n不断地除以b，把结果放到数组里，然后判断回文就行了。输出结果地时候别忘记倒序。还有输入为0的时候，输出也是0。 代码： #include <cstdio> #include <string> #include <cstring> #include <vector> using namespace std; bool is(vector<int> &a) {     for (int i = 0, j = a.si...

不是难题。其实就是按照name, title, publisher, key word和year建立倒排索引就行了。具体倒排索引可以用map<string, set<string> > 代替。key就是那5种类型，value是符合要求的书的集合。题目一点也不难，可以算做模拟题，就是问什么，从倒排索引里把要的东西拿出来输出就可以了。 注意事项： 别忘了输出query…… 代码： #include <cstdio> #include <map> #include <string> #include <...

就是排序问题，每个人有一个id (13位数字)，地区和分数。地区相同的是连续读入的。我们可以把地区相同的按照分数排序，然后算出在地区里的排名local_rank, 注意分数相同的人名次也要相同。这样所有地区都读完之后，每个地区里的人都local_rank都算好了，再总体排序。排序后，和地区算名词类似，分数相同的人名次也要相同——这时是靠id大小决定谁先输出了，所以关键是写cmp函数。 地区排名： 直接按分排，相同分数可以不做区分，因为最后还要再排一次 全局排名： 按分排，分相同的话，id小的在前面。 所有名次都是排序后算出来的。 代码： #inclu...

简单题， 给定一个整数（20位），问他的二倍是否和它组成的数字相同。 由于整数已经超过了long long, C++用数组模拟大整数加法，java可以直接使用bigInteger。 数组模拟整数加法，就是每个数组存一位数，就像我们笔算加法一样，注意进位就可以了。然后数组里面每一位就是结果。 比较数字显然可以排序，另外一种办法是记录每种数字（0-9）出现的次数之差，最后如果全0，显然就是组成的数字相同了。 代码： #include <cstdio> #include <cstring> #include <string> ...