奇数码问题

title: 奇数码问题
date: 2024-01-05 11:52:04
tags: 逆序对
cstefories: 算法进阶指南

题目大意

解题思路

将二维转化为一维，求他的逆序对，如果逆序对的奇偶性相同，则能够实现。

代码实现

#include<iostream>
#include<string.h>
#include<cstring>
#include<unordered_map>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#define int long long

#define bpt __builtin_popcountll

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 2E6 + 10, mod = 998244353;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

const int MOD = 998244353;

priority_queue<int, vector<int>>l;//大根堆
priority_queue<int, vector<int>, greater<int>> r;//小根堆

int a[N], b[N],c[N];
int cnt = 0;
int n;

void merge(int l,int r,int *a)
{
	if (l >= r) return;

	int mid = l + r >> 1;
	merge(l, mid, a);
	merge(mid + 1, r, a);

	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++) {
		if (i <= mid && a[i] <= a[j] || j > r) {
			b[k] = a[i++];
		}
		else {
			cnt += mid - i + 1;
			b[k] = a[j++];
		}
	}

	for (int k = l; k <= r; k++) {
		a[k] = b[k];
	}
}
signed main()
{
	int n;
	while (cin >> n) {
		int ok = 0;
		for (int i = 1; i <= n * n; i++) {
			int x; cin >> x;
			if (x == 0) ok = 1;
			else a[i - ok] = x;
		}
		ok = 0;
		for (int i = 1; i <= n * n; i++) {
			int x; cin >> x;
			if (x == 0) ok = 1;
			else c[i - ok] = x;
		}

		cnt = 0;
		merge(1, n * n, a);
		int ans = cnt;
		cnt = 0;
		merge(1, n * n, c);
		if ((ans & 1) == (cnt & 1)) puts("TAK");
		else puts("NIE");
	}
}