【题解】牛客练习赛50 精

tag：模拟

$l_c$ 为字母 $c$ 第一次出现的下标， $r_c$ 为字母 $c$ 最后一次出现的下标， $cnt_c$ 为字母 $c$ 总共出现的次数。
那么对于所有出现过的字母，判断他们是否都满足 $r_c-l_c+1==cnt_c$ 即可。
时间复杂度为 $O(n)$ 。

B. tokitsukaze and Hash Table

tag：模拟，并查集，STL

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

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

C. tokitsukaze and Soldier

tag：贪心

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

D. tokitsukaze and Event

tag：最短路

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

E. tokitsukaze and Segmentation

tag：dp，组合数学

我们很容易就能写出一个 $O(n^2)$ 的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;
    }
}

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

F. tokitsukaze and Another "Protoss and Zerg"

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

设恰好选择 $i$ 个星灵单位的方案数为 $ans_i$ ， $sum_a=\sum_{i=1}^{n}a_i$
对于每场1v1，构造生成函数： $f(i)=\sum_{j=1}^{b_i}{C_{b_i}^{j}}*x^0+C_{a_i}^{1}*x^1+C_{a_i}^{2}*x^2+...C_{a_i}^{a_i}*x^{a_i}$
其中 $\sum_{j=1}^{b_i}=2^{b_i}-1$
令 $g(x)=\prod_{i=1}^n{f(i)}$
则 $g(x)=c_0+c_1*x^1+c_2*x^2+...+c_{sum_a}*x^{sum_a}$
那么 $ans_i=c_i$
可以使用启发式合并NTT求 $g(x)$ ，即每次选择2个项数最少的 $f(i)$ 进行NTT，时间复杂度为 $O(sum_a*log(sum_a)*log(n))$