首页 > 拼多多9.1笔试1,1,0.6,1
头像
法外狂徒张三丰
编辑于 2020-09-01 21:13
+ 关注

拼多多9.1笔试1,1,0.6,1

T1
把一个矩阵分成按对角线分成八份,如
5
0 2 0 1 0
3 0 0 0 8
0 0 0 0 0
4 0 0 0 7
0 5 0 6 0
8
0 2 2 2 1 1 1 0
3 0 2 2 1 1 0 8
3 3 0 2 1 0 8 8
3 3 3 0 0 8 8 8
4 4 4 0 0 7 7 7
4 4 0 5 6 0 7 7
4 0 5 5 6 6 0 7
0 5 5 5 6 6 6 0
#include <iostream>
#include <queue>
using namespace std;
int ju[201][201], temp;
struct pos{
	int x, y;
};
bool ifLegal(int x, int y) {
	return x >= 0 && x < temp && y >= 0 && y < temp;
}
int d[2][4]={{-1,0,1,0},{0,1,0,-1}};
void da(int x, int y,int c) {
	pos t;
	t.x = x;
	t.y = y;
	queue<pos>que;
	que.push(t);
	while(!que.empty()) {
		pos k = que.front();
		que.pop();
		if (!ifLegal(k.x, k.y))
		continue;
		if (ju[k.x][k.y] != 0)
		continue;
		ju[k.x][k.y] = c;
		for (int i = 0; i < 4; i ++) {
			pos temp;
			temp.x = k.x + d[0][i];
			temp.y = k.y + d[1][i];
			que.push(temp);
		}
	};
}
int main() {
	int n;
	cin >> n;
	temp = n;
	if (temp%2 == 0) {
		++ temp;
	}
	for (int i = 0; i < temp; i ++) {
		ju[i][i] = -1;
		ju[i][temp - i - 1] = -1;
		ju[temp/2][i] = -1;
		ju[i][temp/2] = -1;
	}
	da(0, temp - 2, 1); 
	da(0, 1, 2);
	da(1,0,3);
	da(temp - 2, 0, 4);
	da(temp - 1, 1, 5);
	da(temp - 1, temp - 2, 6);
	da(temp - 2, temp - 1, 7);
	da(1, temp - 1, 8);
	for (int i = 0; i < temp; i ++) {
		for (int j = 0; j < temp; j ++) {
			if (temp != n && (i == temp/2 || j == temp / 2)){
				continue;
			}
			if (ju[i][j] == -1)
			cout << 0;
			else
			cout << ju[i][j];
			cout << " ";
		}
		if (temp != n && i == temp/2)
		continue;
		cout << endl;
	}
}
T2
有一个n*n的棋盘 对应位是1代表是士兵 否则不是 一个士兵和他的上下左右四个位置的士兵可直接连接 连接在一起的士兵构成一个兵团 问移动一个士兵 得到的最大兵团的士兵个数
首先bfs出来全部的兵团,之后枚举每个位置添加士兵,算出添加士兵后的最大军团数量,之后取这个值和全部士兵的最小值输出,因为如果全部士兵不构成一个兵团 我们必能拿出一个其他兵团的兵添加到该位置 反之 拿兵团外围一个兵也可添加到该位置
    #include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
bool shibing[400][400];
int shibingS[400][400];
struct pos{
	int x, y;

};
int d[2][4]={{-1,0,1,0},{0,1,0,-1}};
int num[400 * 400];
bool numcc[400*400];
int n, m;
bool ifLegal(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m;
}
int da(int x, int y,int c) {
	pos t;
	int ans = 0;
	t.x = x;
	t.y = y;
	queue<pos>que;
	que.push(t);
	while(!que.empty()) {
		pos k = que.front();
		que.pop();
		if (!ifLegal(k.x, k.y))
		continue;
		if (shibing[k.x][k.y] == 0 || shibingS[k.x][k.y] == c)
		continue;
		shibingS[k.x][k.y] = c;
		ans++;
		for (int i = 0; i < 4; i ++) {
			pos temp;
			temp.x = k.x + d[0][i];
			temp.y = k.y + d[1][i];
			que.push(temp);
		}
	};
	//cout << ans << endl;
	return ans;
}
int main() {
	int cnt = 0, alll = 0;
	memset(shibingS, -1, sizeof(shibingS));
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j ++) {
			cin >> shibing[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < m; j ++) {
			if (shibingS[i][j] == -1 && shibing[i][j]) {
				++ cnt;
				num[cnt] = da(i, j, cnt);
				ans = max(ans, num[cnt]);
				alll += num[cnt];
			}
		}
	}
	queue<int>que;
//	for (int i = 0; i < n; i ++) {
//		for (int j = 0; j < m; j ++) {
//			cout << shibingS[i][j] << " ";
//		}
//		cout << endl;
//	}
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < m; j ++) {
			if (shibing[i][j])
			continue;
			int temp = 0;
			for (int k = 0; k < 4; k ++) {
				int x = i + d[0][k];
				int y = j + d[1][k];
				if (!ifLegal(x, y))
				continue;
				if (shibingS[x][y] != -1 && !numcc[shibingS[x][y]]) {
					numcc[shibingS[x][y]] = 1;
					temp += num[shibingS[x][y]];
					que.push(shibingS[x][y]);
				}
			}
			temp += 1;
			ans = max(ans, temp);
			while (!que.empty()) {
				int k = que.front();
				que.pop();
				numcc[k] = 0;
			}
		}
	}
	cout << min(ans, alll) << endl;
} 
T3
0,1背包问题 有负cost和负value 写丑了 不放代码了
T4
容斥原理 给定一个集合s求出[1,n]能被集合中任意元素整除的元素的数量
#include <iostream>
using namespace std;
long long gcd(long long m, long long n) {
	return n == 0 ? m : gcd(n, m%n);
}
long long k[11];
long long ans = 0;
long long allll;
int allnum;
void sele(int pos,int te,int all,long long lcm) {
	if (pos == all) {
		int temp = 1;
		for (int i = 1; i < all; i++) {
			temp*=-1;
		}
		ans += temp * (allll/lcm);
		return;
	}
	for (int t = te; t < allnum; t ++) {
		long long tec = k[t];
		if (pos != 0) {
			long long gc = gcd(lcm, tec);
			tec /= gc;
			tec *= lcm;
		}
		sele(pos + 1, t + 1, all, tec);
	}
	
}
int main() {
	cin >> allll >> allnum;
	for (int i = 0; i < allnum; i ++) 
	cin >> k[i];
	for (int i = 1; i <= allnum; i ++) 
	sele(0,0,i,0);
	cout << ans;
}
感觉这次笔试题不是很难,但脑子确实有点转不动



全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐