米哈游客户端笔试 算法题

1 色盲

BFS扫两轮一遍过

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
using namespace std;

int fx[4] = {0,1,0,-1};
int fy[4] = {1,0,-1,0};

vector<vector<int> > vec;
vector<vector<int> > vec_f;
vector<vector<bool> > vis;
vector<vector<bool> > vis_f;
int m,n;
int cnt_1 = 0;  // true
int cnt_2 = 0;  // semang
bool judge(int x,int y){
    if(x<0 || x >= m) return false;
    if(y<0 || y >= n) return false;
    return true;
}
// 根据特定的vec矩阵 以及特定的访问矩阵进行标记
// mark是标记的一个固定的值 如果遇到相等的就 修改vis数组的内容
void mark(int x,int y,const int &marked,
        const vector<vector<int>>& vec,
        vector<vector<bool>>& vis){
    if(judge(x,y) == false || vis[x][y] == true || 
        marked != vec[x][y]) return;
    else{
        vis[x][y] = true;
        for(int i = 0 ; i< 4;++i){
            int nx,ny;
            nx = fx[i] + x;
            ny = fy[i] + y;
            // if(judge(nx,ny) == true &&
            //         vis[nx][ny] == false &&
            //         vec[nx][ny] == mark){
                // vis[nx][ny] = true;
            mark(nx,ny,marked,vec,vis);
            // }
        }
    }
}
// 
void bfs(const vector<vector<int>>& vec,
        vector<vector<bool>>& vis,
        int& cnt)
{
    int m,n;
    m = vec.size();
    n = vec[0].size();
    for (size_t i = 0; i < m; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            if(vis[i][j] == false){
                mark(i,j,vec[i][j],vec,vis);
                ++cnt;
            }
        }
        
    }
}
int main(){
    cin >>m >> n;
    vec.resize(m);
    vec_f.resize(m);
    vis.resize(m);
    vis_f.resize(m);
    for(int i = 0; i < m ; ++i){
        vec[i].resize(n);
        vec_f[i].resize(n);
        vis[i].resize(n,false);
        vis_f[i].resize(n,false);
    }
    for(int i = 0 ; i < m ; ++i){
        string str;
        cin >> str;
        for(int j = 0; j < n ; ++j)
        {
            // cin >> vec[i][j];
            vec[i][j] = str[j];
            if(vec[i][j] != 'R')
                vec_f[i][j] = 'X';
            else
                vec_f[i][j] = vec[i][j];
        }
    }
    bfs(vec,vis,cnt_1);
    bfs(vec_f,vis_f,cnt_2);
    // cout << cnt_1 << endl;
    // cout << cnt_2 << endl;
    cout <<  cnt_1-cnt_2 << endl;
    // bfs_f();
    return 0;
}

2 字符串处理

比较简单

#include <iostream>
using namespace std;
bool fun(string& s,string& t){
	int nums[26] = {0};
	int numt[26] = {0};

	for(int i = 0 ; i < t.size() ; ++i){
		numt[t[i] - 'a']++;
	}
	for(int i = 0 ; i < s.size() ; ++i){
		nums[s[i] - 'a']++;
	}

	int m ,h,y;
	m = 0;
	h = 0;
	y = 0;
	for(int i = 0 ; i < 26 ; ++i){
		if(i == 7)
		 	h = nums[i] - numt[i];
		else if(i == 12)
			m = nums[i] - numt[i];
		else if(i == 24)
			y = nums[i] - numt[i];
		else if(nums[i] - numt[i] != 0) 
			return false;
	}
	return (m == h) && (h==y);
}
int main(){
	int n ;
	cin >> n;

	string s,t;
	while(n--){
		cin >> s >> t;
		bool res = fun(s,t);
		if(res == 1)
			cout << "Yes" << endl;
		else 
			cout << "No" << endl;
		// cout << res << endl;
	}
	return 0;
}

3. 子集

DP 春春不会 BFS暴力过20%，还是太菜了。

#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
ll res = 0;
const int mod = 1e9+7;
// 判断倍数问题
bool isVaild(vector<int>& temp, int x){
	for(auto num : temp){
		if(x%num) return false;
	}
	return true;
}
// 回溯法
void back(vector<int>& nums, int begin , vector<int>& temp){
	if(begin >= nums.size()) return ;

	for(int i = begin; i < nums.size() ; ++i){
		if(isVaild(temp,nums[i]) == true){
			res++;
			temp.push_back(nums[i]);
			back(nums,i+1,temp);
			temp.pop_back();
		}
	}
}
void getSetNum(vector<int> & nums){
	for(int i = 0 ; i < nums.size() ; ++i){
		vector<int> temp;
		temp.push_back(nums[i]);
		back(nums,i+1,temp);
	}
}
int main(){
    int n;
	cin >> n;

	vector<int> a(n);
	for(int i = 0 ; i < n ; ++i)
		cin >> a[i];
	
	sort(a.begin(),a.end());
	getSetNum(a);

	cout << res%mod << endl;
	return 0;	
}

总结

寄