难度：绿+。
题意
给定 \(t\) 组 testcase，每组 testcase 如下。
有 \(m\) 个长度为 3 的字符串，每个字符都是 \(\text{w}\)、\(\text{i}\)、\(\text{n}\) 中的一个，一共有 \(m\) 个 \(\text{w}\)，\(m\) 个 \(\text{i}\) 和 \(m\) 个 \(\text{n}\)。
现在要求用最少次数的交换使得每个字符串都变成 \(\text{w}\)、\(\text{i}\)、\(\text{n}\) 各有一个，并输出方案。
题解
题目本身不难，但是很有趣，感觉分数有点打低了，不过听说 CF 普遍把思维打得比较低。
最让人头疼的问题是要交换次数最小，怎么样才能保证最小？或者说什么样的取法是最优方案？
观察到有 wwn 和 iin 这种只要交换一次就能让两个都结束，肯定优先交换这种的。
将 \(\text{w}\) 设为 0，\(\text{i}\) 设为 1，\(\text{n}\) 设为 2，则所有字符串都可以用 012 来表示。例如 wwn 是 002，iin 是 112 等。
分析什么样的可以一下就两个都消掉，发现是一个 \(x\) 多 \(y\) 少，另一个 \(y\) 多 \(x\) 少的情况。例如 002 就是 0 多 1 少，112 就是 1 多 0 少，所以这两个可以直接消掉。
特殊地，000 这种三个都是一样的就既算 0 多 1 少，也算 0 多 2 少，容易证明这样也是对的。
除了能直接消掉的就是三个一组的消了。为了书写方便，记 \(x\) 多 \(y\) 少的字符串用二元组 \((x,y)\) 表示。则三个一组只有两种情况：\((0,1),(1,2),(2,0)\) 和 \((1,0),(0,2),(2,1)\)。
实现
这道题的实现每个人写出来都不一样，我觉得我写得比较简单。
把 \((x,y)\) 的字符串存到一个 vector<int> vec[3][3] 中的 vec[x][y] 里。
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rept(i,n) for(int i=1;i<=n;i++)
#define repe(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define fi first
#define se second
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define sz(v) (int)(v.size())
using namespace std;
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template<typename T>void chmax(T& a,T b){if(a<b)a=b;return;}
template<typename T>void chmin(T& a,T b){if(a>b)a=b;return;}
const int N=1e5+10;
const char ch[3]={'w','i','n'};
int n;
string s[N];
vector<int> vec[3][3];
struct answer{
int a[2],c[2];
};
vector<answer> ans;
answer mans(int a,int b,int c,int d){
answer res;
res.a[0]=a;
res.c[0]=b;
res.a[1]=c;
res.c[1]=d;
return res;
}
int get(char c){
if(c=='w')return 0;
if(c=='i')return 1;
return 2;
}
void solve(){
cin>>n;
rep(i,3)rep(j,3)vec[i][j].clear();
rept(i,n){
cin>>s[i];
int x=get(s[i][0]),y=get(s[i][1]),z=get(s[i][2]);
if(x!=y&&y!=z&&x!=z)continue;
if(x==y&&x==z){
if(x!=0)vec[x][0].pb(i);
if(x!=1)vec[x][1].pb(i);
if(x!=2)vec[x][2].pb(i);
}
else{
int u;
if(x==y||x==z)u=x;
else u=y;
int v=3-x-y-z+u;
vec[u][v].pb(i);
}
}
ans.clear();
rep(i,3){
rep(j,3){
if(i<j){
while(!vec[i][j].empty()&&!vec[j][i].empty()){
int x=vec[i][j].back(),y=vec[j][i].back();
vec[i][j].pop_back();
vec[j][i].pop_back();
ans.pb(mans(x,i,y,j));
}
}
}
}
while(!vec[0][1].empty()&&!vec[1][2].empty()&&!vec[2][0].empty()){
int x=vec[0][1].back(),y=vec[1][2].back(),z=vec[2][0].back();
vec[0][1].pop_back();
vec[1][2].pop_back();
vec[2][0].pop_back();
ans.pb(mans(x,0,y,1));
ans.pb(mans(y,0,z,2));
}
while(!vec[1][0].empty()&&!vec[0][2].empty()&&!vec[2][1].empty()){
int x=vec[1][0].back(),y=vec[0][2].back(),z=vec[2][1].back();
vec[1][0].pop_back();
vec[0][2].pop_back();
vec[2][1].pop_back();
ans.pb(mans(x,1,y,0));
ans.pb(mans(y,1,z,2));
}
cout<<sz(ans)<<"\n";
rep(i,sz(ans)){
cout<<ans[i].a[0]<<" "<<ch[ans[i].c[0]]<<" "<<ans[i].a[1]<<" "<<ch[ans[i].c[1]]<<"\n";
}
}
signed main(){
int t;
cin>>t;
while(t--)solve();
return 0;
}
//Jerry_Jiang