携程笔试 20231010

忘记下载代码了 就粗糙的记录一下吧

第一题略，忘记了。

第二题模拟，写两个比较函数，比较的元素为pair<int, int>，第一个比较函数将第一个元素作为第一优先级，第二个比较函数将第二个元素作为第一优先级。跑一个循环，轮流使用两个比较函数排序，排序后找到目标元素，输出L或R，更新当前的串，更新长度，直至串长为1时输出O跳出。

第三题给定一个字符串，每次操作能将一个位置上的字母改成与其在字母表上相邻的字母。问至少操作几次可以使所有相邻字母不相同。

大致思路就是从左往右遍历，然后对于连续的相同字母，判断其与两侧首个不同字母的关系，然后进行变化，用几个if去特判。

第四题给一棵树，树上每个节点有颜色红绿蓝，rgb。求有多少个简单路径，长度为4，路上覆盖了三种颜色的节点。

就是一道普通的树上的求和的题目啦。先把1当作根节点建树。建一个数组cnt去存包含now节点时和他的子树时，节点的个数与颜色组成的种树。一共有12种，1r,1g,1b,2r,2g,2b,2rg,2rb,2gb,3rg,3rb,3gb,3rgb。如果3个节点只有一种颜色，那么4个节点肯定不能有3种，所以不用存3r等。遍历该节点的所有儿子，在更新该cnt数组时同时更新答案。举例来说，now颜色为r，有儿子p时，初始化cnt[now][1r]=1, cnt[now][其他]=0. 用儿子p更新ans时，有ans+=cnt[p][3rgb], ans+=cnt[now][2rg] * (cnt[p][2rb] + cnt[p][2gb] + cnt[p][b]), ans += cnt[now][1b] * cnt[now][3rg] 等等。更新cnt时, 有cnt[now][2rg]+=cnt[p][1g], cnt[now][3rg]+=cnt[now][2rg]+cnt[now][g]等等。