2020/9/1 19:00拼多多笔试
//1.
给定一个n，输出n*n的矩阵，数字按照上面的划分，分界线上的为0
100%代码
using namespace std;
typedef long long ll;
int main() {
//ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
int n; cin >> n;
vector<vector<int> >s(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i > (n - 1) / 2) {
if (j > (n - 1) / 2) {
if (i > j) {
s[i][j] = 6;
}
if (j > i) {
s[i][j] = 7;
}
}
else if (j < n / 2) {
if (i + j < n - 1) {
s[i][j] = 4;
}
if (i + j > n - 1) {
s[i][j] = 5;
}
}
}
else if (i < n / 2) {
if (j > (n - 1) / 2) {
if (i + j < n - 1) {
s[i][j] = 1;
}
if (i + j > n - 1) {
s[i][j] = 8;
}
}
else if (j < n / 2) {
if (i > j) {
s[i][j] = 3;
}
if (j > i) {
s[i][j] = 2;
}
}
}
cout << s[i][j] << ' ';
}
cout << endl;
}
return 0;
}
//2.
给出一个 m * n 的矩阵，矩阵中的元素为0或1。如果矩阵中有若干个 1是相邻（上下左右是挨着）的，那么称这些1构成了一个“块”。现在可以将其中一个元素1移动到任意一个元素为0的位置，问移动之后，形成的块最大的面积。
50%代码
using namespace std;
typedef long long ll;
int n, m;
int num;
set<int>sum0;
void dfs(vector<vector<int>>& s, int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= m) return;
if (s[i][j] == 0) return;
s[i][j] = 0;
num++;
dfs(s, i - 1, j);
dfs(s, i, j - 1);
dfs(s, i + 1, j);
dfs(s, i, j + 1);
}
bool vis(const vector<vector<int>>& s, int i, int j) {
if (i - 1 >= 0) {
if (s[i - 1][j]) return false;
}
if (j - 1 >= 0) {
if (s[i][j - 1]) return false;
}
if (i + 1 < n) {
if (s[i + 1][j]) return false;
}
if (j + 1 < m) {
if (s[i][j + 1]) return false;
}
return true;
}
int main() {
//ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
cin >> n >> m;
vector<vector<int>>s(n, vector<int>(m));
queue<pair<int, int> >que;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> s[i][j];
if (s[i][j] == 0) {
que.push({ i,j });
}
}
}
int ans = 0;
while (que.size()) {
int a = que.front().first;
int b = que.front().second;
que.pop();
if (vis(s, a, b))continue;
auto t = s;
t[a][b] = 1;
set<int>sum1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
num = 0;
dfs(t, i, j);
if (num) sum1.emplace(num);
}
}
if (sum1.empty()) continue;
int number = *sum1.rbegin();
if (sum1.size() == 1) {
number--;
}
ans = max(ans, number);
}
cout << ans << endl;
return 0;
}
//3.
01背包，但是体积和重量都可能是负数
64%代码
using namespace std;
typedef long long ll;
int f[210][5010];
int v[210];
int w[210];
int main() {
//ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
int m, n; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
//4.
集合1~~N中能被集合B中任意一个元素整除的数量
100%代码
using namespace std;
typedef long long ll;
int gcd(int x, int y) {
if (x > y) swap(x, y);
while (1) {
int a = x;
int b = y % x;
if (b == 0) return x;
x = min(a, b);
y = max(a, b);
}
}
int main() {
//ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
int m, n; cin >> n >> m;
vector<int>s;
for (int i = 0; i < m; i++) {
int t; cin >> t;
s.emplace_back(t);
for (int j = 0; j < s.size() - 1; j++) {
if (t % s[j] == 0) {
s.pop_back();
break;
}
}
}
int len = 1;
for (auto x : s) {
len = x * len / gcd(x, len);
}
int num = 0;
vector<int>vis(len + 10, 0);
for (auto x : s) {
for (int i = x; i <= len; i+=x) {
if (vis[i] == 0) {
vis[i] = 1;
num++;
}
}
}
int ans = n / len * num;
int t = n / len * len+1;
for (int i =t; i <= n; i++) {
for (auto x : s) {
if (i % x == 0) {
ans++;
break;
}
}
}
cout << ans << endl;
return 0;
}
#笔试题目##拼多多#