牛客周赛 Round 15 解题报告 简介

详细的解题报告

https://blog.nowcoder.net/n/331464bebcdb4fe29af232c84b1c2919

---

A. 枚举签到题， 只要枚举前后两段的分界点，然后判定末尾的奇偶是否一致

B. 枚举最终的字母，然后评估代价，这边单字母的转移代价

> cost = min(abs(i - j), 26 - abs(i - j))

这符合环状结构

C. 有3种解法

1. 3维DP，正向递推，从而求解最终的结果
2. 脑筋急转弯，分类讨论字符串长度
1. n = 1，任意字符即可
2. n = 2，前后两字符不相等就行
3. n = 3，只有 101， 121， 202， 020这几个字符串满足需求
4. n = 4，只有0,2交替更迭的字符串才满足需求
3. dfs 构造

dfs的深度有1000， 但是它分支少且短，而且找到任意解，立刻返回

D. 树形DP

这题和打家劫舍树形DP版的区别在于， 它本质上不是点不相邻，而是边不相邻。

如果能提取到这个关键信息，就容易解决了。