我将以连载的形式每天为大家公布一道题目的参考答案,希望能给初学者一些启发.

点灯问题的背景同，它们的解题原理也是相同的：那就是当某盏灯的状态变化奇数次时，相当于变化1次，而变化偶数次时，相当于变化0次。通常有两种方法：常规法和特殊法。
常规法直接从问题出发，用数组来存储每一盏灯的信息（包括”暗亮“情况和”是否操作“信息），目的明确，思路清晰，也很容易理解，但是当灯的数量较大时（大于15盏），运算量很大，不但速度很慢，而且可能出现内存不足的情况。
特殊法是利用位运算来加快速度和减小内存空间的方法，它一般用一个32位的长整型变量来表示一行灯，变量的每一位对应一盏灯，操作原理是将它和自身以及周围的灯进行异或运算，异或运算的结果即表示它的”暗亮“情况。特殊法虽快，但要求每行灯的数量不可超过32。
    在学习过程中，我收集整理了上述问题的一些解法，现在就请它们一一亮相！
（问题背景描述略）

/*
问题一：已知初始时每盏灯都处于熄灭状态，现在依次对编号为i(0 <= i < n)的灯操作i次，
求最后所有灯的”暗亮“情况。
函数接口: void Solve(const int start[], int end[], int n);
其中：start[]表示了初始状态，它的每个元素均为0，表示初始时每盏灯都处于熄灭状态；
end[]表示了目标状态，需要返回目标状态，即最后所有灯的”暗亮“情况。
n表示有n盏灯。
*/


#include <iostream>
#include <time.h>

using namespace std;

const int Max = 32;

typedef unsigned long ul;

void Solve1(const int start[], int end[], int n);
void Solve2(const int start[], int end[], int n);

int main()
{
      time_t startTime;
    time_t endTime;
    time(&startTime);

      int a[Max] = {0};
      int b[Max] = {0};
      
      Solve1(a, b, Max);
      for (int i=0; i<Max; i++)
            cout << b[i] << ' ';
      cout << endl;
      
      Solve2(a, b, Max);
      for (int i=0; i<Max; i++)
            cout << b[i] << ' ';
      cout << endl;
      
    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

/*常规方法
算法介绍：很明显当某盏灯的状态变化奇数次时，相当于变化1次，而变化偶数次时，相当于变化0次,
即相当于编号为奇数的灯被操作1次，编号为偶数的灯被操作0次。
分别用数组operate[]和status[]表示每盏灯的操作情况和”暗亮“情况，根据操作规则对每盏灯进行相应操作，
并记录”暗亮“变化情况。
*/
void Solve1(const int start[], int end[], int n)
{
      int *status = new int[n];
      int *operate = new int[n];
      for (int i=0; i<n; i++) //数组初始化
      {
            status[i] = start[i];
            operate[i] = 0;
      }
      
      for (int i=0; i<n; i++) //执行操作
      {
            if (i%2 == 1)
            {
                  operate[i] = 1;
                  status[i]++;
                  if (i > 0)
                        status[i-1]++;
                  if (i < n-1)
                        status[i+1]++;
            }
      }
      
      for (int i=0; i<n; i++) //记录目标状态
      {
            if (status[i]%2 == 0)
                  end[i] = 0;
            else
                  end[i] = 1;
      }
}

/*特殊方法
算法介绍：很明显当某盏灯的状态变化奇数次时，相当于变化1次，而变化偶数次时，相当于变化0次,
即相当于编号为奇数的灯被操作1次，编号为偶数的灯被操作0次。
当每行灯的数量不超过32时，用一个32位的长整型变量来表示一行灯，变量的每一位对应一盏灯，
操作原理是将它和自身以及周围的灯进行异或运算，异或运算的结果即表示它的”暗亮“情况。
分别用32位的长整型变量operate和status表示每盏灯的操作情况和”暗亮“情况，根据操作规则对每盏灯进行相应操作，
并记录”暗亮“变化情况。
*/
void Solve2(const int start[], int end[], int n)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            end[0] = 1;
            return ;
      }
      
      //const ul max = (1<<n) - 1; //若这样写，n只能到31，不然位移32个bit，是未定义行为
      const ul max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数),也表示所有灯都亮的情况
      ul temp; //临时变量
      ul status = 0;//表示每盏灯的”暗亮“情况
      ul operate = 0;//记录每盏灯的操作情况
      for (int i=0; i<n; i++) //把灯的信息记录到用二进制数表示的长整型变量的每一位中
      {
            temp = start[i] & max;
            status |= temp << (n-1-i);
            
            temp = (i%2) & max;
            operate |= temp << (n-1-i);
      }
//
//    cout << "b= "<<status<<" e = "<<operate<<endl;
//    for (int i=n-1; i>=0; i--)
//            cout <<((operate >> i) & 1) <<' ';
//    cout<<endl;
      status ^= operate & max; //影响自身
      status ^= (operate << 1) & max; //影响左边的灯
      status ^= (operate >> 1) & max; //影响右边的灯
      
      for (int i=n-1; i>=0; i--) //提取二进制整数每一位的值，记录目标状态
            end[n-i-1] = (status >> i) & 1;
}

你是个好人！

void Solve1(const int start[], int end[], int n)
{
    int i;

    if (n == 1) {
        end[0] = 1;
        return;
    }
    for (i = 1; i < n - 1; ++i)
        end[i] = 1;
}

/*
问题二：已知初始时每盏灯都处于熄灭状态，现在从第一盏灯开始，每隔i(0 <= i <= n/2)盏灯操作一次，
求最后所有灯的”暗亮“情况。例如：当i=2时，需要操作的灯为第1，3，6，。。。盏灯。
      函数接口: void Solve(const int start[], int end[], int n, int distance);
其中：start[]表示了初始状态，它的每个元素均为0，表示初始时每盏灯都处于熄灭状态；
end[]表示了目标状态，需要返回目标状态，即最后所有灯的”暗亮“情况。
n表示有n盏灯，distance表示每隔distance盏灯操作一次。
*/

#include <iostream>
#include <time.h>

using namespace std;

const int Max = 32;

typedef unsigned long ul;

void Solve1(const int start[], int end[], int n, int distance);
void Solve2(const int start[], int end[], int n, int distance);

int main()
{
      time_t startTime;
    time_t endTime;
    time(&startTime);

      int a[Max] = {0};
      int b[Max] = {0};

      Solve1(a, b, Max, 3);
      for (int i=0; i<Max; i++)
            cout << b[i] << ' ';
      cout << endl;

      Solve2(a, b, Max, 3);
      for (int i=0; i<Max; i++)
            cout << b[i] << ' ';
      cout << endl;


    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

/*常规方法
算法介绍：从第一盏灯开始，每隔i(0 <= i <= n/2)盏灯操作一次，即相当于编号为n*(i+1)的灯被操作1次。
分别用数组operate[]和status[]表示每盏灯的操作情况和”暗亮“情况，根据操作规则对每盏灯进行相应操作，
并记录”暗亮“变化情况。
*/
void Solve1(const int start[], int end[], int n, int distance)
{
      int *status = new int[n];
      int *operate = new int[n];
      for (int i=0; i<n; i++) //数组初始化
      {
            status[i] = start[i];
            operate[i] = 0;
      }

      for (int i=0; i<n; i++) //执行操作
      {
            if (i%(distance+1) == 0)
            {
                  operate[i] = 1;
                  status[i]++;
                  if (i > 0)
                        status[i-1]++;
                  if (i < n-1)
                        status[i+1]++;
            }
      }

      for (int i=0; i<n; i++) //记录目标状态
      {
            if (status[i]%2 == 0)
                  end[i] = 0;
            else
                  end[i] = 1;
      }
}

/*特殊方法
算法介绍：很明显当某盏灯的状态变化奇数次时，相当于变化1次，而变化偶数次时，相当于变化0次,
即相当于编号为奇数的灯被操作1次，编号为偶数的灯被操作0次。
当每行灯的数量不超过32时，用一个32位的长整型变量来表示一行灯，变量的每一位对应一盏灯，
操作原理是将它和自身以及周围的灯进行异或运算，异或运算的结果即表示它的”暗亮“情况。
分别用32位的长整型变量operate和status表示每盏灯的操作情况和”暗亮“情况，根据操作规则对每盏灯进行相应操作，
并记录”暗亮“变化情况。
*/
void Solve2(const int start[], int end[], int n, int distance)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            end[0] = 1;
            return ;
      }

      //const ul max = (1<<n) - 1; //若这样写，n只能到31，不然位移32个bit，是未定义行为
      const ul max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数),也表示所有灯都亮的情况
      ul temp; //临时变量
      ul status = 0;//表示每盏灯的”暗亮“情况
      ul operate = 0;//记录每盏灯的操作情况
      for (int i=0; i<n; i++) //把灯的信息记录到用二进制数表示的长整型变量的每一位中
      {
            temp = start[i] & max;
            status |= temp << (n-1-i);

            if (i%(distance+1) == 0)
                  temp = 1;
            else
                  temp = 0;
            operate |= temp << (n-1-i);
      }
//
//    cout << "b= "<<status<<" e = "<<operate<<endl;
//    for (int i=n-1; i>=0; i--)
//            cout <<((operate >> i) & 1) <<' ';
//    cout<<endl;
      status ^= operate & max; //影响自身
      status ^= (operate << 1) & max; //影响左边的灯
      status ^= (operate >> 1) & max; //影响右边的灯

      for (int i=n-1; i>=0; i--) //提取二进制整数每一位的值，记录目标状态
            end[n-i-1] = (status >> i) & 1;
}

/*
问题三：已知初始时每盏灯都处于熄灭状态，请问如何操作可以使得所有的灯都被点亮，
并返回所需的操作次数。如果没有解则如果没有解则返回-1，多个解则只输出一个即可。
      函数接口: int Solve(int operation[], int n);
其中：operation[]存储每盏灯的”是否操作“信息，需要返回。0表示不对灯进行操作，1表示对灯进行操作。
n表示有n盏灯。
返回所需的操作次数。
*/

#include <iostream>
#include <time.h>

using namespace std;

const int Max = 26;

typedef unsigned long ul;

int Solve3(int operation[], int n);
int Solve2(int operation[], int n);
int Solve1(int operation[], int n);
bool Solution(bool status[], int operation[], int max, int top);

int main()
{
      time_t startTime;
    time_t endTime;
    time(&startTime);

      int a[Max] = {0};
      int b[Max] = {0};

      int n;
      n = Solve1(a, Max);
      if (-1 != n)
      {
            cout << n << endl;
            for (int i=0; i<Max; i++)
                  cout << a[i] << ' ';
            cout << endl;
      }


      //n = Solve2(a, Max);
//      if (-1 != n)
//      {
//            cout << n << endl;
//            for (int i=0; i<Max; i++)
//                  cout << a[i] << ' ';
//            cout << endl;
//      }
//
//      n = Solve3(a, Max);
//      if (-1 != n)
//      {
//            cout << n << endl;
//            for (int i=0; i<Max; i++)
//                  cout << a[i] << ' ';
//            cout << endl;
//      }

    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

/*常规方法
算法介绍：每盏灯有操作和不操作两种情况，穷举所有可能的情况，当出现解时，返回所需的操作次数。
若穷举结束仍没有出现解，则表示无解，返回-1。
用数组status[]表示每盏灯的”暗亮“情况，根据操作规则对每盏灯进行相应操作，并记录”暗亮“变化情况。
*/
int Solve1(int operation[], int n)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            operation[0] = 1;
            return 1;
      }

      bool *status = new bool[n];
      for (int i=0; i<n; i++) //数组初始化
            status[i] = false;

      bool flag = Solution(status, operation, n, 0); //回溯求解
      delete []status;
      
      if (flag)
      {
            int sum = 0;
            for (int i=0; i<n; i++)
            {
                  if (operation[i] == 1)
                        sum++;
            }
            return sum;
      }
      else
            return -1;
}

bool Solution(bool status[], int operation[], int max, int top)
{
      if (top < max)//正在依次处理各盏灯
      {
            bool flag;
            operation[top] = 0; //不操作该灯
            flag = Solution(status, operation, max, top+1); //回溯求解

            if (!flag)//若无解，则操作该灯
            {
                  operation[top] = 1;//操作该灯，改变其自身及周围的灯的状态
                  status[top] = !status[top];
                  if (top > 0)
                        status[top-1] = !status[top-1];
                  if (top < max-1)
                        status[top+1] = !status[top+1];

                  flag = Solution(status, operation, max, top+1);//回溯求解
                  //把各盏灯的状态再变回来，以便下一次的递归调用
                  status[top] = !status[top];
                  if (top > 0)
                        status[top-1] = !status[top-1];
                  if (top < max-1)
                        status[top+1] = !status[top+1];
            }
            return flag;
      }
      else //所有的灯都操作完毕，判断是否有解
      {
            for (int i=0; i<top; i++)
            {
                  if (!status[i])
                        return false;
            }
            return true;
      }
}

/*特殊方法
算法介绍：每盏灯有操作和不操作两种情况，穷举所有可能的情况，当出现解时，返回所需的操作次数。
当每行灯的数量不超过32时，用一个32位的长整型变量来表示一行灯，变量的每一位对应一盏灯，
操作原理是将它和自身以及周围的灯进行异或运算，异或运算的结果即表示它的”暗亮“情况。
分别用32位的长整型变量operate和status表示每盏灯的操作情况和”暗亮“情况，根据操作规则对每盏灯进行相应操作，
并记录”暗亮“变化情况。
*/
int Solve2(int operation[], int n)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            operation[0] = 1;
            return 1;
      }
    //const ul max = (1<<n) - 1; //若这样写，n只能到31，不然位移32个bit，是未定义行为
      const ul max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数),也表示所有灯都亮的情况
      ul status; //用来存储灯的”暗亮“情况，status的每一位表示一盏灯
      ul operate;//用来存储灯的”是否操作“信息，operate的每一位表示一盏灯

      for (ul click = 0; click <= max; click++)
      {
            status = 0;
            operate = click;
        
            status ^= operate & max;  //影响自身
            status ^= (operate << 1) & max; //影响左边的灯
            status ^= (operate >> 1) & max; //影响右边的灯

            if (status == max)//如果灯全亮，表示有解
            {
                  for (int i=n-1; i>=0; i--) //提取二进制整数每一位的值，记录目标状态
                        operation[n-i-1] = (operate >> i) & 1;

                  int sum = 0;
                  for (int i=0; i<n; i++)
                  {
                        if (operation[i] == 1)
                              sum++;
                  }
                  return sum;
            }
      }
      return -1;
}

/*一个由观察及推理而得到的特殊方法
算法介绍：罗列n=1。。。9的解：
1： 1； 2： 0 1； 3： 0 1 0； 4： 1 0 0 1； 5： 0 1 0 0 1； 6： 0 1 0 0 1 0；
7： 1 0 0 1 0 0 1； 8： 0 1 0 0 1 0 0 1； 9： 0 1 0 0 1 0 0 1 0。
你是否发现一个有趣的规律？
除n=1和n=2外，当n%3==0时，解是（n/3）个 0 1 0 ；
当n%3==1时，解是（n/3）个 1 0 0 ，加上最后一个 1 ；
当n%3==2时，解是（n/3）个 0 1 0，加上最后两个 0 1 ；
      根据这个规律，我们可以得到一个非常快的算法，可以处理n为任意正整数的情况。
*/
int Solve3(int operation[], int n)
{
      if (n == 1) //如果只有 1 盏灯,直接返回结果
      {
            operation[0] = 1;
            return 1;
      }
      if (n == 2) //如果只有 2 盏灯,直接返回结果
      {
            operation[0] = 1;
            operation[1] = 0;
            return 1;
      }
      if (n % 3 == 0) //当n%3==0时，解是（n/3）个 0 1 0
      {
            for (int i=0; i<n; i+=3)
            {
                  operation[i] = 0;
                  operation[i+1] = 1;
                  operation[i+2] = 0;
            }
      }
      else if (n % 3 == 1)//当n%3==1时，解是（n/3）个 1 0 0 ，加上最后一个 1
      {
            for (int i=0; i<n-1; i+=3)
            {
                  operation[i] = 1;
                  operation[i+1] = 0;
                  operation[i+2] = 0;
            }
            operation[n-1] = 1;
      }
      else //当n%3==2时，解是（n/3）个 0 1 0，加上最后两个 0 1
      {
            for (int i=0; i<n-2; i+=3)
            {
                  operation[i] = 0;
                  operation[i+1] = 1;
                  operation[i+2] = 0;
            }
            operation[n-2] = 0;
            operation[n-1] = 1;
      }
      
      int sum = 0;
      for (int i=0; i<n; i++)
      {
            if (operation[i] == 1)
                  sum++;
      }
      return sum;
}

/*
问题四：问题三的扩展，已知初始时每盏灯都处于熄灭状态，请问如何操作可以使得所有的灯都被点亮，
并返回所需的最少操作次数，如果没有解则返回-1。
      函数接口: int MinSolve(int operation[], int n);
其中：operation[]存储每盏灯的”是否操作“信息，需要返回。0表示不对灯进行操作，1表示对灯进行操作。
n表示有n盏灯。
返回所需的最少操作次数。
*/
#include <iostream>
#include <time.h>

using namespace std;

const int Max = 26;

typedef unsigned long ul;

int Solve3(int operation[], int n);
int Solve2(int operation[], int n);
int Solve1(int operation[], int n);
void Solution(bool status[], int operate[], int operation[], int max, int top, int& min);

int main()
{
      time_t startTime;
    time_t endTime;
    time(&startTime);

      int a[Max] = {0};
      int b[Max] = {0};

      int n;
      n = Solve2(a, Max);
      if (-1 != n)
      {
            cout << n << endl;
            for (int i=0; i<Max; i++)
                  cout << a[i] << ' ';
            cout << endl;
      }


      n = Solve1(a, Max);
      if (-1 != n)
      {
            cout << n << endl;
            for (int i=0; i<Max; i++)
                  cout << a[i] << ' ';
            cout << endl;
      }

    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

/*常规方法
算法介绍：每盏灯有操作和不操作两种情况，穷举所有可能的情况，当出现解时，判断是否优于前面求得的解。
返回最优解；若穷举结束仍没有出现解，则表示无解，返回-1。
用数组status[]表示每盏灯的”暗亮“情况，根据操作规则对每盏灯进行相应操作，并记录”暗亮“变化情况。
*/
int Solve1(int operation[], int n)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            operation[0] = 1;
            return 1;
      }

      bool *status = new bool[n];
      for (int i=0; i<n; i++) //数组初始化
            status[i] = false;

      int *operate = new int[n];//用来存储每一个可能的解
      int min = n + 1; //存储所需的最少操作数
      
      Solution(status, operate, operation, n, 0, min);//回溯求最优解
      delete []status;
      delete []operate;

      if (min > n)
            min = -1;

      return min;
}

void Solution(bool status[], int operate[], int operation[], int max, int top, int& min)
{
      if (top < max)//正在依次处理各盏灯
      {
            operate[top] = 0; //不操作该灯
            Solution(status, operate, operation, max, top+1, min); //回溯求解

            operate[top] = 1;//操作该灯，改变其自身及周围的灯的状态
            status[top] = !status[top];
            if (top > 0)
                  status[top-1] = !status[top-1];
            if (top < max-1)
                  status[top+1] = !status[top+1];

            Solution(status, operate, operation, max, top+1, min);//回溯求解
            //把各盏灯的状态再变回来，以便下一次的递归调用
            status[top] = !status[top];
            if (top > 0)
                  status[top-1] = !status[top-1];
            if (top < max-1)
                  status[top+1] = !status[top+1];
      }
      else //所有的灯都操作完毕，判断是否有解
      {
            int i = 0;
            for (; i<top; i++)
            {
                  if (!status[i])
                        break;
            }
            if (i == top) //如果有解，判断是否优于前面求得的解
            {
                  int sum = 0;
                  for (int i=0; i<max; i++)
                  {
                        if (operate[i] == 1)
                              sum++;
                  }
                  if (sum < min)
                  {
                        min = sum;
                        for (int i=0; i<max; i++)
                              operation[i] = operate[i];
                  }
            }
      }
}
/////////////////////////////////////////////////////////////////////////////

/*特殊方法
算法介绍：
当每行灯的数量不超过32时，用一个32位的长整型变量来表示一行灯，变量的每一位对应一盏灯，
操作原理是将它和自身以及周围的灯进行异或运算，异或运算的结果即表示它的”暗亮“情况。
分别用32位的长整型变量operate和status表示每盏灯的操作情况和”暗亮“情况，根据操作规则对每盏灯进行相应操作，
并记录”暗亮“变化情况。
每盏灯有操作和不操作两种情况，穷举所有可能的情况，当出现解时，判断是否优于前面求得的解。
返回最优解。
*/
int Solve2(int operation[], int n)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            operation[0] = 1;
            return 1;
      }
    //const ul max = (1<<n) - 1; //若这样写，n只能到31，不然位移32个bit，是未定义行为
      const ul max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数),也表示所有灯都亮的情况
      ul status; //用来存储灯的”暗亮“情况，status的每一位表示一盏灯
      ul operate;//用来存储灯的”是否操作“信息，operate的每一位表示一盏灯
      ul answer; //用来存储最优解的灯的”是否操作“信息
      int min = n + 1;//存储所需的最少操作数


      for (ul click = 0; click <= max; click++)
      {
            status = 0;
            operate = click;

            status ^= operate & max;  //影响自身
            status ^= (operate << 1) & max; //影响左边的灯
            status ^= (operate >> 1) & max; //影响右边的灯

            if (status == max)//如果灯全亮，表示有解
            {
                  int sum = 0;
                  for (int i=n-1; i>=0; i--) //提取二进制整数每一位的值，累计操作数量
                        if ((operate >> i) & 1)
                              sum++;
                  if (sum < min) //判断是否优于前面求得的解
                  {
                        min = sum;
                        answer = operate;
                  }
            }
      }
      if (min <= n)
      {
            for (int i=n-1; i>=0; i--) //提取二进制整数每一位的值，记录目标状态
                  operation[n-i-1] = (answer >> i) & 1;
      }
      else
            min = -1;

      return min;
}

/*
问题五：问题四的扩展，现在给出n盏灯的初始的状态和目标状态，
要求计算：从初始状态改变到目标状态所需要的最少操作次数。如果没有解则如果没有解则返回-1。
      函数接口: int MinChange(const int Start[], const int End[], int n);
其中：start[]表示了初始状态，end[]表示了目标状态。n表示有n盏灯。
返回所需的最少操作次数。
如果增大难度，还可以要求返回操作情况，即把函数接口改为：
      函数接口: int MinChange(const int Start[], const int End[], int operation[], int n);
其中：start[]表示了初始状态，end[]表示了目标状态。n表示有n盏灯。
operation[]存储每盏灯的”是否操作“信息，需要返回。
返回所需的最少操作次数。
*/
#include <iostream>
#include <time.h>

using namespace std;

const int Max = 18;

typedef unsigned long ul;

int MinChange2(const int Start[], const int End[], int n);
int MinChange(const int Start[], const int End[], int n);
void Solution(bool status[], const bool end[], int operate[], int max, int top, int& min);
int MinChange(const int Start[], const int End[], int operation[], int n);
void Solution(bool status[], const bool end[], int operate[], int operation[], int max, int top, int& min);

int main()
{
      time_t startTime;
    time_t endTime;
    time(&startTime);

      int a[Max];     long sum = 0;
      int b[Max];
      for (int j=0; j<10; j++){
      for (int i=0; i<Max; i++)
      {
            a[i] = rand() % 2;
            b[i] = rand() % 2;
      }
      cout << "Beg :  ";
      for (int i=0; i<Max; i++)
            cout << a[i] << ' ';
      cout << endl;
      cout << "End :  ";
      for (int i=0; i<Max; i++)
            cout << b[i] << ' ';
      cout << endl;

      cout << "d= "<<MinChange(a, b, Max)<< endl;
      cout << "d= "<<MinChange2(a, b, Max)<< endl;


          //  sum+=(MinChange2(a, b, Max)!=MinChange3(a, b, Max))?1:0;
      }
     // cout<<"s="<<sum<<endl;
      //int operation[Max];
//      cout << "d= "<<MinChange(a, b, operation, Max)<< endl;
//      cout << "Ope :  ";
//      for (int i=0; i<Max; i++)
//            cout << operation[i] << ' ';
//      cout << endl;
    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

/*常规方法
算法介绍：每盏灯有操作和不操作两种情况，穷举所有可能的情况，当出现解时，判断是否优于前面求得的解。
返回最优解；若穷举结束仍没有出现解，则表示无解，返回-1。
用数组status[]表示每盏灯的”暗亮“情况，根据操作规则对每盏灯进行相应操作，并记录”暗亮“变化情况。
*/
int MinChange(const int Start[], const int End[], int n)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            if (Start[0] == End[0])
                  return 0;
            else
                  return 1;
      }

      bool *status = new bool[n];
      bool *end = new bool[n];
      for (int i=0; i<n; i++) //数组初始化
      {
            if (Start[i] == 0)
                  status[i] = false;
            else
                  status[i] = true;

            if (End[i] == 0)
                  end[i] = false;
            else
                  end[i] = true;
      }

      int *operate = new int[n];//用来存储每一个可能的解
      int min = n + 1; //存储所需的最少操作数

      Solution(status, end, operate, n, 0, min);//回溯求最优解
      delete []status;
      delete []operate;

      if (min > n)
            min = -1;

      return min;
}

void Solution(bool status[], const bool end[], int operate[], int max, int top, int& min)
{
      if (top < max)//正在依次处理各盏灯
      {
            operate[top] = 0; //不操作该灯
            Solution(status, end, operate, max, top+1, min); //回溯求解

            operate[top] = 1;//操作该灯，改变其自身及周围的灯的状态
            status[top] = !status[top];
            if (top > 0)
                  status[top-1] = !status[top-1];
            if (top < max-1)
                  status[top+1] = !status[top+1];

            Solution(status, end, operate, max, top+1, min);//回溯求解
            //把各盏灯的状态再变回来，以便下一次的递归调用
            status[top] = !status[top];
            if (top > 0)
                  status[top-1] = !status[top-1];
            if (top < max-1)
                  status[top+1] = !status[top+1];
      }
      else //所有的灯都操作完毕，判断是否有解
      {
            int i = 0;
            for (; i<top; i++)
            {
                  if (status[i] != end[i])
                        break;
            }
            if (i == top) //如果有解，判断是否优于前面求得的解
            {
                  int sum = 0;
                  for (int i=0; i<max; i++)
                  {
                        if (operate[i] == 1)
                              sum++;
                  }
                  if (sum < min)
                        min = sum;
            }
      }
}
/////////////要求返回操作的情况///////////////////////////////////////////
int MinChange(const int Start[], const int End[], int operation[], int n)
{
      if (n == 1) //如果只有一盏灯,直接返回结果
      {
            if (Start[0] == End[0])
                  return 0;
            else
                  return 1;
      }

      bool *status = new bool[n];
      bool *end = new bool[n];
      for (int i=0; i<n; i++) //数组初始化
      {
            if (Start[i] == 0)
                  status[i] = false;
            else
                  status[i] = true;

            if (End[i] == 0)
                  end[i] = false;
            else
                  end[i] = true;
      }

      int *operate = new int[n];//用来存储每一个可能的解
      int min = n + 1; //存储所需的最少操作数

      Solution(status, end, operate, operation, n, 0, min);//回溯求最优解
      delete []status;
      delete []operate;

      if (min > n)
            min = -1;

      return min;
}

void Solution(bool status[], const bool end[], int operate[], int operation[], int max, int top, int& min)
{
      if (top < max)//正在依次处理各盏灯
      {
            operate[top] = 0; //不操作该灯
            Solution(status, end, operate, operation, max, top+1, min); //回溯求解

            operate[top] = 1;//操作该灯，改变其自身及周围的灯的状态
            status[top] = !status[top];
            if (top > 0)
                  status[top-1] = !status[top-1];
            if (top < max-1)
                  status[top+1] = !status[top+1];

            Solution(status, end, operate, operation, max, top+1, min);//回溯求解
            //把各盏灯的状态再变回来，以便下一次的递归调用
            status[top] = !status[top];
            if (top > 0)
                  status[top-1] = !status[top-1];
            if (top < max-1)
                  status[top+1] = !status[top+1];
      }
      else //所有的灯都操作完毕，判断是否有解
      {
            int i = 0;
            for (; i<top; i++)
            {
                  if (status[i] != end[i])
                        break;
            }
            if (i == top) //如果有解，判断是否优于前面求得的解
            {
                  int sum = 0;
                  for (int i=0; i<max; i++)
                  {
                        if (operate[i] == 1)
                              sum++;
                  }
                  if (sum < min)
                  {
                        min = sum;
                        for (int i=0; i<max; i++)
                              operation[i] = operate[i];
                  }
            }
      }
}
/////////////////////////////////////////////////////////////////////////////
/*特殊方法
算法介绍：每盏灯有操作和不操作两种情况，穷举所有可能的情况，当出现解时，返回所需的操作次数。
当每行灯的数量不超过32时，用一个32位的长整型变量来表示一行灯，变量的每一位对应一盏灯，
操作原理是将它和自身以及周围的灯进行异或运算，异或运算的结果即表示它的”暗亮“情况。
分别用32位的长整型变量operate和status表示每盏灯的操作情况和”暗亮“情况，根据操作规则对每盏灯进行相应操作，
并记录”暗亮“变化情况。
*/
int MinChange2(const int Start[], const int End[], int n)
{
    //const ul max = (1<<n) - 1; //若这样写，n只能到31，不然位移32个bit，是未定义行为
      const ul max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数),也表示所有灯都亮的情况
      int min = n + 1; //存储所需的最少操作数

      if (n == 1)
      {
            if (Start[0] == End[0])
                  return 0;
            else
                  return 1;
      }

      ul begin = 0;
      ul end = 0;
      for (int i=0; i<n; i++)
      {
            if (Start[i]!=0)
                  begin += 1<<i;
            if (End[i]!=0)
                  end += 1<<i;
      }//把两个状态分别用一个ul型表示

      for (ul click = 0; click <= max; click++)
      {
            ul b = begin; //用来存储灯的”暗亮“情况，b的每一位表示一盏灯，初始值为0
            ul c = click;//用来存储灯的”是否操作“信息，c的每一位表示一盏灯，初始值为 click

            b ^= c & max;;  //影响自身
            b ^= (c << 1) & max; //影响左边的灯
            b ^= (c >> 1) & max; //影响右边的灯

            if (b == end & max)//如果b == end，表示有解
            {
                  ul sum = 0;
                  for (int i=n-1; i>=0; i--)
                  if ((c>>i) & 1)
                        sum++;
                  if (sum < min)
                        min = sum;
            }
      }
      if (min > n)
            min = -1;

      return min;
}

/*
问题六：问题三的扩展，由一行扩展到多行。
有m*n盏灯，排成m行n列( 1<= n <= 30).对一个灯进行操作，可以改变其本身和周围的灯的状态，
这里的周围指的是上下左右。根据灯的位置分布我们可以知道,角点影响3个灯，边4个，中间5个。
例如：操作坐标位置为(0, 0)的灯,则改变状态的灯有三盏,
它们分别是坐标位置为(0, 0),(0, 1)和(1, 0)的灯；而操作操作坐标位置为(0, 1)的灯,
则改变状态的灯有四盏,它们分别是坐标位置为(0, 0),(0, 1),(0, 2)和(1, 1)的灯；
而操作操作坐标位置为(2, 1)的灯,则改变状态的灯有五盏,它们分别是坐标位置为(2, 0),
(2, 1),(2, 2),(1, 1)和(3, 1)的灯。
已知初始时每盏灯都处于熄灭状态，请问如何操作可以使得所有的灯都被点亮。
返回所需的操作次数，如果没有解则如果没有解则返回-1，多个解则只输出一个即可。
(当然也可以求所需操作次数最少的一个，但当n较大时(超过10)运算量很大)
      函数接口: int Solve(int operation[][MAXCEL], int m, int n);  (MAXCEL = 30)
其中：operation[]存储每盏灯的”是否操作“信息，需要返回。0表示不对灯进行操作，1表示对灯进行操作。
m表示有m行，n表示有n列。
返回所需的操作次数。
      一些例子：
当m = n = 1时, 返回1， operation[1][1] = {1};
当m = 3，n = 2时, 返回4， operation[2][2] = {{0,0},
                                             {1,1},
                                             {1,1}};
当m = 5，n = 3时, 返回10， operation[3][3] = {{0,0,0},
                                             {1,1,1},
                                             {1,0,1},
                                             {1,0,1},
                                             {1,1,1}};
*/

#include <iostream>
#include <time.h>

using namespace std;

typedef unsigned long ul;
const int MAXROW = 20000;
const int MAXCEL = 20;

int Solve(int operation[][MAXCEL], int m, int n);
bool Solution(bool status[][MAXCEL], int operation[][MAXCEL], int maxRow, int maxCel, int x, int y);
int SolveOneRow(int operation[][MAXCEL], const int n);
int SolveOneCel(int operation[][MAXCEL], const int n);

int main()
{
      time_t startTime;
    time_t endTime;
    time(&startTime);

      const int m = 5;
      for (int i=0;i<4;i++){
      int n = i;
      int operation[m][MAXCEL] = {0};

      int s;
      s = Solve(operation, m, n);
      if (-1 != s)
      {         cout << "n =  " << n<<" s= ";
            cout << s << endl;
            for (int i=0; i<m; i++)
            {
                  for (int j=0; j<n; j++)
                        cout << operation[i][j] << ' ';
                  cout << endl;
            }
      } }

    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

int Solve(int operation[][MAXCEL], int m, int n)
{
      if (m < 1 || m > MAXROW || n < 1 || n > MAXCEL)
            return -1;
      else if (m == 1) //处理只有一行灯的情况
            return SolveOneRow(operation, n);
      else if (n == 1)  //处理只有一列灯的情况
            return SolveOneCel(operation, m);
      else
      {
            ul max = 1 << n;
            for (ul i=0; i<max; i++)
            {
                  bool status[MAXROW][MAXCEL] = {0};//存储当前方阵中每个灯“暗亮”信息
                  for (int j=0; j<n; j++)
                  {
                        operation[0][j] = 1 & (i>>j);
                        if (operation[0][j]) //对灯b[0][j]进行操作
                        {
                              status[0][j] = !status[0][j];
                              status[1][j] = !status[1][j];
                              if (j > 0)
                                    status[0][j-1] = !status[0][j-1];
                              if (j < n-1)
                                    status[0][j+1] = !status[0][j+1];
                        }
                  }
                  if (Solution(status, operation, m, n, 1, 0)) //如果有解输出一个解
                  {
                        int sum = 0;
                        for (int i=0; i<m; i++)
                              for (int j=0; j<n; j++)
                                    if (operation[i][j] == 1)
                                          sum++;
                        return sum;
                  }
            }
           return -1;
      }
}

/*
函数介绍：根据n的值判断是否存在使得方阵中所有的灯都亮的解
输入：const int a[][Max]：存储了当前方阵中每个灯被操作的次数
      int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
      int max：方阵的大小，即函数solve(int n)中的n值
      int x, int y：当前正在处理的灯的行号和列号
输出：int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
      返回true表示已经找到解，将结束处理，否则继续处理，直到穷举所有可能的情况。
*/
bool Solution(bool status[][MAXCEL], int operation[][MAXCEL], int maxRow, int maxCel, int x, int y)
{
      bool success = true; //用来判断是否已经找到解

      if (x == maxRow-1 && y == maxCel-1)//当处理到最后一盏灯时
      {
            operation[x][y] = 0;//首先尝试对灯b[x][y]不进行操作
            for (int i=0; i<maxRow; i++)//判断是否所有的灯都是亮的，即被操作了奇数次
            {
                  for (int j=0; j<maxCel; j++)
                        if (!status[i][j])//碰到有不亮的灯立即退出循环
                        {
                              success = false;
                              break;
                        }
                  if (!success)
                        break;
            }
            if (!success)//如果对灯b[x][y]不进行不能满足条件，则对灯b[x][y]进行操作
            {
                  operation[x][y] = 1; //对灯b[x][y]进行操作
                  status[x][y] = !status[x][y];
                  status[x-1][y] = !status[x-1][y];
                  status[x][y-1] = !status[x][y-1];
                  for (int i=0; i<maxRow; i++)
                  {
                        for (int j=0; j<maxCel; j++)
                              if (!status[i][j])//碰到有不亮的灯立即退出循环
                                    return false;
                  }
            }
            return true;
      }
      else //如果处理的不是第一行的灯，我们根据其上方的灯的状况决定是否操作该灯
      {
            if (status[x-1][y]&1)//如果其上方的灯是亮的，则不操作该灯
            {
                  operation[x][y] = 0;//对灯b[x][y]不进行操作
                  if (y < maxCel-1)
                        success = Solution(status, operation, maxRow, maxCel, x, y+1);
                  else
                        success = Solution(status, operation, maxRow, maxCel, x+1, 0);
            }
            else //否则操作该灯
            {
                  operation[x][y] = 1; //对灯b[x][y]进行操作
                  status[x][y] = !status[x][y];
                  status[x-1][y] = !status[x-1][y];
                  if (y > 0)
                        status[x][y-1] = !status[x][y-1];
                  if (x < maxRow-1)
                        status[x+1][y] = !status[x+1][y];
                  if (y < maxCel-1)
                        status[x][y+1] = !status[x][y+1];

                  if (y < maxCel-1)
                        success = Solution(status, operation, maxRow, maxCel, x, y+1);
                  else
                        success = Solution(status, operation, maxRow, maxCel, x+1, 0);
            }
            return success;
      }
}

//处理只有一行灯的情况
int SolveOneRow(int operation[][MAXCEL], const int n)
{
      if (n == 1) //如果只有 1 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            return 1;
      }
      if (n == 2) //如果只有 2 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            operation[0][1] = 0;
            return 1;
      }
      if (n % 3 == 0) //当n%3==0时，解是（n/3）个 0 1 0
      {
            for (int i=0; i<n; i+=3)
            {
                  operation[0][i] = 0;
                  operation[0][i+1] = 1;
                  operation[0][i+2] = 0;
            }
      }
      else if (n % 3 == 1)//当n%3==1时，解是（n/3）个 1 0 0 ，加上最后一个 1
      {
            for (int i=0; i<n-1; i+=3)
            {
                  operation[0][i] = 1;
                  operation[0][i+1] = 0;
                  operation[0][i+2] = 0;
            }
            operation[0][n-1] = 1;
      }
      else //当n%3==2时，解是（n/3）个 0 1 0，加上最后两个 0 1
      {
            for (int i=0; i<n-2; i+=3)
            {
                  operation[0][i] = 0;
                  operation[0][i+1] = 1;
                  operation[0][i+2] = 0;
            }
            operation[0][n-2] = 0;
            operation[0][n-1] = 1;
      }

      int sum = 0;
      for (int i=0; i<n; i++)
      {
            if (operation[0][i] == 1)
                  sum++;
      }
      return sum;
}

//处理只有一列灯的情况
int SolveOneCel(int operation[][MAXCEL], const int n)
{
      if (n == 1) //如果只有 1 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            return 1;
      }
      if (n == 2) //如果只有 2 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            operation[1][0] = 0;
            return 1;
      }
      if (n % 3 == 0) //当n%3==0时，解是（n/3）个 0 1 0
      {
            for (int i=0; i<n; i+=3)
            {
                  operation[i][0] = 0;
                  operation[i+1][0] = 1;
                  operation[i+2][0] = 0;
            }
      }
      else if (n % 3 == 1)//当n%3==1时，解是（n/3）个 1 0 0 ，加上最后一个 1
      {
            for (int i=0; i<n-1; i+=3)
            {
                  operation[i][0] = 1;
                  operation[i+1][0] = 0;
                  operation[i+2][0] = 0;
            }
            operation[n-1][0] = 1;
      }
      else //当n%3==2时，解是（n/3）个 0 1 0，加上最后两个 0 1
      {
            for (int i=0; i<n-2; i+=3)
            {
                  operation[i][0] = 0;
                  operation[i+1][0] = 1;
                  operation[i+2][0] = 0;
            }
            operation[n-2][0] = 0;
            operation[n-1][0] = 1;
      }

      int sum = 0;
      for (int i=0; i<n; i++)
      {
            if (operation[i][0] == 1)
                  sum++;
      }
      return sum;
}

/*
问题六：问题三的扩展，由一行扩展到多行。
有m*n盏灯，排成m行n列( 1<= n <= 30).对一个灯进行操作，可以改变其本身和周围的灯的状态，
这里的周围指的是上下左右。根据灯的位置分布我们可以知道,角点影响3个灯，边4个，中间5个。
例如：操作坐标位置为(0, 0)的灯,则改变状态的灯有三盏,
它们分别是坐标位置为(0, 0),(0, 1)和(1, 0)的灯；而操作操作坐标位置为(0, 1)的灯,
则改变状态的灯有四盏,它们分别是坐标位置为(0, 0),(0, 1),(0, 2)和(1, 1)的灯；
而操作操作坐标位置为(2, 1)的灯,则改变状态的灯有五盏,它们分别是坐标位置为(2, 0),
(2, 1),(2, 2),(1, 1)和(3, 1)的灯。
已知初始时每盏灯都处于熄灭状态，请问如何操作可以使得所有的灯都被点亮。
返回所需的操作次数，如果没有解则如果没有解则返回-1，多个解则只输出一个即可。
(当然也可以求所需操作次数最少的一个，但当n较大时(超过10)运算量很大)
      函数接口: int Solve(int operation[][MAXCEL], int m, int n);  (MAXCEL = 30)
其中：operation[]存储每盏灯的”是否操作“信息，需要返回。0表示不对灯进行操作，1表示对灯进行操作。
m表示有m行，n表示有n列。
返回所需的操作次数。
      一些例子：
当m = n = 1时, 返回1， operation[1][1] = {1};
当m = 3，n = 2时, 返回4， operation[2][2] = {{0,0},
                                             {1,1},
                                             {1,1}};
当m = 5，n = 3时, 返回10， operation[3][3] = {{0,0,0},
                                             {1,1,1},
                                             {1,0,1},
                                             {1,0,1},
                                             {1,1,1}};
*/

#include <iostream>
#include <time.h>

using namespace std;

typedef unsigned long ul;
const int MAXROW = 20000;
const int MAXCEL = 20;

int Solve(int operation[][MAXCEL], int m, int n);
int SolveOneRow(int operation[][MAXCEL], const int n);
int SolveOneCel(int operation[][MAXCEL], const int n);

int main()
{
      time_t startTime;
    time_t endTime;
    time(&startTime);

      const int m = 5;
      for (int i=0;i<6;i++){
      int n = i;
      int operation[m][MAXCEL] = {0};

      int s;
      s = Solve(operation, m, n);
      if (-1 != s)
      {         cout << "n =  " << n<<" s= ";
            cout << s << endl;
            for (int i=0; i<m; i++)
            {
                  for (int j=0; j<n; j++)
                        cout << operation[i][j] << ' ';
                  cout << endl;
            }
      } }

    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}


int Solve(int operation[][MAXCEL], int m, int n)
{
      if (m < 1 || m > MAXROW || n < 1 || n > MAXCEL)
            return -1;
      else if (m == 1) //处理只有一行灯的情况
            return SolveOneRow(operation, n);
      else if (n == 1)  //处理只有一列灯的情况
            return SolveOneCel(operation, m);
      else
      {
            //const ul max = (1<<n) - 1; //若这样写，n只能到31，不然位移32个bit，是未定义行为
            const ul max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数),也表示所有灯都亮的情况
            ul clicks[MAXROW];//存储灯的”是否操作“信息，每个元素表示一行，该元素的每一位表示一盏灯
            for (ul click = 0; click <= max; click++)
            {
                  ul a = 0; //临时变量，用来存储某行的灯最终的”暗亮“情况，
                  ul b = 0; //用来存储某行的灯的”暗亮“情况，初始值为0
                  ul c = click;//用来存储某行的灯的”是否操作“信息，第一行的初始值为 click
                  int i = 0;

                  do  //处理1--（n-1）行
                  {
                        clicks[i] = c;//读入第（i+1）行灯的”是否操作“信息
                        //根据第（i+1）行灯的”是否操作“信息确定该行的灯的”暗亮“情况
                        b ^= c;  //影响自身
                        b ^= (c << 1) & max; //影响左边的灯
                        b ^= (c >> 1) & max; //影响右边的灯
                        a = b; //用临时变量a存储该行的灯的”
                        b = c; //影响下边的灯，用b表示下一行的灯的”暗亮“情况
                        //根据该行的灯的”暗亮“情况，确定下一行灯的”是否操作“信息暗亮“情况
                        c = (a ^ max) & max;
                  } while(++i < m - 1);

                  clicks[i] = c; //读入最末行灯的”是否操作“信息
                  //确定最末行灯的”暗亮“情况
                  b ^= c;
                  b ^= (c << 1) & max;
                  b ^= (c >> 1) & max;

                  if (b == max)//如果最末行灯全亮，表示有解
                  {
                        int sum = 0;
                        for (i=0; i<m; i++)
                        {
                              for (int j=n-1; j>=0; j--)
                              {
                                    operation[i][n-j-1] = (clicks[i] >> j) & 1;
                                    if (operation[i][n-j-1] == 1)
                                          sum++;
                              }
                        }
                        return sum;
                  }
            }
            return -1;
      }
}

//处理只有一行灯的情况
int SolveOneRow(int operation[][MAXCEL], const int n)
{
      if (n == 1) //如果只有 1 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            return 1;
      }
      if (n == 2) //如果只有 2 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            operation[0][1] = 0;
            return 1;
      }
      if (n % 3 == 0) //当n%3==0时，解是（n/3）个 0 1 0
      {
            for (int i=0; i<n; i+=3)
            {
                  operation[0][i] = 0;
                  operation[0][i+1] = 1;
                  operation[0][i+2] = 0;
            }
      }
      else if (n % 3 == 1)//当n%3==1时，解是（n/3）个 1 0 0 ，加上最后一个 1
      {
            for (int i=0; i<n-1; i+=3)
            {
                  operation[0][i] = 1;
                  operation[0][i+1] = 0;
                  operation[0][i+2] = 0;
            }
            operation[0][n-1] = 1;
      }
      else //当n%3==2时，解是（n/3）个 0 1 0，加上最后两个 0 1
      {
            for (int i=0; i<n-2; i+=3)
            {
                  operation[0][i] = 0;
                  operation[0][i+1] = 1;
                  operation[0][i+2] = 0;
            }
            operation[0][n-2] = 0;
            operation[0][n-1] = 1;
      }

      int sum = 0;
      for (int i=0; i<n; i++)
      {
            if (operation[0][i] == 1)
                  sum++;
      }
      return sum;
}

//处理只有一列灯的情况
int SolveOneCel(int operation[][MAXCEL], const int n)
{
      if (n == 1) //如果只有 1 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            return 1;
      }
      if (n == 2) //如果只有 2 盏灯,直接返回结果
      {
            operation[0][0] = 1;
            operation[1][0] = 0;
            return 1;
      }
      if (n % 3 == 0) //当n%3==0时，解是（n/3）个 0 1 0
      {
            for (int i=0; i<n; i+=3)
            {
                  operation[i][0] = 0;
                  operation[i+1][0] = 1;
                  operation[i+2][0] = 0;
            }
      }
      else if (n % 3 == 1)//当n%3==1时，解是（n/3）个 1 0 0 ，加上最后一个 1
      {
            for (int i=0; i<n-1; i+=3)
            {
                  operation[i][0] = 1;
                  operation[i+1][0] = 0;
                  operation[i+2][0] = 0;
            }
            operation[n-1][0] = 1;
      }
      else //当n%3==2时，解是（n/3）个 0 1 0，加上最后两个 0 1
      {
            for (int i=0; i<n-2; i+=3)
            {
                  operation[i][0] = 0;
                  operation[i+1][0] = 1;
                  operation[i+2][0] = 0;
            }
            operation[n-2][0] = 0;
            operation[n-1][0] = 1;
      }

      int sum = 0;
      for (int i=0; i<n; i++)
      {
            if (operation[i][0] == 1)
                  sum++;
      }
      return sum;
}