竞赛讨论区 > 【题解】牛客2020年七夕节比赛
头像
王清楚
编辑于 2020-08-27 10:24
+ 关注

【题解】牛客2020年七夕节比赛

题解赛后在本贴更新~
本场比赛出题团共有7位出题人,希望大家玩的开心~

出题人1:(匿了)
出题人2:
出题人3: 云哥  yyds
出题人4: orz
出题人5:
出题人6:
出题人7:+“慕云而来”

A一道有意思的题目

D
A
ABCD
D
A
C
AB
A
B
C
B
D
D
A
ABC
D
B
D
D
D

B 王母娘娘又双叒叕来难为茶山牛了

这道题就是让你求一个数的阶乘的阶乘的阶乘对一个数取模的结果
解题思路
我们知道模最大是1e9,并且很容易知道从4开始,这个数的阶乘的阶乘已经是大于1e9的,因为我们求的是阶乘,阶乘最后取模和每次取模后相乘的结果相同,因为现在计算的数一定大于模,所以一定会出现一项为0,因此最后的结果也为0。所以如果n小于4,我们直接暴力计算就可以了,反之直接输出0即可
(本道题目开始时数据弱了,之后进行了加强,开场时的提交不进行重测,大家可以重新提交验证)

C 爱心

注意观察n于每一行字符*的数量的关系。
处理好空格和换行就行。

D 拜托了,牛老师

前情提要:~~出锅人~~一开始把数据范围出到,~~然而出锅人不会证明时间复杂度~~。于是改成 ,~~搜厨狂喜~~,可以说是非常~~友好~~了。

首先我们需要根据题目的要求进行因数的分解,找到 n 所有符合情况的因子(不重复,且个数必须大于1)。接着在因子里面进行 dfs ,在dfs 的过程中不断更新答案即可。实测在 里, 因子最多只有240个左右,经过简单的剪枝,可以快速得到答案。时间复杂度 ,其中 k 取决于剪枝水平,经过数据测试大致与因子数是同阶的。如果同学们有证明思路的话可以分享一下!希望没出锅,预祝大家玩的开心。

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44840036

E 争分夺秒

.LCA模版题,判断一下a->1的距离和c->b+b->1的距离小于t即可

F 牛妹的考验

考虑到数据范围:
|S|<=2000,L<=1000
关于字符串包含问题一般想到AC自动机

所以直接进行|S| \* L * 26的dp即可

考虑当前长度为i,停留在k节点所能产生的最大值,然后可以枚举26个小写英文字母,进行dp的状态转移即可

首先,每个节点fail子树权值之和可以通过预处理 处理出来

明显:

假设枚举位为node , 当前字母为x

那么新节点明显为:now = t\[node][x] , 所以状态转移方程即为:
dp[i][now] = max(dp[i][now],dp[i-1][node] + now节点fail子树权值之和)
但是这个now节点需要找到一个在字典树图上存在的一个点,否则没有子树之和可言,所以可以这么操作:
now = node
while(~now&&t[now][j] == 0) now = fail[now];
if(~now) now = t[now][j]

当然这部分可能会卡掉复杂度 | 因为找这个点 可能复杂度会达到sqrt(n)|(本题数据由于七夕节娱乐赛原因,乱搞即可过)
所以可以改变一下t数组的定义:t\[i][j]代表i节点后加入字母j 可以到达的第一个节点
具体在字典树插入时就可以进行操作:

//i为当前节点
for(int j=0;j<26;j++)
if(!t[i][j]) t[i][j] = t[fail[i]][j]


所以,此题就完结撒花了

毕竟七夕节,大家快乐为主,数据并没有刻意去卡一下乱搞做法

反正希望大家乱搞的开心 φ(゜▽゜*)♪

全部评论

(14) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐