题目分析

我们有一个环形网络，N 台计算机排成环，每台计算机有一个 K 位二进制密钥。相邻计算机 i 和 i+1（环状）的密钥必须恰好有 W_i 位不同。要求构造一组满足所有 W_i 约束的密钥。

---

核心思路

1. 问题转化

设第 i 台计算机的密钥为二进制串 s_i，则约束条件为：

HammingDistance(s_i, s_{i+1}) = W_i  （对 i=1..N，其中 s_{N+1} = s_1）

这是一个在环上的约束满足问题。

---

2. 关键观察

2.1 相邻密钥的关系

从 s_i 到 s_{i+1}，我们可以通过翻转一些位来得到。设：

• _0t1[i] = 从 s_i 到 s_{i+1} 中从 0 翻转为 1 的位数
• _1t0[i] = 从 s_i 到 s_{i+1} 中从 1 翻转为 0 的位数

则有：

_0t1[i] + _1t0[i] = W_i  （总翻转位数等于汉明距离）

并且 s_i 中 1 的个数变化为：

popcount(s_{i+1}) = popcount(s_i) + _0t1[i] - _1t0[i]

---

2.2 环上的约束

由于是环形，所有变化必须闭合：

Σ(_0t1[i] - _1t0[i]) = 0  （i=1..N）

结合 _1t0[i] = W_i - _0t1[i]，得到：

Σ(2 * _0t1[i] - W_i) = 0
=> Σ_0t1[i] = ΣW_i / 2

因此解存在的必要条件：所有 W_i 之和必须是偶数。

---

3. 算法设计

3.1 动态规划

代码使用 DP 判断解的存在性：

• f[i][j] 表示考虑前 i 台计算机，第 i 台密钥中 1 的个数为 j 是否可行
• 转移时，根据 W_i 约束计算可能的 j 范围

3.2 构造解

如果解存在：

1. 从最后一台计算机反向推导，确定每对相邻密钥的 _0t1 和 _1t0 值
2. 维护两个集合 _0 和 _1，分别记录当前密钥中 0 和 1 的位置
3. 依次构造每个密钥：
   • 从 _0 中选 _0t1 个位置翻转为 1
   • 从 _1 中选 _1t0 个位置翻转为 0
   • 更新集合

---

4. 算法流程

1. 检查解的存在性：

   • 计算所有 W_i 之和，如果是奇数则无解
   • 使用 DP 验证是否存在满足约束的 1 的个数序列

2. 反向推导：

   • 从最后一台计算机开始，确定每对相邻计算机的翻转方案

3. 正向构造：

   • 从全 0 密钥开始
   • 依次应用翻转操作，构造每个密钥
   • 维护 0 和 1 的位置集合，确保翻转操作可行

---

5. 复杂度分析

• DP 过程：O(N × K)
• 构造过程：O(N × K)
• 总复杂度：O(Σ(N×K)) ≤ O(5,000,000)

满足题目约束。

---

6. 样例验证

样例 1

输入：5 3, W = [2,1,3,0,2]
处理：
- 总和 2+1+3+0+2=8 为偶数，有解
- 构造密钥序列：
  000 → 110 (翻转2位)
  110 → 010 (翻转1位) 
  010 → 101 (翻转3位)
  101 → 101 (翻转0位)
  101 → 000 (翻转2位)
输出与样例一致。

样例 3

输入：2 3, W = [2,1]
处理：
- 总和 2+1=3 为奇数，无解
输出 NO。

---

7. 关键优化

7.1 差分优化

DP 转移时使用差分数组，将区间标记优化为 O(1) 操作。

7.2 集合维护

使用向量维护 0 和 1 的位置，通过切片操作高效实现位翻转。

---

算法标签

• 动态规划 (Dynamic Programming)
• 构造算法 (Constructive Algorithm)
• 汉明距离 (Hamming Distance)
• 环状约束 (Circular Constraints)

---

总结

本题通过分析环形网络上汉明距离约束的数学性质，将其转化为 1 的个数的变化问题，利用动态规划判断解的存在性，再通过巧妙的位翻转构造具体的密钥方案。核心在于发现 ΣW_i 必须为偶数的必要条件，以及通过维护位位置集合来高效构造解。