1 条题解

  • 0
    @ 2026-11-15 20:48:12

    A

    一个数可以被表出,当且仅当:

    • 可以被 kk 整除;
    • 并且在 [l,r][l,r] 内,其中 ll 是已经给出的总手指数,r=l+n×kr=l+n\times k 为可以凑出的最多手指数。

    据此判断即可,复杂度 O(n+q)O(n+q),可以通过全部测试数据。

    B

    注意到异或和加法有着非常相似的性质——只有异或运算时,顺序并不影响结果。因此我们完全可以把两类操作分开处理。

    对于子树异或操作,我们可以记录下来某个节点的所有操作的异或和,然后在最后进行一次 DFS,DFS 过程中记录根到当前节点路径上的节点的操作的异或和,然后异或到当前节点权值上即可。

    对于到根路径的异或操作,我们同样可以记录每个节点的操作异或和,然后最后进行一次另一种 DFS,DFS 过程中统计子树内的节点的操作异或和,并异或到当前节点上,再把这个异或和作为返回值传给上一层节点即可。

    总复杂度 O(n)O(n)。

    C

    注意到迷宫在以 nn 为周期变化,所以可以把一个周期内的迷宫情况预处理好。我们需要知道抵达一个位置时是在迷宫的那个状态,因此可以把每个位置拆成 nn 个点,计算在模 nn 为 rr 的时间到达 (x,y)(x,y) 所需最少时间,则可以在新建的以 (r,x,y)(r,x,y) 为点的图上 BFS 计算最短路。

    需要注意一些细节,例如对于一般的格子,必须今天没有墙且今晚不会有墙到,才能走过去;而终点则只要求今天没有墙就可以走过去。

    总复杂度 O(n3)O(n^3),可以通过全部测试数据。需要适当注意内存的使用。

    D

    内层的括号会产生大于 11 的数,因此现在考虑由任意正整数构成的数列如何插入 +,×+,\times。

    考虑两个相邻的数 x,yx,y,如果 x×y≥x+yx\times y\ge x+y,那么断言 x,yx,y 之间必插入乘号。这是因为不管 xx 左边和 yy 右边是什么情况,所造成影响只会是 xx 乘系数 aa,yy 乘系数 bb(a,b≥1a,b\ge 1),于是仍然有 ax×by≥ab(x+y)≥ax+byax\times by\ge ab(x+y)\ge ax+by,也就是说 x,yx,y 之间仍应该放乘号而非加号。

    同理我们可以推广到多个数 a1,…,asa_1,\dots,a_s,如果连乘已经是这 ss 个数的局部最优,那么一定也是全局最优。

    因此,对于一个正整数列 a1,…,ama_1,\dots,a_m,我们的处理办法就是从小到大枚举区间长度,再枚举这个长度的区间(类似区间 DP),看看这个区间的乘积是否大于加和,如果更大,则直接乘起来合并为一个数,然后继续上述过程。最终就得到了 a1,…,ama_1,\dots,a_m 可以算出的最大结果。

    这个算法的正确性是比较显然的:由于我们从小到大枚举区间长度,因此对于已经枚举过的区间,倘若没有合并,则说明全加是最优的,那么假设当前一个数列 a1,…,ara_1,\dots, a_r 的最优解有 ×\times,若不是全设为 ×\times,则一定形如 $a_1\times\dots\times a_t+a_{t+1}\times\dots\times a_p+\dots$,但 a1,…,ata_1,\dots,a_t 的最优方案是全 ++,因此矛盾,于是只能是全 ×\times,所以我们只需要比较全 ×\times 和全 ++ 即可确定最优解;而依据开始的分析,如果是全 ×\times 则可以直接合并。至此,我们说明了算法的正确性。

    从小到大枚举区间这件事可以通过从小到大枚举右端点 rr,再从大到小枚举左端点 ll 实现,这个过程与处理中缀表达式的栈是类似的,因此可以放一起处理,只不过枚举的 ll 到了最近的 ( 就应当停止。

    原序列的任意一个区间只会被枚举到一次,因此总复杂度 O(n2)O(n^2)。

    需要注意过程中可能得到较大的数,但实际上只要某个数大于了 10910^9,那它与相邻的数(除非是一列 11)必然是相乘优于相加,所以我们只需要记录每个数对 998244353998244353 取模的值,以及它的实际值是否已经大于 10910^9 即可。

    E

    n≤5n \leq 5 时按样例的方式构造,否则答案一定不小于 44,其实按 44 构造即可,具体方法为 ai=i mod 4+1a_i = i \bmod 4+1。

    因为考虑质数要么为 22 要么为奇数。

    如果两个数异或起来为 22,考虑 x⊕y=2x \oplus y=2,那么一定有 ∣x−y∣=2|x-y|=2,因此两个数模 44 的值不同。

    如果两个数异或起来为奇数,那么两个数奇偶性不同,因此两个数模 44 的值不同。

    所以两个数异或起来为质数,那么模 44 的权值一定不同。

    有些选手利用如下方式构造,给第 ii 个数染色时搜索前 i−1i-1 个数 j∈[1,i−1]j \in [1,i-1],如果 j⊕ij \oplus i 为质数,那么把所有jj 中的颜色提出来,染成第一个没有出现过的颜色,如果所有颜色均出现,那么 k+1k+1,以下是一组反例:

    n=18,k=5:n=18,k=5: 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
    上传者