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

把一个矩阵分成按对角线分成八份，如

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;
	}
}

有一个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;
}

0，1背包问题有负cost和负value 写丑了不放代码了

容斥原理给定一个集合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;
}

感觉这次笔试题不是很难，但脑子确实有点转不动

#笔试题目##拼多多#