比赛地址：传送门
赛时过了 3 题，继续加油哈~

A 签到题
J 规律题
K 思维题

A Alive Fossils

思路
模拟题意即可

代码

void solve(){
	int n, c;
	string ss;
	map<string, int> q;
	cin >> n;
	for(int i = 0; i < n; ++ i){
		cin >> c;
		for(int j = 0; j < c; ++ j){
			cin >> ss;
			++ q[ss];
		}
	}
	vector<string> ans;
	for(auto [x, y] : q){
		if(y == n){
			ans.push_back(x);
		}
	}
	cout << ans.size() << '\n';
	for(auto x : ans){
		cout << x << '\n';
	}
	return ;
}

J Permutation and Primes

题意
让你构造一个 1 ~ n 的排列，满足对于所有的 $1\le i < n $，均有 $p_i + p_{i + 1} $ 是一个奇质数，或者 $|p_i - p_{i + 1}| $ 是一个奇质数

思路
奇质数：3, 5, 7, 11, 13, 17, 19, $\dots $
打表可以猜测，这样的构造一定是存在的，而且情况很多，我们只需要选择一种合适的方式即可

仔细认真刻苦慢慢观察就能发现，如果我们利用差值+3 +3 -5，就可以构造一个长为 9 的满足题意的局部序列，包含数字 \([i, i + 8]\)，之后再利用末尾的 i + 8 作为新的起点，就又能往后扩展 8 位。所以，我们可以以 8 位为一个循环节，每个循环节为 \(i, i + 3, i + 6, i + 1, i + 4, i + 7, i + 2, i + 5\)，不够8位的利用开头的 \(1 ~ i % 8\) 来补足即可

代码

int a[8][10]={
	{0},
	{1},
	{1, 2},
	{1, 2, 3},
	{1, 4, 3, 2},
	{1, 4, 3, 2, 5},
	{1, 2, 5, 6, 3, 4},
	{1, 2, 3, 4, 7, 6, 5}
};
int b[8] = {0, 3, 6, 1, 4, 7, 2, 5};

void solve(){// + 3 + 3 - 5
	int n;
	cin >> n;
	int t = n % 8;
	if(t){
		for(int i = 0; i < t; ++ i){
			cout << a[t][i] << ' ';
		}
	}
	for(int i = t + 1; i <= n; i += 8){
		for(int j = 0; j < 8; ++ j){
			cout << i + b[j] << ' ';
		}
	}
	cout << '\n';
	return ;
}

K Scheming Furry

题意
给你一个 n 行 m 列的矩阵，每个位置上的数字两两不相同且均 $\in [1, n \times m] $。选手 fox 和选手 cat 轮流进行操作使得在自己操作后该矩阵变得有序，选手 fox 先进行操作。这里定义矩阵有序为矩阵的元素逐行逐列非递减。两位选手所能做的操作是固定的，选手 fox 仅可以选择交换矩阵的两行，选手 cat 仅可以选择交换矩阵的两列。每位选手每轮必须操作，不能重复操作，即一轮只能操作一次。如果说某位选手发现自己无论怎么操作都不能先让矩阵变得有序，那么它将会想尽办法阻止自己的对手先把矩阵变的有序，即使这会使得矩阵永远无序。两位选手都足够聪明。
聪明的你早就看穿了一切，请你求出谁会先将矩阵变得有序，如果永远无序，输出 "NSFW"

思路
题面很简单，思路其实也很简单
我们先对矩阵本身进行考虑，如果说一个给定的矩阵想通过两位选手的操作变的有序，那么这个矩阵必须得是由最终矩阵经过若干次操作之后得到的，也就是说，给定矩阵的每一行的数，都是范围 $[k \times m + 1, k \times m + m] (k \ge 0) $ 内的数的一个排列，且每一行的排列方式都应当相同。
在这样判断之后，我们就得到了一个有机会通过操作变得有序的矩阵，不然无论选手怎么操作，先天限制不可能。

我们接下来考虑先手 fox 怎样才能赢？如果说先手交换两行后，矩阵刚好就有序了，那么这种情况先手一步就赢了。
如果说先手一步不能实现矩阵有序，那么后手在没有必胜策略的情况下就会进行破坏，这种情况下除非后手的操作是有迹可循的，不然就会陷入平局的局面。那么什么时候后手的操作有迹可循呢？就是当只有两列的时候，此时后手的操作被固定了，如果说此时在后手的循环操作中，先手也可以实现矩阵的有序，那么先手 fox 就赢了。这种情况的判断可以利用行位置的逆序对和列位置的逆序对的奇偶性来进行判断，因为最终的矩阵行位置的逆序对和列位置的逆序对均为 0，所以可以通过逆序对的奇偶性来判断能否在循环操作中实现矩阵有序。这里注意一点，先手操作比后手多一步，所以此时奇偶性应当是不相同，而下面的情况应当是相同

那么对于后手来说也是同样，当矩阵只有两行的时候，除非在先手的循环操作中，后手可以实现矩阵的有序，后手 cat 可赢，不然就只剩平局了。

代码

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 2e2 + 5, inf = 0x3f3f3f3f, mod = 998244353;
int n, m, a[maxm][maxm];

struct BIT{
	int num;
	vector<ll> c;
	BIT(int x = maxm) : num(x), c(x + 1, 0){}
	int lowbit(int x){ return x & (-x); }

	void update(int x, int v){
		while(x <= num){
			c[x] += v; x += lowbit(x);
		}
		return ;
	}

	ll getsum(int x){
		ll res = 0;
		while(x){
			res += c[x]; x -= lowbit(x);
		}
		return res;
	}
};

void solve(){
	cin >> n >> m;
	bool f = true;//判断矩阵的行列是否为有序矩阵操作而来的
	int cntc = 0, cntr = 0;//统计行列有序的个数
	vector<int> c(m + 1, -1);
	BIT bitr(n);
	int rcha = 0;
	for(int i = 1; i <= n; ++ i){
		int tx = -1, ty = -1, x, y = 0;
		for(int j = 1; j <= m; ++ j){
			cin >> a[i][j];
			x = (a[i][j] - 1) / m;
			if(i > 1) y = abs(a[i - 1][j] - a[i][j]);
			if(f){
				//判行
				if(tx != -1 && x != tx) f = false;
				else tx = x;
				//判列差
				if(y % m) f = false;
				else if(ty != -1 && ty != y / m) f = false;
				else ty = y / m;
			}
		}
		if(f && x == i - 1) ++ cntr;//有序行
		if(f){
			++ x;
			rcha += i - 1 - bitr.getsum(x);
			bitr.update(x, 1);
		}
	}
	if(!f){//矩阵乱序，无法实现
		cout << "NSFW\n"; return ;
	}
	BIT bitc(m);
	int ccha = 0;
	for(int i = 1; i <= m; ++ i){
		if((a[1][i] - 1) % m + 1 == i) ++ cntc;//有序列
		ccha += i - 1 - bitc.getsum((a[1][i] - 1) % m + 1);
		bitc.update((a[1][i] - 1) % m + 1, 1);
	}
	if(cntr + 2 == n && cntc == m){//fox一步赢
		cout << "FOX\n"; return ;
	}
	if(m == 2 && rcha % 2 != ccha % 2){//fox有限步赢，后手操作以2为周期
		cout << "FOX\n"; return ;
	}
	if(n == 2 && ccha % 2 == rcha % 2){//cat有限步赢
		cout << "CAT\n"; return ;
	}
	cout << "NSFW\n";
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}