360笔试9.9
第一题为输出每个宝藏能在第几天打开
#include<bits/stdc++.h>
using namespace std;
int main () {
int n;
cin>>n;
vector<int>arr(n, 0);
int begin = -1;
unordered_map<int, bool>mp; // 已经拥有的钥匙
bool flag = false;
for (int i = 0; i < n; ++i) {
cin>>arr[i];
if (arr[i] == 1) {
begin = i + 1;
flag = true;
}
if (!flag) {
mp[arr[i]] = true;
}
}
vector<int>res(n + 1, -1);
res[1] = begin;
int nextDoor = 2;
for (int i = begin; i < n; ++i) {
while(mp[nextDoor]) {
res[nextDoor] = begin;
nextDoor++;
}
begin++;
mp[arr[i]] = true;
}
while(mp[nextDoor]) {
res[nextDoor] = begin;
nextDoor++;
}
for (int i = 1; i <= n; ++i) {
cout<<res[i]<<" ";
}
return 0;
} 第二题为求出正方形区域最大的和
//
// Created by Lenovo on 2022/9/9.
//
// 动态规划！！！
#include<bits/stdc++.h>
using namespace std;
int main () {
int t;
cin>>t;
while (t--) {
int n, m;
cin>>n>>m;
vector<vector<int>> arr(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin>>arr[i][j];
}
}
vector<vector<int>> dp(n, vector<int>(m, 0));
int res = 0;
// 先记住边长，然后在计算数字之和！！！ 时间复杂度也是一样的！！
// 不为-1就可以组成正方形！！
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i == 0 || j == 0) {
dp[i][j] = arr[i][j] == -1 ? 0 : 1;
} else {
if (arr[i][j] == -1) {
dp[i][j] = 0;
} else {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (dp[i][j] == 0) {
continue;
}
int row = i - dp[i][j] + 1;
int col = j - dp[i][j] + 1;
int tmpres = 0;
for (int q = row; q <= i; q++) {
for (int w = col; w <= j; w++) {
tmpres += arr[q][w];
}
}
res = max(res, tmpres);
}
}
cout<<res<<endl;
}
} 两题都是middle
#360笔试#
