【题解】牛客练习赛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,时间复杂度为

全部评论
难受 最后一题明明思路对了 但是写炸了qwq
点赞 回复 分享
发布于 2019-08-23 22:42

相关推荐

吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
04-11 21:31
四川大学 Java
野猪不是猪🐗:(ja)va学弟这招太狠了
点赞 评论 收藏
分享
评论
8
2
分享

创作者周榜

更多
牛客网
牛客企业服务