百度3.13 24暑期实习笔试编程题

一共三道题，第一道纯签到，记不太清了。

T2：

输入一个数x（x<=1e9），要求用任意个'r','e','d'构造一个长度小于等于1e5的字符串，使得字符串的回文子串数为x.

T3：

给出一棵树，每个结点用红色或蓝色染色。定义一条边的贡献为删掉该条边得到的两个子树的同色联通块数的差的绝对值，一棵树的贡献为树上每条边的贡献之和，求该树的贡献。

样例输入：

4

RRBB

1 2

2 3

1 4

样例输出：

2

样例解释：

删除1-2这条边，两个子树的同色联通块都为2，差的绝对值为0

删除2-3这条边，两个子树的同色联通块分别为1,2，差的绝对值为1

删除1-4这条边，两个子树的同色联通块分别为2,1，差的绝对值为1

故答案为0+1+1=2。

评价

三道都做了，个人觉得难度不是很大，第二题构造比较简单，第三题利用树的性质也很好解决。有要题解的可以在评论区探讨。