【民间题解】牛客练习赛56
没有人写题解我来写一发
A-小蒟和他的乐谱
设当前的音符为x ，((x - 1) % 7 + 7) % 7即为这个数在模7意义下的正模。
判断是不是0，1，2，4，5即可。
然后问题简化为求最长全1段。
复杂度O(n)。
B-小琛和他的学校
我们钦定1为根，那么任意一条边的两个端点就有了深浅。
我们定义u是深度较浅的端点，v是深度较深的端点。
定义sum是学生总量，sz[v]是以v为根的子树点的个数，dp[v]是以v为根的子树的学生的个数。
这条边仅会被如下两种情况使用：
1.以v为根的子树的点发起活动，那么这条边使用 sz[v] * (sum - dp[v]）次
2.除了以v为根的子树的其他点发起活动，那么这条边使用了(n - sz[v]) * dp[v]次
对于每条边计算即可。
复杂度O(n)。
C-小魂和他的数列
考虑dp[i][j]表示长度为i，且最后一个数下标为j的递增序列个数。
那么dp[i + 1][j + 1] 只要考虑dp[i][1...j]中所有最后一位比他小的转移即可。
这里使用树状数组辅助转移。
复杂度O(nklog(n))
D-小翔和泰拉瑞亚
考虑魔法的如下四种情况。
1.最大值和最小值的位置在同一个魔法力，那么该魔法用和不用不影响答案，我们钦定这种情况的魔法一定要使用。
2.最大值的位置在该魔法里，最小值的位置不在该魔法里，那么该魔法不应使用。
3.最大值的位置不在该魔法里，最小值的位置在该魔法里，那么该魔法应使用。
4.最大值和最小值的位置都不在同一个魔法力，那么该魔法用和不用不影响答案，我们钦定这种情况的魔法一定不要使用。
综上，我们考虑枚举每个点作为最小值的情况，那么所有影响该点的魔法都应使用，所有不影响该点的魔法都不应使用。
我们需要一种区间加一个值，区间查询最大值的数据结构，这显然是线段树。
复杂度O(nlog(n))
E-小雀和他的王国
我们发现一个双联通分量中割去一条边不会使整体分裂为两个连通块。
进行双联通分量分解后，我们获得了由割边组成的树，树上任意一条边被割裂，都会使整体分为两个连通块。
因为要加一条边，现在要使得这个树上的某条链成环，且环的点数最多。选择直径即可。
答案就是 删去直径后这棵树上边的个数/总边数。
复杂度O(n)或O(nlog(n))
F-小球和新型材料
该问题分解为两个问题：
1.每个循环右移串的权值。
2.每个循环右移串回文子串的个数。
对于问题1
我们考虑将B倒置后复制成两倍长度，符合fft的公式，进行p次fft即可。
对于问题2
我们将第二个串复制两份后即求每个长度为n的滑窗，回文串的个数。
我们考虑使用Manacher求出所有最长的回文串以后，使用线段树求得每个滑窗中回文串的个数。
复杂度O(nlog(n))
std:
查看23道真题和解析