什么是构造

构造题是一种题型。

不同于其它的算法、数据结垢题，根据查询输出结果；构造题是让你给出一组方案，使得在一定限制内符合条件。

从形式上来看，问题的答案往往具有某种规律性，使得在问题规模迅速增大的时候，仍然有机会比较容易地得到答案。

这要求解题时要思考问题规模增长对答案的影响，这种影响是否可以推广。例如，在设计动态规划方法的时候，要考虑从一个状态到后继状态的转移会造成什么影响。

构造题一个很显著的特点就是高自由度，也就是说一道题的构造方式可能有很多种，但是会有一种较为简单的构造方式满足题意。看起来是放宽了要求，让题目变的简单了，但很多时候，正是这种高自由度导致题目没有明确思路而无从下手。

构造题另一个特点就是形式灵活，变化多样。并不存在一个通用解法或套路可以解决所有构造题，甚至很难找出解题思路的共性。

构造题的解法

构造题的经典算法有二分、分治、排序、图论算法如网络流，2-SAT，最短路等等。也会用到一些数学公式推导求出构造方法。

考虑问题时，我们往往从小情况入手，再构造大的情况。

有时我们也会考虑特殊情况，自己添加条件限制范围。

题解（21.8.29）

CF1438D Powerful Ksenia

题目描述

给 $\le 10^5)$ 个正整数 $a_i$ , $\le a_i\le10^9$ .

每次操作是选三个不同的下标 $i, j, k$ ，让 $a_i,a_j,a_k$ 都变成 $a_i \oplus a_j\oplus a_k$ ，也就是这三个数的异或和.

让你判断是否能在 $n$ 次操作内，使这 $n$ 个正整数的值变成相同的.

若能，第一行输出YES，第二行输出 $m$ 表示操作数量，接下来 $m$ 行每行三个整数，描述一次操作；

若不能，输出NO.

题解

Step 1
首先考虑 $n = 3$ 的情况，此时一次操作就能完成。

Step 2
在考虑 $n = 4$ 的情况，一次操作之后就变成了 $[a, a, a, b]$ 的情况，再进行一次变成 $[a, b, b, b]$ ，如果 $\ne b$ ，那么无解。

Step 3
在考虑 $n = 5$ 的情况，则 $[a,b,c,d,e]\rightarrow[a,a,a,d,e]\rightarrow[a,a,d,d,d]\rightarrow[d,d,d,d,d]$

此时似乎已经有了头绪。

当 $n$ 为奇数时，我们只需要将序列变为 $[a, a, b, b, c, c . . . d, d, d]$ 的形式，然后连续用前面的一对数异或序列最后的数即可。

通过计算或找规律可得到操作次数最多为 $n ? 2$ 次。

Step 4
那么当 $n$ 为偶数时呢？

我们进行Step 3操作，发现最后会形成 $[a, a, b, b, c, c . . . d, d, d, e]$ 这种情况。当 $d = e$ 时，可以像上一步一样将序列全部异或成一个数，操作次数为 $n ? 3$ 次（省去了异或最后一个数的次数）；而当 $\ne e$ 时无解。

为了解释无解，我们要理清一个性质，那就是操作前后序列异或和不变。

那么显然如果这个偶数个数的序列有解，其异或和必然为0。也就是中间操作不会改变异或和。

所以 $\ne e$ 时无解。

$AC\ Code$

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
inline ll read()
{
	ll s = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar();}
	return s * w;
}
ll n, a[100005];
int main()
{
	n = read();
	for(re ll i = 1; i <= n; i++)
		a[i] = read();
	if(n % 2 == 0)
	{
		for(re ll i = 3; i <= n - 1; i += 2)
			a[i] = a[i - 1] = a[i - 2] = a[i] ^ a[i - 1] ^ a[i - 2];
		if(a[n] != a[n - 1])
		{
			printf("NO");
			return 0;
		}
		else
		{
			printf("YES\n%lld\n", n - 3);
			for(re ll i = 3; i <= n - 1; i += 2)
				printf("%lld %lld %lld\n", i, i - 1, i - 2);
			for(re ll i = 3; i <= n - 3; i += 2)
				printf("%lld %lld %lld\n", n, i - 1, i - 2);
		}
	}
	else
	{
		printf("YES\n%lld\n", n - 2);
		for(re ll i = 3; i <= n; i += 2)
			printf("%lld %lld %lld\n", i, i - 1, i - 2);
		for(re ll i = 3; i <= n - 2; i += 2)
			printf("%lld %lld %lld\n", n, i - 1, i - 2);
	}
	
	return 0;
}