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