讨论/题目交流/🏆 第 187 场力扣周赛/
🏆 第 187 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 旅行终点站
4 分 - 是否所有 1 都至少相隔 k 个元素
5 分 - 绝对差不超过限制的最长连续子数组
7 分 - 有序矩阵中的第 k 个最小数组和

第三题
枚举子数组的右端点 二分+rmq计算出最远的左端点即可

class Solution {
public:
    static const int maxn=1e5+10;
    int a[maxn];
    int dpmax[maxn][20],dpmin[maxn][20];
void rmq_init (int n) {
    for (int i = 0; i < n; i++) dpmax[i][0] =dpmin[i][0]= a[i];
    for (int j = 1; (1<<j) <= n; j++) {
        for (int i = 0; i+(1<<j)-1 < n; i++) {
            dpmax[i][j] = max (dpmax[i][j-1], dpmax[i+(1<<(j-1))][j-1]);
            dpmin[i][j] = min (dpmin[i][j-1], dpmin[i+(1<<(j-1))][j-1]);
        }
    }
}
    long long sum[maxn];
void init(int n){
    sum[0]=0;
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i-1];
}
int rmqmax (int l, int r) {
    int k = 0;
    while ((1<<(k+1)) <= r-l+1) k++;
    return max (dpmax[l][k], dpmax[r-(1<<k)+1][k]);
}
int rmqmin (int l, int r) {
    int k = 0;
    while ((1<<(k+1)) <= r-l+1) k++;
    return min (dpmin[l][k], dpmin[r-(1<<k)+1][k]);
}
    int longestSubarray(vector<int>& nums, int limit) {
        for (int i=0;i<nums.size();i++) a[i]=nums[i];
        rmq_init(nums.size());
        init(nums.size());
        long long Max = 0;
        int n=nums.size();
        for (int i=0;i<n;i++){
            int l=0,r=i;
            while (l<r){
                //cout<<l<<" "<<r<<endl;
                int mid = (l+r)>>1;
                //cout<<"mid="<<mid<<endl;
                //cout<<"rmq="<<rmqmax(mid,i)<<" "<<rmqmin(mid,i)<<endl;
                if (rmqmax(mid,i)-rmqmin(mid,i)<=limit){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
           // cout<<"l="<<l<<" r="<<r<<endl;
            l=min(l,r);
           // cout<<"i="<<i<<"l="<<l<<endl;
            Max = max(Max,1LL*i-l+1);
        }
        return Max;
    }
};

第四题
注意到每个矩阵元素不超过5000,则答案不超过200000,且答案具有单调性
因此二分答案,check则是直接dp dp(i,j)表示用了前i行,和为j的方案数

class Solution {
public:
    int n,m;
    int a[50][50];
    int sum[50];
    long long dp[40+2][200000+10];
    int check(int mid,int k){
        for (int i=0;i<=n;i++){
            for (int j=1;j<=mid;j++) dp[i][j]=0;
        }
        dp[0][0]=1;
        for (int i=1;i<=n;i++){
            for (int mask=0;mask<=mid;mask++){
                if (dp[i-1][mask]==0) continue;
                for(int j=1;j<=m;j++){
                    if (mask+a[i][j]>mid) continue;
                    dp[i][mask+a[i][j]]=(dp[i][mask+a[i][j]]+dp[i-1][mask]);
                    if (dp[i][mask+a[i][j]]>k) dp[i][mask+a[i][j]]=k;
                    if (dp[i][mask+a[i][j]]==k){
                        if (sum[n]-sum[i]+mask+a[i][j]<=mid) return true;
                    }
                }
            }
        }
        long long res=0;
        for (int i=1;i<=mid;i++){
            res+=dp[n][i];
            if (res>=k) return true;
        }
        return false;
    }
    int kthSmallest(vector<vector<int>>& mat, int k) {
        n=mat.size();
        m=mat[0].size();
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                a[i+1][j+1] =mat[i][j]; 
            }
        }
        sum[0]=0;
        for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][1];
        int r;
        for (int i=1;i<=n;i++) r+=a[i][m];
        int l=sum[n];
        while (l<r){
            int mid=(l+r)>>1;
            if (check(mid,k)){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        for(int i=min(l,r);i<=max(l,r);i++){
            if (check(i,k)) return i;
        }
        return 0;
    }
};
1
展开全部 18 讨论