美团笔试 10.21

1、m n矩阵选取最多点使得两两距离不为整数

可以想到每行每列最多选一个点，答案就是min(n,m)

2、题面忘了，应该不难

3、给定以ABCDE五种字符为值的矩阵，问只能按ABCDEABCD…走下去的最长路径长度，有环输出-1

维护vis和dst对以A为开头且未访问的节点dfs，dfs过程中标记还未返回的节点vis为-1，用来判断重新遍历到该节点时是否成环

4、给定长度为n的a b字符串，问构造长度为c的回文串，ci=ai或者bi，的不同回文串个数对1e9+7取模

遍历一半，判断对应字符选择的情况，每个下标都有三种可能，0 怎么选都不相等，1 只有一种字符可以选（注意判ai=bi），2 ai≠bi且右边有相同的字符两两对应，答案就是这些下标方案数的累积

5、给定一颗带权值的树，和q次操作，每次操作选定节点和x，使得该节点为根的子树每个节点权值修改为x，问最终整棵树权值和

后面操作可以覆盖前面的，所以可以对每个节点维护一个带时间戳和修改值的pair，然后记录完q次之后对树dfs一下，下放所有操作就行了