米哈游笔试题目思路（客户端卷）

考场一小时就速通交卷了，发个考场AC代码。肯定还能优化，轻喷。代码一题比一题短。。。

1.矩阵连通块

思路两次dfs，一次是正常的，一次是按照B和G等价来看。

#include<iostream>

using namespace std;

int n, m;
string s[1010];
bool vis1[1010][1010], vis2[1010][1010];
const int mv[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int dfs1(int x, int y) {
	if(x < 0 || x >= n) return 0;
	if(y < 0 || y >= m) return 0;
	if(vis1[x][y]) return 0;
	if(!vis1[x][y]) vis1[x][y] = true;
	for(int i = 0; i < 4; i++) {
		if(x + mv[i][0] < 0 || x + mv[i][0] >= n) continue;
		if(y + mv[i][1] < 0 || y + mv[i][1] >= m) continue;
		if(s[x + mv[i][0]][y + mv[i][1]] == s[x][y])
			dfs1(x + mv[i][0], y + mv[i][1]);
	}
	return 1;
}
int dfs2(int x, int y) {
	if(x < 0 || x >= n) return 0;
	if(y < 0 || y >= m) return 0;
	if(vis2[x][y]) return 0;
	if(!vis2[x][y]) vis2[x][y] = true;
	for(int i = 0; i < 4; i++) {
		if(x + mv[i][0] < 0 || x + mv[i][0] >= n) continue;
		if(y + mv[i][1] < 0 || y + mv[i][1] >= m) continue;
		if(s[x][y] == 'G' || s[x][y] == 'B') {
			if(s[x + mv[i][0]][y + mv[i][1]] == 'G' || s[x + mv[i][0]][y + mv[i][1]] == 'B')
				dfs2(x + mv[i][0], y + mv[i][1]);
		}
		else if(s[x + mv[i][0]][y + mv[i][1]] == s[x][y])
			dfs2(x + mv[i][0], y + mv[i][1]);
	}
	return 1;
}
int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> s[i];
	}
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cnt += dfs1(i, j);
		}
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cnt -= dfs2(i, j);
		}
	}
	
	cout << cnt;
	return 0;
}

2.mhy字符串

手动玩一下可以发现mhy这三个字的顺序没有任何关系。

例如：yhm->mhyhmy->mhyhmy->hym

然后hym通过类似的操作就可以变成mhy，因此这个插入删除就等价于无序插入删除而且可以随意调整已有的顺序。

然后只需要比较mhy之外的字符串是否相等，已经mhy三个字符之间的数量关系。

#include <bits/stdc++.h>

using namespace std;

int bin_s[3], bin_t[3];

int main() {
	int T;
	cin >> T; 
	while(T--) {
		bin_s[0] = bin_s[1] = bin_s[2] = 0;
		bin_t[0] = bin_t[1] = bin_t[2] = 0;
		string s, t;
		cin >> s >> t;
		string new_s, new_t;
		for(int i = 0; i < (int) s.length(); i++) {
			if(s[i] == 'm') bin_s[0]++;
			else if(s[i] == 'h') bin_s[1]++;
			else if(s[i] == 'y') bin_s[2]++;
			else new_s.push_back(s[i]);
		}
		for(int i = 0; i < (int) t.length(); i++) {
			if(t[i] == 'm') bin_t[0]++;
			else if(t[i] == 'h') bin_t[1]++;
			else if(t[i] == 'y') bin_t[2]++;
			else new_t.push_back(t[i]);
		}
		if(new_s == new_t) {
			if(bin_s[0] - bin_t[0] == bin_s[1] - bin_t[1] 
			&& bin_s[0] - bin_t[0] == bin_s[2] - bin_t[2])
				cout << "Yes" << endl;
			else cout << "No" << endl;
		}
		else cout << "No" << endl;
	}
	return 0;
}

3.子集合计数

简单O(nsqrt(a))的dp，排序之后dp[i]代表以a[i]结尾的数的集合数量。那么dp[i]只需要从所有a[i]的因数处转移，因为集合不可重复，所以可以排序之后令pos[a[i]] = i，没有的就-1，所以sqrt(a[i])枚举一下因数，用pos桶查坐标，都加上就行。

#include <bits/stdc++.h>

using namespace std;

const long long M = 1000000007;
int a[100010], pos[1000010];
int dp[100010];

int main() {
	memset(pos, -1, sizeof(pos));
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for(int i = 0; i < n; i++) {
		pos[a[i]] = i;
	}
	long long ans = 0;
	for(int i = 0; i < n; i++) {
		int tmp = a[i];
		for(int j = 1; j * j <= tmp; j++) {
			if(tmp % j == 0) {
				if(pos[tmp / j] > -1 && j != tmp / j) {
					dp[i] += dp[pos[tmp / j]];
				}
				if(pos[j] > -1) {
					dp[i] += dp[pos[j]];
				}
			}
		}
		ans += dp[i];
		ans %= M;
		dp[i]++;
	}
	cout << ans;
	return 0;
}