竞赛讨论区 > 【题解】牛客练习赛64

【题解】牛客练习赛64

头像
Huah
编辑于 2020-05-23 12:37:40 APP内打开
赞 11 | 收藏 0 | 回复5 | 浏览1012

A:怪盗-1412

将序列排列成,这样可以得到最大化的子序列数量,答案为,时间复杂度
标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780345

B:Dis2

与每个点距离为的点为这个点的度数。对于每个点,枚举和它有边相连的点,点对点的贡献为与点距离为的点的个数减去(减掉这个点),时间复杂度
标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780359

C:序列卷积之和




设+


预处理前缀和统计前缀和出现的数量,即可得出答案,时间复杂度
标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780364

D:宝石装箱

表示选出个箱子装不合法的宝石的方案数。

那么为至少个箱子装了不合法的宝石的方案数。
根据容斥原理,答案为
表示不可以装入第个箱子的宝石的数量,注意到每个宝石只对应一个箱子。
初始时,
然后相当于每次加入一个物品,当加入第个箱子,有,那么通过背包就可以求出所有的,最后统计答案即可,时间复杂度,常数很小。
标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780376

E:红色的樱花

如果,那么答案为。否则:
随机选择一个点,初始时,让,然后执行以下操作:
a.将点染色,再让
b.如果点已经被染色,则跳出,否则回到
的时候,被染色的点构成了一个循环。
这样的循环的数量有个。
那么操作1转为花费牛币,跳到点所在的环的任意一个位置。
可以证明,操作1至多只需要执行一次。
如果执行0次操作1,我们只能进行横和列的移动,那么就是分别求
的最小正整数解。
如果执行1次操作1:
1.牛牛和牛妹在同一个环,答案为
2.牛牛和牛妹不在同一个环,那么通过列或者行的移动移动到牛妹所在的环,答案再加即可,观察环与环在行上移动和列上移动的影响,可以发现只在行上移动或者只在列上移动是最优的,分别求 的最小正整数解即可,时间复杂度
标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780369

F:如果我让你查回文你还爱我吗

先求出所有的回文半径,设为第个位置的回文半径,对于一个查询,我们要统计(这里暂时只考虑奇回文)。这样的时间复杂度为
,那么我们就只需要对区间查询左回文,对区间查询右回文,消除了的限制。
同样,对于的回文半径,我们把它分成两条线段,一条线段相当于对区间内的每个点权值加,对于一个查询,我们要求所有区间满足的线段对区间的点的贡献和,对于的查询类似。那么可以将查询离线,用数据结构维护区间和。在线查询可以用可持久化数据结构维护。总的时间复杂度为
标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780554

5条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐