【题解】牛客练习赛50

A. tokitsukaze and Connection

tag：模拟

为字母第一次出现的下标，为字母最后一次出现的下标，为字母总共出现的次数。
那么对于所有出现过的字母，判断他们是否都满足即可。
时间复杂度为。

B. tokitsukaze and Hash Table

tag：模拟，并查集，STL

解法一：
用并查集维护空位。在位置插入一个数后，合并和即可。
要注意，合并的时候，必须当爹，才能达到维护的效果。

解法二：
用set维护所有空位，每次lower_bound找到第一个可用空位即可。(可能会卡常)

C. tokitsukaze and Soldier

tag：贪心

按从大到小排序。用一个小根堆维护已选士兵的战力。
设第个必选，那么对团的人数起到限制作用的一定是。
因为是从大到小选的，所以已选士兵的一定大于等于。
那么选了第个后，把战力小的踢出去，直到满足的限制。
对所有结果取个max，就是答案。

D. tokitsukaze and Event

tag：最短路

s为起点，用边权a跑一遍最短路，记为。
把边的方向反转，t为起点，用边权b跑一遍最短路，记为。
那么在节点切换模式的最小伤害为。
再做一遍后缀min即可。

E. tokitsukaze and Segmentation

tag：dp，组合数学

我们很容易就能写出一个的dp。

for(int i=1;i<=n;i++) dp[i]=0;
dp[0]=1;
for(int i=1;i<=n;i++)
{
    suf=0;
    for(int j=i;j;j--)
    {
        suf=(suf+s[j]-'0')%3;
        if(s[j]=='0'&&j<i) continue;
        if(!suf) (dp[i]+=dp[j-1])%=mod;
    }
}

表示的切割方案数，那么答案为。
接着我们发现求"suf"的过程可以通过预处理后缀和来优化。
于是可以用的时间复杂度通过本题。
PS：有其他的dp姿势，还有组合数的做法。

F. tokitsukaze and Another "Protoss and Zerg"

tag：组合数学，生成函数，NTT，启发式

设恰好选择个星灵单位的方案数为，
对于每场1v1，构造生成函数：
其中
令
则
那么
可以使用启发式合并NTT求，即每次选择2个项数最少的进行NTT，时间复杂度为