【题解】牛客2020年七夕节比赛
题解赛后在本贴更新~
本场比赛出题团共有7位出题人,希望大家玩的开心~
出题人1：
（匿了）
（匿了） 出题人2：
出题人3：
云哥 yyds
云哥 yyds 出题人4：
orz
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
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即可
解题思路
我们知道模最大是1e9，并且很容易知道从4开始，这个数的阶乘的阶乘已经是大于1e9的，因为我们求的是阶乘，阶乘最后取模和每次取模后相乘的结果相同，因为现在计算的数一定大于模，所以一定会出现一项为0，因此最后的结果也为0。所以如果n小于4，我们直接暴力计算就可以了，反之直接输出0即可
（本道题目开始时数据弱了，之后进行了加强，开场时的提交不进行重测，大家可以重新提交验证）
C 爱心
注意观察n于每一行字符*的数量的关系。
处理好空格和换行就行。
处理好空格和换行就行。
D 拜托了，牛老师
前情提要：~~出锅人~~一开始把数据范围出到
，~~然而出锅人不会证明时间复杂度~~。于是改成 
，~~搜厨狂喜~~，可以说是非常~~友好~~了。
首先我们需要根据题目的要求进行因数的分解，找到 n 所有符合情况的因子（不重复，且个数必须大于1）。接着在因子里面进行 dfs ，在dfs 的过程中不断更新答案即可。实测在 里， 因子最多只有240个左右，经过简单的剪枝，可以快速得到答案。时间复杂度
，其中 k 取决于剪枝水平，经过数据测试大致与因子数是同阶的。如果同学们有证明思路的话可以分享一下！希望没出锅，预祝大家玩的开心。
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节点需要找到一个在字典树图上存在的一个点，否则没有子树之和可言，所以可以这么操作：
当然这部分可能会卡掉复杂度 | 因为找这个点 可能复杂度会达到sqrt(n)|（本题数据由于七夕节娱乐赛原因，乱搞即可过）
所以可以改变一下t数组的定义：t\[i][j]代表i节点后加入字母j 可以到达的第一个节点
具体在字典树插入时就可以进行操作：
|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]
所以可以改变一下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]
所以，此题就完结撒花了
毕竟七夕节，大家快乐为主，数据并没有刻意去卡一下乱搞做法
反正希望大家乱搞的开心 φ(゜▽゜*)♪
七夕应当和清楚姐姐表白
腾讯音乐娱乐集团一面37人在聊
投递牛客等公司10个岗位 >