网易笔试解析

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10];
char b[10];
int main()
{
	int t;
	cin >> t ;
	while(t --){
		int n;
		cin >> n;
		for(int i = 1; i <= n; i ++)	cin >> a[i];
		for(int i = 1; i <= n; i ++)	cin >> b[i];
		sort(a + 1, a + n + 1);
		sort(b + 1, b + n + 1);
		pair<int,int>	cnt0[10];
		for(int i = 0; i < 10; i ++)	cnt0[i] = {0, 0};
		int ct0 = 0, ct1 = 0;
		for(int i = 1; i <= n; i ++){
			if(ct0 && cnt0[ct0].first == a[i]){
				cnt0[ct0].second ++;
			} else{
				cnt0[++ct0] = {a[i], 1};
			}
		}
		pair<char,int>	cnt1[10];
		for(int i = 0; i < 10; i ++)	cnt1[i] = {0, 0};
		for(int i = 1; i <= n; i ++){
			if(ct1 && cnt1[ct1].first == b[i]){
				cnt1[ct1].second ++;
			} else{
				cnt1[++ct1] = {b[i], 1};
			}
		}

		if(n == 1)	puts("1");
		else if(n == 2){
			if(ct0 == 1)	puts("2");
			else	puts("1");
		} else if(n == 3){
			if(ct0 == 1)	puts("6");
			else if(ct0 == 2)	puts("2");
			else	puts("1");
		} else if(n == 4){
			if(ct0 == 1)	puts("150");
			else if(ct0 == 2 && (cnt0[1].second == 1 || cnt0[1].second == 3))	puts("6");
			else if(ct0 == 2 && cnt0[1].second == 2)	puts("4");
			else if(ct0 == 3)	puts("2");
			else	puts("1");
		} else if(n == 5){
			if(ct0 == 1)	puts("15000");
			else if(ct1 == 1 && ct0 == 5 && cnt0[1].first + 4 == cnt0[5].first)	puts("8000");
			else if(ct1 == 1)	puts("300");
			else if(ct0 == 2 && (cnt0[1].second == 1 || cnt0[1].second == 4))	puts("150");
			else if(ct0 == 2 && (cnt0[1].second == 2 || cnt0[1].second == 3))	puts("40");
			else if(ct0 == 5 && cnt0[1].first + 4 == cnt0[5].first)	puts("20");
			else if(ct0 == 3 && (cnt0[1].second == 3 || cnt0[2].second == 3 || cnt0[3].second == 3))puts("6");
			else if(ct0 == 3 && (cnt0[1].second == 1 || cnt0[2].second == 1 || cnt0[3].second == 1))puts("4");
			else if(ct0 == 4)	puts("2");
			else	puts("1");
		}
	}
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 800;
int a[N][N];
int p[N * N + N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool st[N][N];
int n, m;
bool ttmp(pair<int,int> a, pair<int,int> b)
{
	return a.first > b.first;
}
int find(int x)
{
	if(p[x] == x)	return x;
	return p[x] = find(p[x]);
}
void dfs(int x, int y)
{
	int tt = m * (x - 1) + y;
	for(int i = 0; i < 4; i ++){
		int nx = x + dx[i], ny = y + dy[i];
		int tmp = m * (nx - 1) + ny;
		if(st[nx][ny] && find(tt) != find(tmp)){
			p[find(tt)] = find(tmp);
		}
	}
}
int main()
{
	cin >> n >> m;
	int myx, myy;
	cin >> myx >> myy;
	int posx, posy;
	cin >> posx >> posy;
	memset(st, false, sizeof st);
	int mx = -1;
	vector<pair<int,int>> res;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			scanf("%d", &a[i][j]);
			mx = max(mx, a[i][j]);
			res.push_back({a[i][j], m * (i - 1) + j});
		}
	}
	sort(res.begin(), res.end(), ttmp);
	for(int i = 1; i <= N * N; i ++){
		p[i] = i;
	}
	for(int k = 0; k <= mx + 1; k ++){
		vector<pair<int,int>> v;
		int tmp = res.size();
		for(int i = tmp - 1; i >= 0; i --){
			int x = res[i].first, y = res[i].second;
			if(x <= k){
				int ii = y / m + 1, jj = y % m;
				if(jj == 0)	jj = m;
				st[ii][jj] = 1;
				v.push_back({ii, jj});
				res.pop_back();
			}else	break;
		}
		for(int i = 0; i < v.size(); i ++){
			int x = v[i].first, y = v[i].second;
			dfs(x, y);
		}
		if(find(m * (myx - 1) + myy) == find(m * (posx - 1) + posy)){
			cout << k << endl;
			return 0;
		}
	}
	return 0;
}