1 条题解

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

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

    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
    160
    时间
    2000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者