1 条题解
-
0
A
一个数可以被表出,当且仅当:
- 可以被 整除;
- 并且在 内,其中 是已经给出的总手指数, 为可以凑出的最多手指数。
据此判断即可,复杂度 ,可以通过全部测试数据。
B
注意到异或和加法有着非常相似的性质——只有异或运算时,顺序并不影响结果。因此我们完全可以把两类操作分开处理。
对于子树异或操作,我们可以记录下来某个节点的所有操作的异或和,然后在最后进行一次 DFS,DFS 过程中记录根到当前节点路径上的节点的操作的异或和,然后异或到当前节点权值上即可。
对于到根路径的异或操作,我们同样可以记录每个节点的操作异或和,然后最后进行一次另一种 DFS,DFS 过程中统计子树内的节点的操作异或和,并异或到当前节点上,再把这个异或和作为返回值传给上一层节点即可。
总复杂度 。
C
注意到迷宫在以 为周期变化,所以可以把一个周期内的迷宫情况预处理好。我们需要知道抵达一个位置时是在迷宫的那个状态,因此可以把每个位置拆成 个点,计算在模 为 的时间到达 所需最少时间,则可以在新建的以 为点的图上 BFS 计算最短路。
需要注意一些细节,例如对于一般的格子,必须今天没有墙且今晚不会有墙到,才能走过去;而终点则只要求今天没有墙就可以走过去。
总复杂度 ,可以通过全部测试数据。需要适当注意内存的使用。
D
内层的括号会产生大于 的数,因此现在考虑由任意正整数构成的数列如何插入 。
考虑两个相邻的数 ,如果 ,那么断言 之间必插入乘号。这是因为不管 左边和 右边是什么情况,所造成影响只会是 乘系数 , 乘系数 (),于是仍然有 ,也就是说 之间仍应该放乘号而非加号。
同理我们可以推广到多个数 ,如果连乘已经是这 个数的局部最优,那么一定也是全局最优。
因此,对于一个正整数列 ,我们的处理办法就是从小到大枚举区间长度,再枚举这个长度的区间(类似区间 DP),看看这个区间的乘积是否大于加和,如果更大,则直接乘起来合并为一个数,然后继续上述过程。最终就得到了 可以算出的最大结果。
这个算法的正确性是比较显然的:由于我们从小到大枚举区间长度,因此对于已经枚举过的区间,倘若没有合并,则说明全加是最优的,那么假设当前一个数列 的最优解有 ,若不是全设为 ,则一定形如 $a_1\times\dots\times a_t+a_{t+1}\times\dots\times a_p+\dots$,但 的最优方案是全 ,因此矛盾,于是只能是全 ,所以我们只需要比较全 和全 即可确定最优解;而依据开始的分析,如果是全 则可以直接合并。至此,我们说明了算法的正确性。
从小到大枚举区间这件事可以通过从小到大枚举右端点 ,再从大到小枚举左端点 实现,这个过程与处理中缀表达式的栈是类似的,因此可以放一起处理,只不过枚举的 到了最近的
(就应当停止。原序列的任意一个区间只会被枚举到一次,因此总复杂度 。
需要注意过程中可能得到较大的数,但实际上只要某个数大于了 ,那它与相邻的数(除非是一列 )必然是相乘优于相加,所以我们只需要记录每个数对 取模的值,以及它的实际值是否已经大于 即可。
E
时按样例的方式构造,否则答案一定不小于 ,其实按 构造即可,具体方法为 。
因为考虑质数要么为 要么为奇数。
如果两个数异或起来为 ,考虑 ,那么一定有 ,因此两个数模 的值不同。
如果两个数异或起来为奇数,那么两个数奇偶性不同,因此两个数模 的值不同。
所以两个数异或起来为质数,那么模 的权值一定不同。
有些选手利用如下方式构造,给第 个数染色时搜索前 个数 ,如果 为质数,那么把所有 中的颜色提出来,染成第一个没有出现过的颜色,如果所有颜色均出现,那么 ,以下是一组反例:
1 2 2 3 1 4 4 3 1 2 2 3 1 4 4 3 1 5
- 1
信息
- ID
- 182
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者