百度实习笔试

差不多1h20min写完，就记一下算法题吧 不会八股文，前面还有道卡特兰数。。分享攒人品🥺🥺@-@

T1，判断字符串中是否有"Baidu"

T2, 只能用red三种字母构造一个含n个回文串的字符串，要求字符串串长度<=1e5,n<=1e9 怎么还考构造的。。。

有点像牛牛某场练习赛的题

给出我的构造方法 用k个连续的r，可以构造出 k(k+1)/2 个回文串，那就可以在根号n级别内去构造目标串。 然后用"ed"当分隔符，分隔掉每组r，类似rrrrrrredrrrredr这样，其中ed也是有贡献的。 每组r量级是根号级别去下降的，所以1e5内可以构造出来。

至于为什么一堆类似平方的数可以构造出任意数，不会证明。。。

T3，树上问题，点只有两种颜色，给出每个点颜色。定义e的边权是把e切割后，两个子树的连通块数量之差的绝对值。求边权总和

题意没读懂一开始，后面猜的题意（

dp做的，也不算吧就计数一下

 定义f[u],g[u]为以u为根的子树颜色为B/R的连通块数 f[u]=[col[u]==‘B’] + ∑(f[v]−[col[u]==col[v]]),其中v是u的儿子 ，g[u]同理

然后算边权

如果两端点颜色不同，本次分割不会产生新连通块，则边权 w=∣f[u]+g[u]−(f[1]−f[u]+g[1]−g[u])∣

如果两端点颜色相同，产生新连通块，则边权 w=∣f[u]+g[u]−(f[1]−f[u]+g[1]−g[u]+1)∣

如有错误，请大佬们指正QAQ