1 条题解
-
0
T1 宝石项链(necklace)题解
题意简述
有一个长度为 的环形 序列。一次操作选择位置 ,翻转 三位(下标模 ),代价为 。求让所有位置颜色相同的最小总代价,无解输出 。
思路
操作次数可以看成 变量
对同一个位置操作两次,等价于没有操作;而所有 ,所以最优方案中每个位置至多操作一次。设
$$x_i=\begin{cases}1,&\text{对位置 }i\text{ 操作一次}\\0,&\text{不操作}\end{cases}$$最终第 位的颜色只取决于它被翻转次数的奇偶性。
固定目标颜色
枚举最终颜色 。令
则第 位需要被翻转奇数次当且仅当 。于是得到模 意义下的环形方程组
$$x_{i-1}\oplus x_i\oplus x_{i+1}=b_i\qquad(1\le i\le n),$$其中下标模 计算。
枚举边界后线性递推
当 时,只要知道 和 ,就可以:
- 由第 个方程得到 ;
- 由第 个方程依次得到 ;
- 最后检查第 个和第 个方程是否成立。
因此枚举 共 种情况,每种情况 递推并计算代价,取最小值即可。
时,操作一次会翻转自己一次,直接有 。
时,对位置 操作会翻转位置 一次、位置 两次(等于不变);对位置 操作同理。因此两次操作互不影响,,。
什么时候无解?
上面的枚举已经能处理所有情况。若想提前判断,可以这样看:
- 当 时,矩阵 在模 意义下可逆,因此对每种目标颜色都一定有解。
- 当 时,核空间由两个周期为 的向量张成,方程组有解当且仅当下标模 的三个同余类中 的和的奇偶性相同。把 换成 会让三个和的奇偶性同时翻转,所以两种目标颜色的可解性相同:要么都有解,要么都无解。
这也解释了样例 2:三个同余类中 的个数分别为 ,奇偶性不同,所以无解。
正确性证明
引理 1: 最优方案中每个位置至多操作一次。
若某位置操作了至少两次,删去其中两次操作,所有位置被翻转次数的奇偶性不变,方案仍然合法,而代价严格减少(),矛盾。
引理 2: 固定 后,方程组与“最终所有位置颜色为 ”等价。
第 位最终颜色为 异或(它被翻转次数的奇偶性)。它被翻转的次数为 ,奇偶性即 。要求最终颜色为 ,即该异或值等于 。
引理 3: 枚举 并递推可以找到所有合法解。
任意合法解都有某个 ,而递推是由方程唯一确定的;若递推结果通过最后两个方程的检查,则所有 个方程都成立。因此枚举不会漏解,也不会把不合法方案计入。
定理: 算法输出的最小值就是答案。
算法枚举了两种目标颜色和所有合法操作方案,并取最小代价;由引理 1、2、3,这覆盖了所有可能的最优方案。
复杂度
时间 ,常数约为 次线性扫描;空间 。
参考代码(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; }易错点
- 的边界: 时一颗宝石永远“全部同色”,答案为 ; 时对一颗宝石操作不会影响另一颗。不能直接套用 的递推。
- 两种目标颜色都要考虑:只考虑全部变成 会漏掉更便宜的全部变成 的方案。
- 无解条件不是“三个同余类和相等”,而是三个和的奇偶性相同。例如 时三个和可以是 ,仍然有解。
- 代价要用
long long:,,答案可达 。 - 不要忘记操作两次抵消:若允许 ,枚举会爆炸;但最优解中 。
测试点设计
测试点 设计意图 1 样例 1,答案为 2 样例 2, 且三个同余类奇偶性不同,无解 3 ,答案为 4 ,两颗颜色不同,答案为较便宜的一颗的代价 5 且颜色混合,无解 6 且全为 ,答案为 7 ,三个同余类奇偶性不同,无解 8 ,三个同余类都有解,检验非唯一解时的最小代价 9 ,随机数据并强制三个同余类奇偶性不同,输出 10 ,随机颜色、所有 ,答案为最少操作次数 11 ,随机颜色、随机大代价,答案接近 12 ,构造三个同余类都有解的大代价数据,检验长整型与无解判定的区分
- 1
信息
- ID
- 6
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者