代发题解，本人不是出题人
题目难度排序
简单:ABC
中等:DEFG
难：HIJ
题目：这波啊，这波是······
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/A
- 这波是肉蛋葱鸡！
- 时间复杂度O(1)。
- 作者： wbs
题目：李在赣神魔
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/B
- 这种题是不需要讲的
- 时间复杂度
。
- 作者： wbs
题目：电竞希金斯
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/C
- 这种题是不需要讲的
- 时间复杂度
。
- 作者： lyh
题目：财富密码
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/D
- 统计有多少整数n满足
- 作者： lyh
- 根据欧拉定理，看到反常的p的范围就直接枚举n mod (p - 1)的值r。
- 则问题等价于
- 中国剩余定理直接解决
- 时间复杂度
。
芜湖起飞
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/E
- 给出一张n个点m条边的图，边权都是关于x的一次函数。
。
- 作者： wbs
- 本题的答案具有凸完全单调性
- 考虑任意一条路径，其长度仍然是一次函数
- 那么最短路的函数就应该在任一点低于所有路径，因此是一个半平面交
- 所以我们直接三分x的值并求最短路。
- 时间复杂度
题目：这题多捞啊
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/F
- 输出所有的正整数集合S =
满足：
- S的任意子集和不为n
- 作者：lyh
- 结合题目的名字和数据范围，我们知道这题肯定有大问题
- 满足条件的集合肯定非常少
- 很轻松就能找到两类：
- 1+1+1+···+（n+1）,n为奇数时还有2+2+···+2
- 把这两类输出，记得特判n = 1
- 哇，A了，好简单啊
- 可是为什么呢
- 考虑集合的前缀和
这n个数
- 它们之间任意两个模n不会同余，否则矛盾
- 所以这谢前缀和模n的余数两两互异
- 交换
，我们得到
- 后n - 1个数与之前的相同，所以
- 类似的我们得到所有的数模n同余
- 因此满足条件的只有上面的两组解
- 时间复杂度
题目：正方形打野
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/G
- 给出一个
,向每个格子中填充字母，使得：
- 所有的同字母四联通块必须为正方形
- 最小化从上到下，从左到右的字典序
- 作者：lyh
- 最小化字典序是经典的贪心问题
- 我们按照从上到下，从左到右的顺序枚举每一个未填充格子的颜色，判断是否可行，需要的时候将已有的正方形
向右方和下方扩充一行和一列 - 填到一个格子的时候其左右上方紧邻格子都可能填充过
- 如果该颜色与上方或右方相同，这种情况不合法
- 接下来，如果它与左边颜色不同，那么可以构成
方块
- 如果左边的方块不是一个已有正方形的右上角，那么不合法
- 否则我们将该正方形向右方和下方扩充一行和一列，无法扩充则
不合法。 - 时间复杂度
- 事实上颜色一定不超过四种，因为著名的“四色定理”：任意地图
一定可以被四种颜色上色，使得相邻区域不同色题目：时间管理
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/H
- 给出一个长度为n的序列，支持：
- 区间对一个数取gcd
- 询问区间和
- n,操作次数
,权值不超过
- 作者： wbs
- a对b取gcd，其结果或者不变，或者不超过a/2
- 所以每个数最多只有log段取值
- 先用扫描线找到包含每个点的操作集合，以时间顺序排序
- 为了求着log段取值的起始时间，我们要支持在集合中插入,删除以及二分查找
- 可以采用线段树
- 接下来，再将这nlogn段取值插入树状数组并查询
- 算上gcd的复杂度，似乎是
的，非常不优美
- 但是考虑单词二分时的log个gcd，他们总的复杂度仍是一个log的
- 所以时间复杂度为
- 因为出现了一种出题人始料未及的乱搞做法导致数据中没有针对这种做法的点。
- 比赛中通过的那种做法是错误的，可以轻易被卡到时间超限。
- 虽然出题人在同步赛中已经发现了这种乱搞，但是他还是决定不临时加数据了，算是奖励一下敢于尝试数据结构题的同学吧。
题目：这波Alice在第五层
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/I
- 有一片森林。初始只有一棵n个节点的树
- Alice和Bob轮流操作，每次可以选择当前森林的某些根删去，无法操作者输
- 问先手还是后手必胜
- 数据组数
。
- 作者： lyh
- 解法1：
- 如果当前存在可选的叶子节点，也就是孤立点，那么先手必胜
- 因为假设去掉这些叶子节点后后手存在必胜策略，那么先手第一
步可以选择该必胜策略的第一步+叶子节点来获取必胜 - 那么所有的叶子节点的父亲先手是不能选的，否则就必败了
- 将所有叶子节点及其父亲从树中去掉，那么问题还是“不能操作者
输”，并且规模缩小了 - 重复上述动作直到节点数不超过1
- 如果节点被删光了，那么先手必败，剩下根则先手必胜。
- 时间复杂度
解法2： - 一个点的儿子如果有先手必胜那么其先手必败。
- 分析很类似于解法一
- 设先手必胜的子树为A，其余子树结合为B
- 先手先把树根拿掉，接下来后手不论操作A还是B，先手也跟着操作相同的集合
- 不论B中先手胜利还是后手胜利，先手总能操作到A集合的最后一步
- 直接递推即可，时间复杂度
题目：电竞胡司令
- 题目链接：https://ac.nowcoder.com/acm/contest/5945/J
- 埃及祖玛是一款风靡全球的游戏，其简化版规则概括如下：
- 有一排珠子，从左至右编号为1~n
，每颗珠子有一个颜色，初始时，不存在三颗相邻的同色珠子 - 你可以进行若干次操作，每次可以在序列的任意位置插入一颗任
意颜色的珠子，插入完成后将进行检测 - 如果此时有三颗及以上的相邻珠子同色，那么这些珠子都将消失（如果最多有𝑙个相邻的同色珠子那么𝑙个全部消失），左右两边
的序列合并为新序列，重复此过程直到不存在三颗相邻的同色珠
子。 - 如果序列为空，则游戏结束。否则进行下一次插入。
- 设左起第i颗珠子的颜色为a[i],定义a[0] = a[n + 1] = 无意义的颜色
- 除法消失机制的条件:存在l,r，
- 若满足条件，则将a[1] ~ a[l-1]以及a[r+1] ~ a[n]拼成一个新序列，替换原来的序列,并将n改成为新序列的长度，再重复上述过程.
- 对于给定的序列，求出最少插入几次即可把序列删除为空
- 作者：wbs
- 首先，这个游戏存在一些酷炫玩法：前面的插入均不产生消除，
但最后一次插入突然把序列消除干净了。 - 但是所有酷炫玩法都可以转化为老实的玩法且不增加操作次数。
- 在老实的玩法下，至多经过两次操作就会引发消除，而且如果是
两次后才引发消除的话这两次操作插入的珠子同色。 - 这是因为能通过一次插入即消除干净的序列可以对应到回文串，
每个字符代表一个或两个原串的字符，相邻两个字符不相同。 - 考虑这个回文串的首尾两个字符，我们发现先消除中间部分再消
除这两个字符不会影响总操作次数，据归纳法可得结论。 - 考虑区间DP，即f[l][r] 表示将a[l]~a[r]消除为空所需的最小代价
- 情况1：消除一段序列可以先消除一段它的前缀或后缀
- 情况2：如果不满足情况1，那么最后一次消除前，a[l]和a[r]都存在，且必然颜色相同
- 每次消除至多4个珠子，它们颜色相同，其中两个珠子分别在序列首尾
- 最后只剩余首尾两个珠子:f[l][r] = min(f[l][r],f[l + 1][r - 1] + 1)
- 最后消除3个珠子：f[l][r] = min(f[l][r],f[l+1][k-1]+f[k+1][r-1])
- 最后消除4个珠子：f[l][r] = min(f[l][r],f[l+1][p-1]+f[p+1][q-1]+f[q+1][r-1])
- DP过程中可能会有不合法的消除，需要注意。
- 枚举的分界线两侧颜色不能相同，因为它们必然被同时消除。
- 时间复杂度
,需要继续优化
- 瓶颈在于消除4个珠子的情况时的枚举，可以通过类似前缀和优
化的方法来优化。 - 时间复杂度
,但是自带
常数，可以通过本题
- 其实把数据出那么大的原因是四次方暴力太快了，对于n = 500都能轻松跑过，这就非常离谱
全部评论
(2) 回帖