问题描述

又到了大家最喜欢的数学考试时间！

小蓝老师给了你 nn 个方程组成的线性方程组，格式如下：

x1+x2=a1x1​+x2​=a1​

x1+x2+x3=a2x1​+x2​+x3​=a2​

x2+x3+x4=a3x2​+x3​+x4​=a3​

………………

xn−3+xn−2+xn−1=an−2xn−3​+xn−2​+xn−1​=an−2​

xn−2+xn−1+xn=an−1xn−2​+xn−1​+xn​=an−1​

xn−1+xn=anxn−1​+xn​=an​

小蓝老师还会提供给你 a1,a2,a3,⋯ ,an(1≤i≤n)a1​,a2​,a3​,⋯,an​(1≤i≤n) 的值，并且规定 xixi​ 由 00 和 11​ 构成。

你需要求解给定的线性方程组，由于答案可能不唯一，你需要输出字典序最小的解。
输入格式

第一行输入包含一个正整数 n(2≤n≤2×105)n(2≤n≤2×105)，表示线性方程组的数量。。

第二行输入 nn 个正整数 a1,a2,a3,⋯ ,ana1​,a2​,a3​,⋯,an​ 表示数组 a(0≤ai≤3)a(0≤ai​≤3) 的值。

数据保证该线性方程组至少存在一组解，且一定是合法数据。
输出格式

输出 nn 个整数，为字典序最小的线性方程组的解，第 ii 个整数表示 xixi​。

正解

一.将题给的方程组转换一下（甚至可以不要最后一行），因为a[i]都是已知的，所以可以看出只要知道x[1]就可以递推出x2,x3,x4…xn
二.再根据题意x[i]只能为0或者1，故本题只有两种情况
1. x[1]=0
2.x[1]=1
三.且要以最小字典序输出，故要先看x[1]=0的情况，再看x[1]=1的情况

#include <iostream>
using namespace std;
const int N = 2e5+10;
int n;
int a[N];
int x[N];
int main()
{
  cin>>n;
  for(int i = 1;i<=n;i++)cin>>a[i];

  x[1] = 0;
  bool flag = false;
  for(int i = 2;i<=n;i++)
  {
    x[i] = a[i-1] - x[i-2] - x[i-1];
    if(x[i] != 0 && x[i] != 1)
    {
      flag = true;
      break;
    }
  }

  if(flag)
  {
    x[1] = 1;
    for(int i = 2;i<=n;i++) x[i] = a[i-1] - x[i-2] - x[i-1];
  }
  for(int i = 1;i<=n;i++)cout<<x[i]<<" ";
  return 0;
}