1 条题解

  • 0
    @ 2026-11-15 18:30:12

    题目分析

    追忆(recall)题解

    一个字符串可以被重排为回文串当且仅当最多只有一种字符的出现次数为奇数。

    一个字符串可以被重排为循环串当且仅当所有字符串的出现次数的最大公约数大于 11。

    如果一个字符串可以被重排为回文串且长度为偶数,那么它同时也能被重排为循环串(每种字符出现次数均为偶数,所以存在公约数 22)。

    据此模拟即可。

    遥远(distance)题解

    直接建图然后 bfs 是 O(n4)O(n^4) 的,因为有 O(n3)O(n^3) 个点,每次拓展时需要枚举同轴的 O(n)O(n) 个点。

    注意到同一条轴线上的点一定按奇偶性被分为了两类,每个类内部都是一个团,可以在一步之内互相到达。不难想到对三个方向的 O(n2)O(n^2) 条轴线各自开一个桶表示这条轴线上的团是否被到达过,这样就可以快速剪掉重复的判断。复杂度降至 O(n3)O(n^3),可以通过本题。

    梦境(dream)题解

    一根长度为 xx 的木材最终会被切割成 xx 根长度为 11 的木材,而且在这个过程中最多会产生 O(log⁡x)O(\log x) 种不同长度的木棍。这启发我们预先把所有木材可能产生的长度处理出来,然后预处理出 SiS_i 表示如果经过了若干次切割后最长的木材长度变为 ii 那么一共会产生多少根长度为 11 的木材。询问 kk 就只需要在这个数组上二分。复杂度视实现而定。

    清澈(transparent)题解

    题意抽象出来是:定义两个序列 a,ba,b 匹配当且仅当 ∀i∈[1,n−1],ai<ai+1  ⟺  bi<bi+1\forall i\in[1,n-1],a_i<a_{i+1}\iff b_i<b_{i+1}。给定一个固定的序列 aa,多次询问给定 bb 问 aa 中是否存在子序列与 bb 匹配。

    这题最关键的性质是,aa 中所有以第 ii 个位置为结尾的与查询序列的某个前缀匹配的子序列里只需要保留最长的那个。或者说,如果存在合法子序列,那么一定存在一个合法子序列使得,以这个子序列里的每个位置为结尾拿出来的子序列都是以这个位置为结尾时最长的匹配。这个性质的证明有很多种方法,可以归纳证明,也可以分类讨论+调整法。

    有了这个性质之后就可以 dp 了,对于每次询问,记询问序列为 bb,记 fif_i 表示以 ii 为结尾的能与 bb 的某个前缀匹配的子序列中最长的长度。现在已知 f1,⋯ ,fif_1,\cdots,f_i,要求出 fi+1f_{i+1}。记 $C(x,y)=\begin{cases}1&(x>y)\\0&(x=y)\\-1&(x<y)\end{cases}$ 那么 fjf_j 会对 fi+1f_{i+1} 产生贡献当且仅当 C(bfi,bfi+1)=C(aj,ai)C(b_{f_i},b_{f_{i+1}})=C(a_j,a_i)。对 C(bfi,bfi+1)C(b_{f_i},b_{f_{i+1}}) 按 11 或 −1-1 分类,每一类里的转移与最长上升子序列(LIS)的转移是本质相同的。直接枚举的复杂度为 O(n2)O(n^2),用二分则可以优化至 O(nlog⁡n)O(n\log n)。总时间复杂度为 O(Tnlog⁡n)O(Tn\log n)。

    circle

    考察内容:动态规划,贪心,随机化

    20pts

    对于 k=3k=3,枚举 nkn^k​​,直接计算所有三元环最大的权值。

    因为对于三元环而言相对顺序不会改变环的形态,所以只需要枚举的三元点对是 n(n−1)(n−2)6\frac{n(n-1)(n-2)}{6} 个,在 n=1000n=1000 的情况下可以通过。

    另外20pts

    对于 xi=yix_i=y_i,容易观察到环上的点一定是 xix_i 最大或最小的若干个点。

    枚举所有可能的情况,即去枚举最小的 aa 个最大的 bb 个元素,然后 k!k! 枚举他们的相对顺序,计算所有情况中的最大值,单组数据的复杂度为 O(k×k!)O(k \times k!)​。

    100pts

    先考虑这么一个问题,找到一条长度为 kk 的路径,i1,i2,i3,…,iki_1,i_2,i_3,…,i_k,且满足 i1<i2<…<iki_1<i_2<…<i_k,最大化这条路径的长度。

    $|x_1-x_2|+|y_1-y_2|=\max(x_1+y_1-x_2+y_2,x_2+y_1-x_1-y_2,x_2+y_2-x_1-y_1,x_1+y_2-x_2-y_1)$

    我们将一个点拆分为 44 种情况 x1+y1,x1−y1,−x1+y1,−x1−y1x_1+y_1,x_1-y_1,-x_1+y_1,-x_1-y_1。

    我们会发现对于 22 个点,若前一个点选了第一种情况,第二个点就要选第四种情况。

    对应地,需要选 (2,3),(3,2),(4,1)(2,3),(3,2),(4,1),上述曼哈顿距离即为这四种情况中的最大值。

    因为我们最后要求解的就是一条长度为 kk 的最大路径,所以可以等效为下面这个问题。

    每个点都有 44 项权值,你需要找到一条长度为 kk 的路径,并给每两个相邻点赋 44 项权值中的某一项,且他们的方案只能是 (1,4),(2,3),(3,2),(4,1)(1,4),(2,3),(3,2),(4,1) 中的某一种。

    那么可以用下面这样一种DP方式,f[i][j][1/2/3/4]f[i][j][1/2/3/4] 表示考虑了前 ii 个点,当前路径长度为 jj,且最后一个点和下一个点的方式为 1/2/3/41/2/3/4 中的某一种时,它的最大权值。

    再考虑这么一个问题:

    找到一条长度为 kk 的环,i1,i2,i3,…,iki_1,i_2,i_3,…,i_k,且满足 i1<i2<…<iki_1<i_2<…<i_k,最大化这个环的长度。

    会发现 i1i_1 和 iki_k 之间还有一条连边,我们在原来的基础上再加一维,记录 i1i_1 的方式为 1/2/3/41/2/3/4 中的某一种,在考虑 iki_k 时补全这一项。

    现在回到原问题,我们发现如果最优解最终满足 i1<i2<…<iki_1<i_2<…<i_k 的话,我们套用上述方式已经求解出了答案,但现在最优解不一定满足这个条件。

    我们思考一下如果序列随机,一个大小为 kk 的环有 kk 种拆分方式,且从左往右和从右往左是不影响这个环的形态的,即有 2(k−1)!\frac{2}{(k-1)!} 的概率用上述方式得到答案。

    我们考虑随机打乱整个序列多次,然后将所有解取最优值,当 k=6k=6 时概率为 160\frac{1}{60}

    而

    1−(5960)500≈0.99981-(\frac{59}{60})^{500}≈0.9998

    正确率足够高,也可以提高随机次数获得更高的正确率。

    整体复杂度为 P×nkP \times nk,其中 PP 为随机次数。

    • 1

    信息

    ID
    156
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者