1 条题解

  • 0
    @ 2026-11-12 21:02:48

    T1 宝石项链(necklace)题解

    题意简述

    有一个长度为 nn 的环形 0101 序列。一次操作选择位置 ii,翻转 i−1,i,i+1i-1,i,i+1 三位(下标模 nn),代价为 cic_i。求让所有位置颜色相同的最小总代价,无解输出 −1-1。

    思路

    操作次数可以看成 0/10/1 变量

    对同一个位置操作两次,等价于没有操作;而所有 ci>0c_i>0,所以最优方案中每个位置至多操作一次。设

    $$x_i=\begin{cases}1,&\text{对位置 }i\text{ 操作一次}\\0,&\text{不操作}\end{cases}$$

    最终第 ii 位的颜色只取决于它被翻转次数的奇偶性。

    固定目标颜色

    枚举最终颜色 t∈{0,1}t\in\{0,1\}。令

    bi=ai⊕tb_i=a_i\oplus t

    则第 ii 位需要被翻转奇数次当且仅当 bi=1b_i=1。于是得到模 22 意义下的环形方程组

    $$x_{i-1}\oplus x_i\oplus x_{i+1}=b_i\qquad(1\le i\le n),$$

    其中下标模 nn 计算。

    枚举边界后线性递推

    当 n≥3n\ge 3 时,只要知道 x1x_1 和 xnx_n,就可以:

    1. 由第 11 个方程得到 x2=b1⊕xn⊕x1x_2=b_1\oplus x_n\oplus x_1;
    2. 由第 2,3,…,n−22,3,\dots,n-2 个方程依次得到 x3,x4,…,xn−1x_3,x_4,\dots,x_{n-1};
    3. 最后检查第 n−1n-1 个和第 nn 个方程是否成立。

    因此枚举 x1,xn∈{0,1}x_1,x_n\in\{0,1\} 共 44 种情况,每种情况 O(n)O(n) 递推并计算代价,取最小值即可。

    n=1n=1 时,操作一次会翻转自己一次,直接有 x1=b1x_1=b_1。

    n=2n=2 时,对位置 11 操作会翻转位置 11 一次、位置 22 两次(等于不变);对位置 22 操作同理。因此两次操作互不影响,x1=b1x_1=b_1,x2=b2x_2=b_2。

    什么时候无解?

    上面的枚举已经能处理所有情况。若想提前判断,可以这样看:

    • 当 3∤n3\nmid n 时,矩阵 I+S+S−1I+S+S^{-1} 在模 22 意义下可逆,因此对每种目标颜色都一定有解。
    • 当 3∣n3\mid n 时,核空间由两个周期为 33 的向量张成,方程组有解当且仅当下标模 33 的三个同余类中 bib_i 的和的奇偶性相同。把 bb 换成 1−b1-b 会让三个和的奇偶性同时翻转,所以两种目标颜色的可解性相同:要么都有解,要么都无解。

    这也解释了样例 2:三个同余类中 11 的个数分别为 1,0,01,0,0,奇偶性不同,所以无解。

    正确性证明

    引理 1: 最优方案中每个位置至多操作一次。

    若某位置操作了至少两次,删去其中两次操作,所有位置被翻转次数的奇偶性不变,方案仍然合法,而代价严格减少(ci>0c_i>0),矛盾。

    引理 2: 固定 tt 后,方程组与“最终所有位置颜色为 tt”等价。

    第 ii 位最终颜色为 aia_i 异或(它被翻转次数的奇偶性)。它被翻转的次数为 xi−1+xi+xi+1x_{i-1}+x_i+x_{i+1},奇偶性即 xi−1⊕xi⊕xi+1x_{i-1}\oplus x_i\oplus x_{i+1}。要求最终颜色为 tt,即该异或值等于 ai⊕t=bia_i\oplus t=b_i。

    引理 3: 枚举 x1,xnx_1,x_n 并递推可以找到所有合法解。

    任意合法解都有某个 x1,xnx_1,x_n,而递推是由方程唯一确定的;若递推结果通过最后两个方程的检查,则所有 nn 个方程都成立。因此枚举不会漏解,也不会把不合法方案计入。

    定理: 算法输出的最小值就是答案。

    算法枚举了两种目标颜色和所有合法操作方案,并取最小代价;由引理 1、2、3,这覆盖了所有可能的最优方案。

    复杂度

    时间 O(n)O(n),常数约为 88 次线性扫描;空间 O(n)O(n)。

    参考代码(C++)

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main() {
        freopen("necklace.in", "r", stdin);
        freopen("necklace.out", "w", stdout);
    
        int n;
        if (scanf("%d", &n) != 1) return 0;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        vector<long long> c(n + 1);
        for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
    
        const long long INF = (long long)4e18;
        long long ans = INF;
    
        vector<int> b(n + 1), x(n + 1);
    
        for (int t = 0; t <= 1; t++) {
            for (int i = 1; i <= n; i++) b[i] = a[i] ^ t;
    
            for (int x1 = 0; x1 <= 1; x1++) {
                for (int xn = 0; xn <= 1; xn++) {
                    if (n == 1) {
                        // 唯一变量 x[1],操作一次会翻转自己一次
                        if (x1 == xn && x1 == b[1])
                            ans = min(ans, (long long)x1 * c[1]);
                        continue;
                    }
                    if (n == 2) {
                        // 对 i 操作会翻转 i 一次、另一颗宝石两次(等于不变)
                        if (x1 == b[1] && xn == b[2])
                            ans = min(ans, (long long)x1 * c[1] + (long long)xn * c[2]);
                        continue;
                    }
    
                    x[1] = x1;
                    x[n] = xn;
                    // 方程 1: x[n] xor x[1] xor x[2] = b[1]
                    x[2] = b[1] ^ x[n] ^ x[1];
                    for (int i = 2; i <= n - 2; i++)
                        x[i + 1] = b[i] ^ x[i - 1] ^ x[i];
    
                    // 检查最后两个方程
                    if ((x[n - 2] ^ x[n - 1] ^ x[n]) != b[n - 1]) continue;
                    if ((x[n - 1] ^ x[n] ^ x[1]) != b[n]) continue;
    
                    long long cost = 0;
                    for (int i = 1; i <= n; i++)
                        if (x[i]) cost += c[i];
                    ans = min(ans, cost);
                }
            }
        }
    
        if (ans >= INF / 2) puts("-1");
        else printf("%lld\n", ans);
        return 0;
    }
    

    易错点

    1. n=1,2n=1,2 的边界:n=1n=1 时一颗宝石永远“全部同色”,答案为 00;n=2n=2 时对一颗宝石操作不会影响另一颗。不能直接套用 n≥3n\ge 3 的递推。
    2. 两种目标颜色都要考虑:只考虑全部变成 00 会漏掉更便宜的全部变成 11 的方案。
    3. 无解条件不是“三个同余类和相等”,而是三个和的奇偶性相同。例如 n=9n=9 时三个和可以是 1,3,51,3,5,仍然有解。
    4. 代价要用 long long:n≤106n\le 10^6,ci≤109c_i\le 10^9,答案可达 101510^{15}。
    5. 不要忘记操作两次抵消:若允许 xi≥2x_i\ge 2,枚举会爆炸;但最优解中 xi∈{0,1}x_i\in\{0,1\}。

    测试点设计

    测试点 设计意图
    1 样例 1,答案为 44
    2 样例 2,3∣n3\mid n 且三个同余类奇偶性不同,无解
    3 n=1n=1,答案为 00
    4 n=2n=2,两颗颜色不同,答案为较便宜的一颗的代价
    5 n=3n=3 且颜色混合,无解
    6 n=3n=3 且全为 00,答案为 00
    7 n=6n=6,三个同余类奇偶性不同,无解
    8 n=9n=9,三个同余类都有解,检验非唯一解时的最小代价
    9 n=999999n=999999,随机数据并强制三个同余类奇偶性不同,输出 −1-1
    10 n=106n=10^6,随机颜色、所有 ci=1c_i=1,答案为最少操作次数
    11 n=106n=10^6,随机颜色、随机大代价,答案接近 2.5×10142.5\times 10^{14}
    12 n=999999n=999999,构造三个同余类都有解的大代价数据,检验长整型与无解判定的区分
    • 1

    信息

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