【题解】牛客练习赛50
tag：模拟
为字母
第一次出现的下标，
为字母
最后一次出现的下标，
为字母
总共出现的次数。
那么对于所有出现过的字母，判断他们是否都满足即可。
时间复杂度为。
tag：模拟，并查集，STL
解法一：
用并查集维护空位。在位置插入一个数后，合并
和
即可。
要注意，合并的时候，必须当爹，才能达到维护的效果。
解法二：
用set维护所有空位，每次lower_bound找到第一个可用空位即可。(可能会卡常)
tag：贪心
按从大到小排序。用一个小根堆维护已选士兵的战力
。
设第个必选，那么对团的人数起到限制作用的一定是
。
因为是从大到小选的，所以已选士兵的
一定大于等于
。
那么选了第个后，把战力小的踢出去，直到满足
的限制。
对所有结果取个max，就是答案。
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，时间复杂度为
