80min AK。
好难，秋招目前写过最难的笔试。

T1

Description

给定一个长度为的排列，要求构造一个长度相同的排列，满足，且的字典序最小。

Solution

贪心构造，用一个set或者堆来维护剩余没填入b的数里面的最小值和次小值，如果当前填入最小值会导致，那么就填入次小值；另外，在只剩下两个数没填的时候，直接填入最小值可能次小值正好使得，特判这种情况。时间复杂度。

T2

Description

给定字符串和，且字符串只包含小写字母，可以对进行任意次操作，每次操作将中的小写字母全部修改为小写字母，比如将中的修改成就变成，问能不能将变成。

Solution

1. 如果与相同则肯定是Yes，否则check 2；
2. 考虑每次操作只会让可能让原先不同的字符变得相同，而不可能将相同的字符分开，所以check一下中的每个字符的位置在中是不是相同字符，如果不是则肯定是No否则check 3；
3. 最后考虑如果和都包含全部的26个字母，那么肯定是No，否则是Yes。 时间复杂度。

T3

Description

给定行列的只包含小写字母的字符矩阵，求有多少个子矩阵满足每个字母最多出现一次。

Solution

考虑对行枚举固定的范围，对列用双指针维护寻找答案，枚举行范围的时候可以想到其长度一定不超过26，然后对该范围内每一列状压一下即可。 时间复杂度。
其实还可以继续优化，考虑枚举长度，就可以通过的状压来直接得到的状压，像这样处理复杂度为。

T4

Description

给定一个长度为的正整数，现在要恰好修改其中的个数位，使得这个数能被75整除，问方案数的值。

Solution

直接dp，设表示从高到低前个数位表示的数字修改次后得到的数在意义下值为的方案数，那么转移显然分为修改当前数字和不修改当前数字两种。时间复杂度为，然后剪枝一下，当枚举的前一个状态dp值为0时不进行转移。需要特别注意的是的空间复杂度过大，考虑将第一维用滚动数组滚掉，空间复杂度降为，可以通过此题。