以下编程题均为博主在2023年投递实习和秋招过程中的笔试真题（共61道编程题），为避免不必要的麻烦，不对题目的来源进行说明。

3.4

• 第一题

  题意：给一个数组（n≤2e5），求数组内任意数对的最大差值。即对任意i<j，求最大的x[j] - x[i]。

  题解：处理一下前缀最小值。

• 第二题

  题意：给一个数组（n≤2e5，有正数和负数）和常数k。求长度<=k的连续子区间的最大总和。

  题解：先做一下前缀和。循环扫描区间的右边界，把前k个位置的前缀和放到优先队列/set中维护，每次取出最小的前缀和，做减法后更新答案。

• 第三题

  题意：给一个矩阵图（像下面这种，矩阵≤1500x1500），其中#代表障碍物。给出起点和终点的坐标，求起点到终点的最短路。
  ...#.
  ..#..
  #...#

  题解：对起点做一次bfs。

3.11

• 第一题

  题意：给一个数字串（如“11222233”），可以把任意字符替换成0-9的任意数字，问让字符串不存在相邻相同字符的最小修改次数。

  题解：双指针暴力扫。

• 第二题

  题意：给一个200x200的矩阵，每个点上有一定的金币数和一种颜色（红或蓝），起始点在（0，0），每次可以向下或向右移动。如果移动到的下一个点和当前点颜色不同，移动前需要先支付k（>0）个金币，如果支付不起则不能移动。移动到一个点后可以获得那个点上的金币（>0）。初始的金币数是0，问任意移动后停下的最大金币数是多少。

  题解：因为只能像右下移动，所以路径必然不会重复，所以用两层循环维护dp[i][j]，表示到达点（i，j）时的最大金币数即可。有一个坑点是虽然说了初始的金币是0，但给的权值数组val[0][0]不一定是0，被卡了好久。

• 第三题

  题意：给出n（n <= 1e5）个流星观测的起始时间L[i]和R[i]（1<=L[i]<=1e9）。求任意时刻下能观测到的最大流星数量，以及能观测到该数量的时刻数。例如，观测时间为[1, 3]、[2, 6]、[5, 7]，答案为2 4。

  题解：考虑区间端点的数量，不超过4e5个，由于数值会比较大，先将所有端点离散化。接着可以用前缀和数组sum维护，例如离散后的区间是[L, R]，那么令sum[L]++, sum[R+1]--。这样在从左往右扫描的时候，就能知道每个位置（离散后的）的观测数量，也就能获得第一个答案。

  对于时刻数，可以在sum数组上用双指针扫描满足最大观测数的段落。但是这样会存在一个问题，如上例中，[2, 3, 5, 6]每个位置的观测数都是2，但是直接用6-2+1=5就会把不满足的时刻4也包含进去。解决办法是，在离散每个时刻时，把相邻2个时刻之间再添加一个离散值。所以例子中的端点[1, 2, 3, 5, 6, 7]应如下图离散，圈出来的就是新插入的值。（感觉我的做法很奇怪，应该不是正解。

  

• 第四题

  题意：在15x15的矩阵上，两人分别驾驶坦克操作。每个回合能做的操作是像4个方向之一移动一格，或者开火。不能移动到矩阵外，不能移动到对方已经路过的格子。开火命中对方则获胜，同一回合互相命中则同时获胜。同时移动到一个格子平局。若256回合结束后还没获胜，则对比双方经过的格子总数，数量多的获胜。

  题解：大模拟。

• 第五题

  题意：给出一棵树，每个节点是红色或蓝色。若一个节点的子树中红色点和蓝色点数量相同（不包括该点本身），则这个点是good。求有多少个good的点。

  题解：树形dp，自下而上维护即可。

3.12

• 第一题

  题意：给出缩略的字符串（如“A4B7”），将其还原输出（如"AAAABBBBBBB"）。

  题解：暴力。

• 第二题

  题意：t组数据。给出n个怪物的血量a[i]，你有2种操作，直接杀掉1只怪物或选2只怪物各扣一滴血，求杀完n只怪物的最小操作数。

  题解：只有杀2只血量都为1的怪物时选择操作2，其他情况均使用操作1。

• 第三题

  题意：有3种活动A、B、C，每种活动有参与人上限a[i]和每人需缴费b[i]。有n个人，给出每个人想参加的活动列表（如AB、A、AC、ABC，不为空），每个人最多只能参加1个活动。若n个人都能参加活动，输出最小总花费；若不能，输出最多能同时参加的人数。

  题解：令dp[i][j][k]表示ABC三种活动参与人数为i、j、k时的最小花费，4层循环（n^4）更新dp数组即可（注意避免1人多次贡献的情况）。

• 第四题

  题意：给定一个n（n<=2e5）个数的数组，求所有前缀数组（a[1], a[1-2],...,a[1-n]）的平均数和中位数（四舍五入）。

  题解：我又做麻烦了，用双向链表+线段树维护，写了一小时，我日。实际上维护一个大根堆和小根堆即可，插入新数的时候维持两个堆大小相同或差1。

3.13

• 第一题
  题意：输入一个字符串，问对其任意排列后能否组成"Baidu"。
  题解：判断5个字母是否存在且字符串长度为5。

• 第二题
  题意：给出一个正整数x（<=1e9），用r、e、d三种字母构造出一个字符串，满足回文子串的数量刚好是x，输出字符串。
  题解：构造题。考虑一段连续的长度为len的相同字母组成的字符串，其回文子串数量为len*(len+1)/2，如下表。那么考虑能否对len从大到小来填充x，也就是构造形如 r*x + e*y + d*z + r*x2 + e*y2 + d*z2 + ...（x>y>z>x2>y2>z2，循环使用3种字符，长度递减）的字符串。观察后发现，这样的字符串不会出现包含不同字符的回文子串，同时一定能填充至长度为x。

  len	1	2	3	4	...
  cnt	1	3	6	10	...

• 第三题
  题意：给出一个包含n（<=2e5）个点的树，每个点是红色或蓝色。定义每条边的权值为断开后，两棵子树内不同颜色联通块数量的差值的绝对值。
  题解：树形dp。第一次dfs统计sum[u]，表示u结点子树内存在多少个异色联通块。转移方程如下：
  \(\\\)
  \(sum[u] = 1\)
  \(对于结点u,遍历所有子节点v\)
  \(sum[u] += sum[v] // u,v颜色不同\)
  \(sum[u] += sum[v] - 1 // u,v颜色相同\\\)
  再做一次dfs，对于每条边，两棵子树的异色联通块树分别为sum[v]和sum[root]-sum[v]（若u,v同色则+1），计算边权，得到答案。

3.19

• 第一题

  题意：给出一个n*m大小（1000*1000）的矩阵，每个点有一种颜色（R或G或B）。定义颜色相同的位置可以上下左右4个方向联通，此时联通块的数量为x。对于有色盲的人，会把G和B视为一种颜色，他们看到的联通块数量为y。计算并输出x-y。

  题解：dfs搜索联通块的数量，2种方式在搜索的时候区别开就行，O(n*m)。

• 第二题

  题意：t（<=1000）组数据，给出2个字符串a和b（字符串长度<=1000）。每次操作可以在a中删除一个"mhy"子序列，或插入一个"mhy"子序列。问通过若干操作，能否使a变成b。

  题解：首先，插入和删除操作是可逆的。假如此时2个串分别为"xh"和"hx"，发现可以通过先插入再删除的方式"移动"h的位置（xh->mhxhy->hx）。推广一下，对于m或h或y字符，我们可以任意移动它在字符串中的位置。综上，先把2串中的删去m、h、y后的剩余串进行比较，再统计m、h、y三种字符的数量，能删的尽量删，若剩余的3种字符数量仍相同，则答案为Yes。

• 第三题

  题意：给出一个n（<=1e5）个数的集合（不存在相同数，a[i]<=1e6）。求有多少个长度大于1的子集满足任意两数之间都存在倍数关系，答案对1e9+7取模。

  题解：先排序。dp[i]表示以第i个数结尾的满足条件的子集有多少种，递推公式如下。枚举每个数的所有因子，即可得到需要更新的来源，复杂度为O(n*sqrt(1e6))。

  \[dp[i]=\sum{dp[j]+1} // j<i且a[i]\%a[j]=0 \]

3.27

• 第一题

  题意：给一个n<1e5的数组a，1<=a[i]<=1e5。把数组分为两个子数组A和B，满足A∩B=null、A∪B=a、A中数的总和大于B中数的总和，输出长度最短的A数组。（若存在长度相同的多组解，输出总和最大 的）

  题解：不会。用背包复杂度要n*n了。

• 第二题

  题意：给定一个1000*1000的数组，a[i][j]=0/1，0表示不能走，1表示能走。初始点在（0，0），每次可以向右或向下移动一格，求移动到（n-1, m-1）的方案数。

  题解：两层for循环，dp更新即可。

7.14

• 第一题

  题面：给出两个字符串，每个字符串由多个数字组成，数字之间用'.'分隔，数字可能有前导零，例如“0.110.002.0”。比较两个字符串的大小，从左往右依次对比每个数字，如果数字个数不同，视为往数字少的串尾部添加0，直到个数相同。

  题解：字符串切割，再用stoi转成数字，按题意比较。

• 第二题

  题面：给出一个n（<100的奇数），按照题面指定的规则在一个n*n的矩阵中填入1~n²。输出填完后的矩阵。

  题解：按题意模拟。

• 第三题

  题面：给出一个window、max和数组a，a[i]表示在第a[i]秒想要运行一个进程（a数组单调不递减），要求在长度为window的时间框内，运行的进程不超过max个。求a中的每个进程能否被运行。

  题解：维护窗口最左边时间点在a中的下标、当前窗口内的进程数量cnt。在从前往后遍历a数组的过程中，更新这两个值，如果cnt<max，则当前进程能运行，否则不能运行。

7.21

• 第一题

  题面：有一棵树（n<300），每个节点有颜色，用字母A-Z表示，现在给你这棵树的dfs序，问树的结构可能有多少种，对1e9取模。

  例子：输入ABABABA，输出5。

  题解：三维dp。

  dp[L][R][1]表示【L，R】部分的字符串能组成的第二层节点数量<=1的树的种类。

  dp[L][R][0]表示【L，R】部分的字符串能组成的第二层节点数量>=2的树的种类。

  转移方程如下，可以避免重复计算。
  \(\\\)
  \(dp[L][R][0]=\sum{(dp[L][i][0] + dp[L][i][1])*dp[i][R][1]} //L和i颜色相同\)
  \(dp[L][R][1]=dp[L+1][R-1][0]+dp[L+1][R-1][1]\)
  \(\\\)

• 第二题

  题面：在水平坐标轴上，有很多石子在不同的位置（n<100，x[i]<1e9）。现在你在起点0，每次可以向右跳动【L，R】的距离（L，R<10），求跳到pos或之后的位置时（pos<1e9），经过的最少的石子数量是多少。

  例子：有5个石子，位置是【2，3，5，6，7】，L=2，R=3，pos=10；输出2。

  题解：对石子周围的部分点进行离散化，dp维护到达每个点的最小石子数量。对于相邻的距离超过R的两个点，用同余最短路判断能否到达。

7.23

• 第一题

  题意：给出n（<1e5）和k。构造包含n个数的正整数数组，满足数组的最大公约数为k，求数组总和的最小值。

  题解：构造数组形如【k，2k，...，nk】即可。

• 第二题

  题意：给出线段的长度n（<1e9）、区间的数量m（<1e5）、截取的长度k（<1e9），以及m个区间（1<=L[i],R[i]<=1e9，保证区间不相交）。用k尽量覆盖更多的区间总长度，求最大覆盖的值。

  题解：前缀和+滑动窗口。首先，对于最大的结果，一定存在一个窗口在其右边界与某个区间的R[i]重合时满足。可以想象一下，对于一个窗口左右移动时发生的变化。那么从左向右枚举区间，维护窗口左端所在的区间编号，计算当下最大值更新答案。复杂度为O(m)。

• 第三题

  题意：给出一个n个数的数组（n<2e5，-1e9<a[i]<1e9）和一个数x（-1e9<x<1e9）。可以把数组中某个值改为x，也可以不修改。求所有连续子数组中总和的最大值。

  题解：前缀和。首先对数组求一遍前缀和sum，那么子数组[l, r]的和即为sum[r] - sum[l-1]，再求前缀最大值数组L和后缀最大值数组R（如下公式）。如果不使用x，那么枚举子数组包含i，ans = max(R[i] - L[i - 1])，即i右侧的最大sum值减去i左侧的最小sum值。

  \[L[i]=\max(sum[1,...,i])\\ R[i]=\max(sum[i,...,n]) \]

  接着考虑加入x的影响。如果把a[i]改为x，那么sum[i~n]的值都会增加(x - a[i])，R[i]的值也会增加(x - a[i])。那么对于ans的计算稍加修改，ans = max(R[i] - L[i - 1] + x - a[i])。复杂度为O(n)。

8.6

• 第一题

  题意：有n组数据，每组数据给出m，j，k，表示参加比赛的人数（m=2的幂次，m<=2000）、观众想看的2个人的分数排名。接着给出m个人的比赛顺序（每轮比赛两两进行，分数高的人获胜，直到最后诞生冠军），m个人的分数。如果在所有比赛中，分数排第j的人和分数排第k的人进行了比赛，输出YES，否则输出NO。

  题解：用队列按题意模拟即可。

• 第二题

  题意：给出s串、t串和正整数k（len(s)<2e5，len(t)<10，k<2e9）。求s中有多少子序列等于t，同时满足子序列中所有相邻字符的距离≤k，对1e9+7取模。

  样例：

  • 输入：soovood svd 2 输出：1（s和v的距离为2）

  • 输入：soovood svd 1 输出：0

  题解：dp[i][j]表示，子序列结尾为t[i]，尾部间隔为j的子序列数量，转移更新公式如下。在遍历s串时，假如当前字符c==t[i]，则使用第一条更新公式；每遍历一个字符，之前子序列的间隔就会增加1，使用第二条更新公式。
  \(\\\)
  \(dp[i][0] = sum(dp[i-1][0].......dp[i-1][k])\)
  \(dp[i-1][j+1] = dp[i-1][j]\)
  \(\\\)
  为了维护第一种转移，需要区间求和和单点修改，可以使用线段树或树状数组。为了维护第二种转移，需要对dp数组进行滑动处理。总复杂度为O(2e5*10*log)。

• 第三题

  题意：给出n，m，k（均为≤1e6的正整数）。在二维坐标系上，有(1，1)到(n，m)这n*m个点，每个点权值为横坐标与纵坐标的乘积。求所有点的权值中第k大的值。

  题解：二分答案。枚举横坐标的值，除法得到纵坐标的范围，进而得到比当前mid大的值有多少。复杂度为O(n*log)。

8.9

• 第一题

  题面：给出正整数x和n（x≤20，n≤10），以及包含n个正整数的数组a（a[i]≤20，且无重复元素）。假如a中每个数可以无限次取用，求有多少种方法组成x。

  题解：完全背包裸题，O(n*x)。

• 第二题

  题面：有n个同学和m个社团（n≤3e4，m≤1000），给出每个社团包含的同学。每个同学可能参加了任意数量个社团。同一个社团中的人互相是好友，好友具有传递性，求最大的朋友圈中包含多少人。

  题解：dfs求最大联通块，O(n)。

8.10

• 第一题

  题面：给出一个字符串s和q次操作（len(s)≤2e4，q≤2e4），每次操作给出L、R、k（1≤L≤R≤len(s)，R[i]-L[i]≤10，k[i]=0/1）。若k[i]=0，提取原串的L[i]-R[i]部分添加到字符串开头；否则添加到字符串结尾。求最终的字符串。

  题解：每次都从初始串上提取，直接模拟字符串拼接即可，复杂度为O(q*10+len(s))。

• 第二题

  题面：给出一棵n个点的树和q次查询（n，q≤5e4）。每次查询给出2条毛毛虫在树上的节点位置，毛毛虫会随机向下爬直到不能再爬，令最终两只毛毛虫所在位置的组合（p1，p2）的可能数量为x种，求q次查询中所有的x的异或值。

  题解：每只毛毛虫向下爬的最终位置的可能数量就是子树的叶子节点数，x即为两棵子树的叶子节点数之积。做一次dfs统计每个点作为根的子树的叶子节点数，求出每个x并异或得到答案，复杂度为O(n+q)。

8.13

• 第一题

  题面：输入文件列表和一个指定的关键字s，查找哪些文件夹或者文件包含了该关键词，输出包含关键词的文件/文件夹的完整路径。

  样例：

  输入：
  4
  6
  root/
  -dir1/
  --file1.txt
  --file4.txt
  -dir4/
  --file5.txt
  输出：
  /root/dir1/file4.txt
  /root/dir4/
  

  题解：按输入顺序建树，dfs查询。注意考虑第一层可能有多个文件夹。

• 第二题

  题面：输入一个a数组和一个b数组（数组内值的范围为【0，255】），可以用b数组中的数去替换a数组中的数，希望让a数组变为严格单调递增，求最小的替换数；无法实现输出-1。

  题解：其实是力扣原题，https://leetcode.cn/problems/make-array-strictly-increasing/description/。

8.20

• 第一题

  题意：有n个人围成一圈，从1到4报数，每次报到2的人离开，求最后一个人的编号。

  题解：直接模拟。只过了45%，感觉数据有问题。

• 第二题

  题意：给两个矩阵，输出相乘的结果矩阵。

  题解：n*m*k直接计算。

• 第三题

  题意：有A和B两个正整数数组，把B合并到A中，让A变成不含重复数的升序数组，输出A。

  题解：全丢到set里然后输出，过了70%。题面也不清晰，不知道到底想要什么。

• 第四题

  题意：给两个字符串，输出最长公共子序列的长度。

  题解：dp模板题。但是测试用例是最长公共子串，用子序列0%，用子串100%。

8.27

• 第一题

  题意：在二维坐标系上，有人和2只怪物，人的起始位置在（1，1），怪物分别在（x0，y0）和（x1，y1）。人有起始生命值H，每秒可以选择上下左右方向移动一格，如果当前格子上有怪物，也可以花费1秒和怪物战斗。怪物的起始战斗力为h[i]，每隔a[i]的时间会提升b[i]（1≤a[i], b[i]≤1e5）。如果战斗时人的剩余血量≥怪物战斗力，人可以扣除怪物战斗力数值的血量来打败怪物。求人打败两只怪物后剩余的最大生命值，如果无法打败则输出“yingyingying”。

  题解：只有两种策略，先打怪物1再打怪物2，或先打怪物2再打怪物1。各算一下，取最大值。（注意怪物的战斗力可能增长到爆int）

• 第二题

  题意：有n（≤1e5）个数的数组，A和B两人进行博弈。开始时在数组中随机一个位置，接下来每人要选一个位置在上一个数左边且比上一个数小的数，无法选择的人输。求先手赢的概率，用分数表示。

  题解：如果初始随机数x的左边存在小于x的数，A只要选择左边最小的一个，B就无法再选了，A必赢；否则A必输。统计一下有多少个这样的x，x/n（除掉最大公约数）即为答案。

• 第三题

  题意：给出一棵n（≤1e5）个点的树，每个点上有一个字符m或h或y。求树上所有路径组成的字符串中，包含mhy子串的数量。

  题解：假设根节点字符为h，子节点为m的子树大小=【x，y，z】，子节点为y的子树大小=【a，b，c】，那么对答案的贡献为（x+y+z）*（a+b+c）。那么dfs统计子树大小，再在每个字符为h的节点上按该公式计算，就能得到总的答案。

8.27

• 第一题

  题意：给出罗马数字和十进制数字的对应表（MDCLXVI），输入一个十进制数，输出罗马数字的字符串。

  题解：从大往小依次做减法，边减边构造答案。

• 第二题

  题意：有n个同学，其中有一些是朋友关系，朋友具有传递性，会形成一个个小圈子。问有多少个小圈子。

  题解：建图，dfs查找联通块数量。

• 第三题

  题意：给出一份代码，让你找出问题并修改（至少3个问题）。

  题解：auto没加引用导致传值；结构体成员const string&要把&去掉；对vector做reserve会导致内部成员的地址变化。

9.10

• 第一题

  题意：给一颗二叉树（n≤1e5），每个节点权值为0/1。求根节点到叶节点的路径中，有多少条上1的数量比0的数量多一？

  题解：dfs的时候，顺便维护cnt1-cnt0。

• 第二题

  题意：给一个n个数的数组a（n≤1e5，a[i]≤1e9），接下来有n-1次操作，每次删除a中的一个数。求数组原始的中位数，以及每次操作后的中位数。

  题解：用两个multiset维护中位数，力扣应该有类似的题目。

• 第三题

  题意：给一个n个数的数组a（n≤2e5，a[i]≤1e9），表示n个怪物的战斗力。牛牛的初始战力x为0，和怪物战斗时，如果x＜a[i]，牛牛的战力x会上升至a[i]；否则x下降至a[i]。求打败n只怪物后，牛牛累计上升的战力最大为多少？

  题解：贪心。排序后，先打一个战力最大的，再打一个战力最小的，循环下去。

• 第四题

  题意：有一个长度为n的01串，给出k（k≤n≤1e6）时，定义串的检验和为所有长度为k的子串的异或和。给定n和k，对任意一个长度为n的01串S，求其他长度为n的01串中和S校验和相同的有多少个？

  题解：结论题。S串有2^{n种，校验和有2}k种，平均每种有2^{(n-k)个，那么答案为2}(n-k)-1。

• 第五题

  题意：给一个n个数的数组a（n≤1e5，a[i]≤1e9），每次操作可以选一个数将其二进制下最低位的1变成0。求k（k≤100）次操作后a数组的总和最小为多少？

  题解：背包。用dp[i][j]表示前i个数进行了j次操作后的最大总和，转移时需要对a[i]进行二进制分解，转移方程如下。复杂度为O(n*k*30)。

  //对当前数a[i]进行j次操作，减去的值为sum
  //对前i-1个数进行了pre次操作
  //0≤pre≤k
  dp[i][pre + j] = max{dp[i - 1][pre] + sum} 
  

9.12

• 第一题

  题面：在一个n*m（n,m≤1000）的棋盘上，起始点在（1,1）。两个人轮流移动，可以向上或向右移动奇数长度的距离，无法移动的人输。若先手必赢输出Yes，否则输出No。

  题解：结论题。n+m为奇数输出Yes，偶数输出No。

• 第二题

  题面：有n个帖子（n≤1e5），每个帖子有两个权值a和b。现在能从中任选一些帖子，求下公式的最大值。

  \[|\sum{a[i]}-\sum{b[i]}| \]

  题解：只有两种可能，选择所有a≥b的帖子，或选择所有a＜b的帖子，计算两者的最大值。

• 第三题

  题面：项目组有n个人（n≤1e5），他们出了一份方案给老板。老板会打回让他们重改m次，每次会让[L[i]，R[i]]范围内的人怒气+1（m≤1e5，1≤L[i]≤R[i]≤n）。每个人有一个最大容忍度a[i]（a[i]≤1e9），如果某次被老板打回后有人怒气值超过了容忍度，他就会找老板battle，并使用上一版方案。求最后使用的方案是第几版？

  题解：二分答案，根据二分的值去检查是否有人破防了，复杂度O((n+m)*log)。

9.16

• 第一题

  题面：给一个n个数的数组a，以及正整数k、L、R（n≤1000，a[i]≤1e9，1≤L≤R≤k≤10）。定义一个合法的子序列为对任意长度为k的子数组，子序列都含有其中x个数，x∈【L，R】。一个合法的子序列的权值为子序列所有数之和，求所有的合法子序列的权值和是多少？（对1e9+7取模）

  题解：状压dp。用一个二进制数表示k个数在子序列中是否被选中。维护两个数组cnt和sum，cnt[i][st]表示i之前的状态为st的合法子序列的数量，sum[i][st]表示i之前的状态为st的合法子序列的总贡献。转移时只有两种前驱，即第i-k个数是否被使用。复杂度为O(n*2^10)。

• 第二题

  题面：给出一个字符串s，由数字、字母、空格组成。把其中的数字替换为空格，若存在多个连续空格时只保留一个，且开头和结尾不能是空格。输出修改后的字符串。

  题解：按题意模拟。

• 第三题

  题面：T组数据（T≤10）。给出n个二维坐标上的点（n≤20，0≤x[i],y[i]≤100）。若存在4个点构成一个平行于坐标轴的正方形，则可以通过一次操作把4个点删除。求最多能删除多少个点？

  题解：状压dp。用二进制数st表示未被删除的点，虽然0≤st≤2^20-1，但实际上只存在大约2e5种可能的状态。首先预处理出所有能组成正方形的点对<p1,p2,p3,p4>，存在n²种。然后记忆化搜索更新dp数组，转移方法就是枚举尚存的正方形，向下继续搜索。复杂度约为O(T*2e5*n²)。

9.23

• 第一题

  题意：给出2个sql表的数据，指定连接方式（left join/right join/inner join/full join）和比较方式（</=/>），输出select语句的结果。

  题解：模拟。但是有很多细节，比如查询的数据并不是主键，在一张表内可能存在重复的值。

• 第二题

  题意：给出n本书，和书的权值a、b（n≤1e5，0≤a[i], b[i]≤1e9）。对某一本书，第一次学习能获得a[i]的知识，之后每次学习能获得b[i]的知识，每次学习需要1单位时间。现在有m单位时间（1≤m≤1e9），求能获得的总知识的最大值是多少？

  题解：最多只有一本书会被学习2次以上。枚举被多次学习的书，对其他的书，若a[j]>b[i]则应该学习，否则不学习。通过前缀和+二分能快速得到其它书学习一次得到的知识，剩余时间全用于对当前书多次学习。复杂度为O(nlog)。

• 第三题

  题意：有n个任务和m个人，以及n*m的矩阵表示每个人完成每个任务的时间。一个任务只能被一个人处理，一个人可以串行处理多个任务。完成所有任务的时间，等于单个人花费时间的最大值。现在对任务进行分配，求完成所有任务的最小时间。（n,m≤12，0≤t[i][j]≤100）

  题解：状压dp。dp[i][st]表示前i个人完成了状态为st的任务的最小时间，st有2^m种。在转移时枚举前i-1个人的状态pre和第i个人处理的工作st，合并的状态nxt=pre|st。复杂度为O(m*2^n*2^n)。