8.6 文远知行 笔试

2小时，3道编程题，还是挺有难度的。

编程题：

• 第一题

题意：有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)。