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
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) 回帖