（十）从样例猜想到证明与构造

样例可以启发猜想，但样例中没有出现的情况也需要解释。可以先观察操作改变了什么，再寻找没有改变的量，最后尝试构造一份完整方案。

1. 完整示例：相邻两盏灯的翻转

题目原文（自拟）： 有 n 盏排成一行的灯，0 表示关闭，1 表示点亮。一次操作选择相邻两盏灯，同时翻转它们的状态。判断能否把所有灯关闭。能做到时，输出 YES，下一行输出操作次数，第三行输出每次操作的左侧灯编号；做不到时只输出 NO。灯从 1 编号。第一行输入整数 n，\(1\le n\le200000\)；第二行输入一个长度为 n 的 01 字符串。

样例输入：

5
10111

样例输出：

YES
3
1 2 4

先试 11→00，再试 10→01。一次翻转让亮灯数量减少 2、增加 2 或保持不变，因此亮灯数量的奇偶性始终不变。全部关闭时亮灯数量为 0，奇数盏亮灯无法变成这个结果。

亮灯数为偶数就一定能做到吗？从左向右处理：当前灯已经关闭就前进；当前灯亮着，就翻转它与右邻灯。这样当前灯变成 0，以后只操作右边的位置，不再碰它。

样例依次变为 10111→01111→00011→00000，操作左侧编号为 1、2、4。处理完前 n-1 盏后，只剩最后一盏可能亮着；此时亮灯数仍为偶数，因此最后一盏也只能是 0。这同时给出了充分性证明和实际操作方案。

我们得到等价关系：能全部关闭，当且仅当初始亮灯数为偶数。 奇偶性解释做不到的原因，逐项关闭的构造解释做得到的原因，两部分合起来才覆盖所有输入。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n;
    string lights;
    cin >> n >> lights;
    int ones = 0;
    for (char state : lights) {
        ones += state == '1'; // 每盏亮灯贡献 1，先检查奇偶性。
    }
    if (ones % 2 != 0) {
        cout << "NO\n";
        return 0;
    }
    vector<int> operations;
    for (int i = 0; i + 1 < n; ++i) {
        if (lights[i] == '1') {
            lights[i] = '0'; // 翻转后锁定当前位置，后续不再碰它。
            lights[i + 1] = lights[i + 1] == '0' ? '1' : '0';
            operations.push_back(i + 1); // 输出使用题目的 1 起始编号。
        }
    }
    cout << "YES\n" << operations.size() << '\n';
    for (int i = 0; i < static_cast<int>(operations.size()); ++i) {
        if (i > 0) cout << ' ';
        cout << operations[i];
    }
    cout << '\n'; // 没有操作时，这一行为空。
}

代码解释： 前面的计数得到判定，后面的循环把充分性证明直接写成程序。0 得到 YES、0 次操作和空行；1 得到 NO；10 得到 NO，而不是因为“至少有两盏”就判定成功。每个位置只处理一次，时间为 \(O(n)\)，保存方案需要 \(O(n)\) 空间。

这里用到两种证明方法：从操作前后的变化得到不变量，从目标反推可执行步骤得到构造。后面遇到交换、翻转或移动题，也可以先列出一次操作改变了哪些量。

练习： CF 4A — Watermelon（分别写出必要性与一个实际构造）；洛谷 P5717 — 三角形分类（区分存在三角形与三角形的类型）。

（十） 从样例猜想到证明与构造

1. 完整示例：相邻两盏灯的翻转

（十）从样例猜想到证明与构造