1 条题解

  • 0
    @ 2026-11-15 14:01:48

    题目分析

    20 pts

    对于20%的数据,有 1≤T≤5,1≤n,m≤51 \leq T \leq 5, 1 \leq n, m \leq 5。

    暴力搜索判断即可。

    50 pts

    对于50%的数据,有 1≤T≤5,1≤n≤1061 \leq T \leq 5, 1 \leq n \leq 10^6。

    递推:

    在不考虑环形即不考虑 A1A_1 与 AnA_n 是否同色时的方案数有 m(m−1)n−1m(m - 1)^{n-1}。将上面方案数减去 A1A_1 与 AnA_n 同色的方案数即把这两块当成同一区域,此时方案数为 an−1a_{n-1}。

    $$a_n = (m-1+1)(m - 1)^{n-1} - a_{n-1} \quad (n \geq 2)$$

    $a_n = (m - 1)^n+(m-1)^{n-1} - a_{n-1} \quad (n \geq 2)$​

    an−(m−1)n=−[an−1−(m−1)n−1]a_n - (m - 1)^n = -[a_{n-1} - (m - 1)^{n-1}]​

    bn−1=−bnb_{n-1}=-b_n

    bn=an−(m−1)nb_n=a_n-(m-1)^n 这个数列是一个公比为 −1-1​ 的等比数列

    b2,b3,b4,b5,....,bnb_2,b_3,b_4,b_5,....,b_n 公比为 −1-1 的等比数列

    b2=a2−(m−1)2=m∗(m−1)−(m−1)2=m−1b_2=a_2-(m-1)^2=m*(m-1)-(m-1)^2=m-1

    an=(m−1)×(−1)n−2+(m−1)na_n=(m-1) \times (-1)^{n-2}+(m-1)^n

    n=2n=2 代入 a2−(m−1)2a_2-(m-1)^2= m∗(m−1)−(m−1)2=m−1m*(m-1)-(m-1)^2=m-1

    首项为 m−1m-1 公比为 −1-1 的等比数列

    an=(−1)n−2(m−1)+(m−1)na_n =(-1)^{n-2}(m-1)+(m - 1)^n

    100 pts

    对于100%的数据,有 1≤T≤105,1≤n,m≤1091 \leq T \leq 10^5, 1 \leq n, m \leq 10^9。

    由上可知 an=m(m−1)n−1−an−1a_n = m(m - 1)^{n-1} - a_{n-1}

    整理得 an−(m−1)n=−[an−1−(m−1)n−1]a_n - (m - 1)^n = -[a_{n-1} - (m - 1)^{n-1}]

    令 bn=an−(m−1)nb_n = a_n - (m - 1)^n 则 {bn}\{b_n\} 是公比为 −1-1 首项 b2=m(m−1)−(m−1)2=m−1b_2 = m(m - 1) - (m - 1)^2 = m - 1 的等比数列:

    bn=(−1)n−2(m−1)(n≥2)b_n = (-1)^{n-2}(m - 1) \quad (n \geq 2)

    所以 $a_n = (m - 1)^n + (-1)^{n-2}(m - 1) \quad (n \geq 2)$

    游览计划

    • 考点:图论,bfs,贪心。
    • 难度:CSP-J T4

    测试点 1~3

    给暴力留的分。

    测试点4~8

    先通过bfs求出每个点到另一个点的最短路径的长度 di,jd_{i,j} ,然后暴力枚举四个点 a,b,c,da,b,c,d ,然后求 max⁡(da,b+db,c+dc,d)\max(d_{a,b}+d_{b,c}+d_{c,d}) 就可以了。

    复杂度 O(n4)O(n^4) 。

    测试点9~10

    答案就是 33,因为在完全图中,任意两点的最短路都是 11 。

    测试点11~15

    同样求出 di,jd_{i,j} ,然后暴力枚举三个点 a,b,ca,b,c ,然后求出离 cc 点最远的点 fcf_c,但是 fcf_c 可能是 aa 或者 bb ,所以需要求出离 cc 点第二远的点 gcg_c,第三远的点 hch_c ,这样就一定可以找出那个最远的点。

    复杂度是 O(n3)O(n^3) 。

    当然也有许多其他做法。

    测试点16~20

    优化上一个算法。

    同样求出 di,jd_{i,j} 和 fi,gi,hif_i,g_i,h_i 。

    我们枚举两个点 a,ba,b ,然后经过 a→ba\to b 的最远路径一定是 fa/ga/ha→a→b→fb/gb/hbf_a/g_a/h_a\to a\to b\to f_b/g_b/h_b 其中之一。

    依次考虑这几种情况,排除掉非法的情况(经过相同的点),直接枚举就可以了。

    复杂度是 O(n2)O(n^2) 。

    • 1

    信息

    ID
    82
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者