构造题种类繁多，套路多种多样，这里介绍几种经典套路
抽屉原理
使用于要求操作数限制小于等于 \(\left \lfloor \frac{n}{k} \right \rfloor\) 的题，如果可以构造出恰好 \(k\) 种方案，所有方案操作数总和为 \(n\)，那么其中最少的方案是满足条件的
CF1450C2 Errich-Tac-Toe (Hard Version)
将格子三色染色，即根据 \((i+j)\%p\) 的值分成三类
那么每一个连续三个颜色相同的格子一定一类占一个，那么只要保证其中两类分别是两种符号，一定可以破坏所有的三连格。
那么每一类有 \(X\) 改 \(O\) 和 \(O\) 改 \(X\) 两种方法
可以发现总共六种方法加起来总共是 \(k\) 次操作
那么把这些操作两两组合，形成三种方案，一定有一个是满足条件的
代码实现
#include<bits/stdc++.h>
using namespace std;
int t,n,cnt[5],cnt1[5];
char c[305][305];
struct Sum{
int val,id;
}sum[5];
bool cmp(Sum a,Sum b){
return a.val<b.val;
}
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%s",c[i]+1);
}
memset(cnt,0,sizeof cnt);
memset(cnt1,0,sizeof cnt1);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int id=(i+j)%3+1;
if(c[i][j]=='X')cnt[id]++;
if(c[i][j]=='O')cnt1[id]++;
}
}
sum[1].val=cnt[1]+cnt1[2];
sum[2].val=cnt[2]+cnt1[3];
sum[3].val=cnt[3]+cnt1[1];
for(int i=1;i<=3;i++)sum[i].id=i;
sort(sum+1,sum+4,cmp);
// cout<<sum[1].val<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int id=(i+j)%3+1;
if(id==sum[1].id&&c[i][j]=='X')cout<<'O';
else if(id==sum[1].id%3+1&&c[i][j]=='O')cout<<'X';
else cout<<c[i][j];
}
cout<<endl;
}
}
return 0;
}