【GiantPandaCV導語】本次周賽做得還算順利，主要考察了模擬，二分，單調(diào)棧，拓撲排序以及樹形DP等知識點，這里記錄一下題解。

A. 人口最多的年份

解題思路：數(shù)據(jù)范圍比較小，可以直接模擬，從年份開始循環(huán)，然后再循環(huán)logs數(shù)組，如果年份在出生和死亡年份之間就記錄。

AC代碼：

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        int mx = 0, ans = 0;
        for(int i=1950; i<=2050; i++){
            int t = 0;
            for(int j=0; j<logs.size(); j++){
                if(logs[j][0]<=i&&i<logs[j][1]){
                    t++;
                }
            }
            if(t > mx){
                mx = t;
                ans = i;
            }
        }
        return ans;
    }
};

B. 下標對中的最大距離

解題思路：看一下數(shù)據(jù)量1e5，并且數(shù)組是有序的，那么枚舉一個下標，二分另外一個下標就可以了。不過更好的做法是雙指針，我更擅長寫二分，這里只接寫的二分法的代碼。

AC代碼：

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        for(int i=0; i<nums1.size(); i++){
            int l = i, r = nums2.size()-1;
            int now = -1;
            while(l <= r){
                int mid=(l+r)>>1;
                if(nums2[mid]>=nums1[i]){
                    l=mid+1;
                    now=mid;
                }
                else{
                    r=mid-1;
                }
            }
            if(now!=-1){
                ans = max(ans, now-i);
            }
        }
        return ans;
    }
};

C. 子數(shù)組最小乘積的最大值

解題思路：以當前為中心，往左往右找不小于最遠處和，這樣最大，最大。需要注意結(jié)果要取模。

AC代碼:

class Solution {
public:
    long long sum[100010];
    int mod=1e9+7;
    int maxSumMinProduct(vector<int>& nums) {
        long long maxx = 0;
        int n = nums.size();
        for(int i=1; i<=n; i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        stack <int> s;
        for(int i=0; i<=n; i++){
            int now = i == n ? -1 : nums[i];
            while(!s.empty() && now < nums[s.top()]){
                int id = s.top();
                s.pop();
                int num = nums[id];
                if(s.empty()){
                    maxx = max(maxx, sum[i] * num);
                }
                else{
                    maxx = max(maxx, (sum[i] - sum[s.top()+1]) * num);
                }
            }
            s.push(i);
        }
        maxx %= mod;
        return (int)maxx;
    }
};

D. 有向圖中最大顏色值

解題思路：顯然，當這個有向圖有回路的話結(jié)果無限大，輸出-1。我們可以通過拓撲排序的方法判斷有向圖是否有環(huán)，若這個有向圖不具有拓撲次序，那么就說明有環(huán)。然后就是對結(jié)果的求解，我們依次枚舉每一個字母，求出這個字母在所有路中的某一條中出現(xiàn)次數(shù)的最大值。根據(jù)前面求出的拓撲次序DP一下即可，dp[i]表示以i點為起點的路徑中，當前字母c的最大出現(xiàn)次數(shù)，那么轉(zhuǎn)移就是，其中j是i的兒子節(jié)點。

#define mst(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
const int maxn = 300005;
const ll mod = 1e9+7;
const ll INF = 1e9;
const double eps = 1e-9;

int n,m;
int degree[maxn];
char s[maxn];
int dp[maxn];
vector<int>vec[maxn];
vector<int>mp;

bool check()
{
    mp.clear();
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(degree[i]==0) q.push(i);
    }
    while(q.size())
    {
        int u=q.front();
        q.pop();
        mp.push_back(u);
        for(int i=0;i<vec[u].size();i++)
        {
            degree[vec[u][i]]--;
            if(degree[vec[u][i]]==0) q.push(vec[u][i]);
        }
    }
    return mp.size()==n;
}

int solve(int x)
{
    mst(dp,0);
    char c=x+'a';
    int cnt=0;
    for(int i=mp.size()-1;i>=0;i--)
    {
        int u=mp[i];
        for(int j=0;j<vec[u].size();j++)
        {
            dp[u]=max(dp[u],dp[vec[u][j]]);
        }
        if(s[u-1]==c) dp[u]++;
        cnt=max(cnt,dp[u]);
    }
    return cnt;
}

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        for(int i=0; i<colors.size(); i++) s[i] =colors[i];
        n = colors.size();
        for(int i=1;i<=n;i++) vec[i].clear();
        m = edges.size();
        mst(degree,0);
        for(int i=0; i<m; i++){
            edges[i][0]++;
            edges[i][1]++;
            vec[edges[i][0]].push_back(edges[i][1]);
            degree[edges[i][1]]++;
        }
        if(!check()) return -1;
        int ans = 0;
        for(int i=0;i<26;i++)
        {
            ans=max(ans,solve(i));
        }
        return ans;
    }
};

總的來說，是一次比較好的周賽體驗QAQ。

歡迎關(guān)注GiantPandaCV, 在這里你將看到獨家的深度學習分享，堅持原創(chuàng)，每天分享我們學習到的新鮮知識。( ? ?ω?? )?

有對文章相關(guān)的問題，或者想要加入交流群，歡迎添加BBuf微信：