QAQ因为绝望地发现好像这些应用都没有题目...所以就专门开了个随笔存题面qwq
谁的孙子最多
给定一棵树，其中1号节点是根节点，问哪一个节点的孙子节点最多，有多少个。（孙子节点，就是儿子节点的儿子节点。）
【输入要求】 第一行一个整数N（N≤100000），表示树节点的个数。此后N行，第i行包含一个整数Ci，表示i号节点儿子节点的个数，随后共Ci个整数，分别表示一个i号节点的儿子节点。
【输出要求】 一行两个整数，表示孙子节点最多的节点，以及其孙子节点的个数，如果有多个，输出编号最小的。
谁的孙子最多II
给定一棵树，其中1号节点是根节点，问哪一个节点的孙子节点最多，有多少个。（孙子节点，就是儿子节点的儿子节点。）
【输入要求】 第一行一个整数N（N≤100000），表示树节点的个数。此后N-1行，第i行包含一个整数Fi，表示i+1号节点的父亲。
【输出要求】 一行两个整数，表示孙子节点最多的节点，以及其孙子节点的个数，如果有多个，输出编号最小的。
链表操作
给定一个N个数的数组，M次操作，每次操作为下列操作之一。求最后的数组。 操作1：在第X个数之后插入一个数Y。 操作2：删除第X个数。
【输入要求】 第一行两个整数N，M（N，M≤100000）含义见试题描述。 第二行N个整数，表示原来的数组。 接下来M行，每行第一个数OPT，表示操作类型。 对于操作1，接下来两个数X，Y，含义见题面描述，保证0≤X≤当前数的个数，若X=0，表示在数组开头插入。 对于操作2，接下来一个数X，含义见题面描述，保证1≤X≤当前数的个数。
【输出要求】 输出若干个数，表示最后的数组。
数组操作
今有N个数组，初始时，N个数组均为空。共有M次操作，每次在第X个数组中加入数字Y。问最终各数组中有多少数，并将它们排序输出。
【输入要求】 第一行两个整数N、M（N≤100000，M≤300000）。 接下来M行，每行两个整数X、Y，含义见试题描述。（1≤X≤N，Y≤10^9）
【输出要求】 共N行，第i行第一个数SUM，表示第i个数组数的个数，接下来SUM个数，为排序之后的数组。
排序
给定N个数组，要求先对这N个数组分别进行排序，然后再根据N的数组的字典序对这N个数组进行排序。输出排序的结果。
【输入要求】 第一行一个整数N，表示数组数。 接下来N（N≤1000）行，每一行先包含一个整数SUM（SUM≤1000），表示数组的大小，接下来SUM个整数，表示数组中的一个元素。
【输出要求】 共N行，每行表示一个数组。
序列翻转
给定一个N个数的数组，M次操作。每次操作将数组的一段翻转，求最后的数组。
【输入要求】 第一行两个整数N，M（N，M≤1000）含义见试题描述。 第二行N个整数，表示原来的数组。 接下来M行，每行两个整数X，Y（1≤X≤Y≤N），表示翻转区间[X,Y]。
【输出要求】 一行N个整数，表示操作后的数组。
RANDOM
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成"去重"与"排序"的工作。
输入要求 第1行为1个正整数，表示所生成的随机数的个数：N( N≤100) 第2行有N个用空格隔开的正整数，为所产生的随机数。
输出要求 第1行为1个正整数M，表示不相同的随机数的个数。 第2行为M-1个用空格隔开的正整数(行尾没有多余的空格)， 为从小到大排好序的不相同的随机数。
SUMX
考虑一组n个不同的正整数a1,a2,...,am，它们的值在1到1000000之间。给定一个整数x。写一个程序sumx计算这样的数对个数(ai,aj)，1<=i<j<=n并且ai+aj=x。
输入要求 标准输入的第一行是一个整数n(1<=n<=1000000)。第二行有n个整数表示元素。第三行是一个整数x(1<=x<=2000000)。
输出要求 输出一行包含一个整数表示这样的数对个数。
知识点及提示 不同的和为13的数对是(12, 1), (10, 3)和(2, 11)。
DEC
给定N个数Ai，以及一个正整数C，问有多少对i,j，满足Ai-Aj=C。
输入要求 第一行输入两个空格隔开的整数N和C 第2至N+1行每行包含一个整数 Ai
输出要求 输出一个数表示答案。
买蛋糕2
今天是路路的生日，生日蛋糕自然是少不了。路路的朋友们一起去蛋糕店来买蛋糕，可是等一行人到了蛋糕店之后，发现那里是人山人海啊-_-。这下可把店家给急坏了，因为人数过多，需求过大，所以人们要等好长时间才能拿到自己的蛋糕。由于每位客人订的蛋糕都是不同风格的，所以制作时间也都不同。老板为了最大限度的使每位客人尽快拿到蛋糕，因此他需要安排一个制作顺序，使每位客人的平均等待时间最少。这使他发愁了，于是他请你来帮忙安排一个制作顺序，使得每位客人的平均等待时间最少。
输入要求 输入有两行。第一行是一个整数n，表示有n种蛋糕等待制作（1≤n≤100）。 第二行有n个数，第i个数表示第i种蛋糕的制作时间。
输出要求 输出包括一行，有n个整数，整数间用空格隔开， 行末没有空格，是蛋糕的制作顺序， 每个数即是蛋糕的编号。
count
有n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
【输入要求】 输入包含n+1行： 第1行是整数n，表示自然数的个数。 第2到n+1行每行一个自然数。
【输出要求】 从小到大输出若干行，每行为一个数字和它出现的次数。
【解题提示】n≤300000
drawer
期末考试即将来临，小T由于同时肩负了学习、竞赛、班团活动等多方面的任务，一直没有时间好好整理他的课桌抽屉，为了更好地复习，小T首先要把课桌抽屉里的书分类整理好。小T的抽屉里堆着N本书，每本书的封面上都印有学科名称，学科名称用一个字符串表示，如语文学科的书封面上都印有“chinese”。现在，你的任务是帮助小T找出哪个学科的书最多？
输入数据 入文件第一行包含一个自然数N（0＜N≤1000）表示抽屉中书的总数。接下来N行每行包含一本书的学科名称，学科名称是一个长度不超过15的由小写英文字母组成的字符串。
输出数据 出文件仅有一行包含一个字符串，表示最多的那种书的学科名称。数据保证答案一定是唯一的。
exclusive
有这样的一个集合，集合中的元素个数由给定的N决定，集合的元素为N个不同的正整数，一旦集合中的两个数x,y满足y = P*x，那么就认为x,y这两个数是互斥的，现在想知道给定的一个集合的最大子集满足两两之间不互斥。
【输入要求】 第一行给定两个数N和P。 接下来一行包含N个不同正整数ai。
【输出要求】 输出一行表示最大的满足要求的子集的元素个数。
【解题提示】 1≤N≤10^5, 1≤P≤10^9，1≤ai≤10^9
match
n个不同的字符串，每个字符串对应一个数字。q次询问一个字符串对应什么数字。
【输入要求】 第1行n，q。 第2到n+1行，每行一个字符串和一个数字，中间用一个空格隔开。 第n+2到n+q+1行，每行一个询问的字符串。
【输出要求】 q行，每行一个数字
【解题提示】 n,q≤20000 每个字符串的长度≤30
game
给出了N个单词，已经按长度排好了序。如果某单词i是某单词j的前缀，i->j算一次接龙(两个相同的单词不能算接龙)。 你的任务是：对于输入的单词，找出最长的龙。
【输入要求】 第一行为N。以下N行每行一个单词（由小写组成），已经按长度排序。
【输出要求】 仅一个数，为最长的龙的长度。
【解题提示】 N≤50000 每个单词长度≤50
double
n条信息，一条信息包括一个字符串s和一个整数x，表示名字为s的奶牛获得了一棵质量为x的草。一头奶牛可能获得不止一棵草，但不超过十棵草。 q次询问一头奶牛获得了哪些质量的草，按输入顺序先后输出。
【输入要求】 一行一个整数n。 n行每行一个字符串s和一个整数x，以空格隔开。 一行一个整数q。 q行每行一个字符串s，表示询问的奶牛的名字。
【输出要求】 对于每个询问输出若干行，每一行一个整数，表示此奶牛s获得的草的质量，按输入顺序输出。若s一棵草都没有，则不输出。
滑动窗口
给出一个长度为n的数组(n<=1000)，有一个可移动的长度为k的窗口，从最左端开始每个时刻向右移动一格，你的任务是输出每个时刻窗口内最大及最小的数字。
Window position Maxvalue
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
输入要求 一行包含四个整数n,k,p,q，满足a[0]=1,a[i]=(a[i-1]*p+i) % q
输出要求 一个数值，表示每个时刻窗口内最大值的和。
advertisement
最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。 我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，且0<Hi<=10^8，并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。
输入要求 第一行：一个数n (n<=1000)。 第二行：n个数,给出这n个建筑物。
输出要求 第一行：一个数ans，表示最大面积。 知识点及提示:一个高为4，长度为6的广告牌。
最大全1子矩阵
输入一个n*m的01矩阵，求最大全1子矩阵的面积。
输入要求 输入第一行有两个用一个空格隔开的正整数n, m表示矩阵的大小。 接下来n行，每行m个01字符，每两个字符间用一个空格隔开。
输出要求 输出一个整数，表示最大面积。
知识点及提示 n, m <= 10
懒羊羊吃草
懒羊羊也有存储粮食的习惯。每当他存储一份粮食时，他会专门拿出一个筐来存放。因此，他的仓库里有很多很多筐的青草。而我们的懒羊羊又是一个经常馋嘴的小羊，每当他想吃草时，就会从仓库里找出数量最少的一筐草，把它吃掉。可是懒羊羊因为草吃得太多了导致大脑运转缓慢，所以他不得不向你请求支援，帮他找出他应该吃数量为多少的青草。
输入要求 第一行为一个正整数n，表示懒羊羊一共进行了n次操作(2<=n<=1000000) 第二行至第n+1行每行表示一个懒羊羊的操作，当这行形式为 单独一个字符'q' 时，表示懒羊羊肚子饿了，要吃掉仓库里当前数量最少的那份青草；当这行形式为一个字符'i' 和一个整数k时，表示懒羊羊将一份数量为k的青草存入了仓库，'i'和k之间用空格隔开。 输入数据保证每次询问时仓库里都有草可吃且所有操作中懒羊羊至少会吃一次草。
输出要求 每当输入为'q' 时， 输出懒羊羊当前吃掉的那份青草的数量是多少。
合并果子
在一个果园里，多多已经将n个果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入要求 输入包括两行，第一行是一个整数n（1 <= n <= 100000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。
输出要求 输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
丑数
题目描述
素因子都在集合{2, 3, 5, 7}的数称为ugly number。
求第n大的丑数。 n<=100000。BlackBox
Black Box是一种原始的数据库.它可以储存一个整数数组,还有一个特别的变量i.最开始的时候Black Box是空的,而i等于0。这个 Black Box要处理一串命令.命令只有两种：ADD(x): 把x元素放进Black Box; GET:i加1,然后输出 Black box 中第i小的数.记住：第i小的数,就是 Black Box里的数的按从小到大的顺序排序后的第i个元素.例如我们来演示一下一个有11个命令的命令串.
序号 操作 i 数据库 输出
1 ADD(3) 0 3
2 GET 1 3 3
3 ADD(1) 1 1,3
4 GET 2 1,3 3
5 ADD(-4) 2 -4,1,3
6 ADD(2) 2 -4,1,2,3
7 ADD(8) 2 -4,1,2,3,8
8 ADD(-1000) 2 -1000,-4,1,2,3,8
9 GET 3 -1000,-4,1,2,3,8 1
10 GET 4 -1000,-4,1,2,3,8 2
11 ADD(2) 4 -1000,-4,1,2,2,3,8
输入要求 输入包括两行，第一行是一个整数n（1 <= n <= 100000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。
输出要求 输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。