B Crazy Binary String

题意

给一个01字符串，求0和1个数相同的最长子序列和子串长度。

分析

子序列长度就是\(min(cnt(0),cnt(1))*2\)，子串的长度也是原题，记录一下0和1个数差的前缀和，然后用一个数组记录前面扫过的0个数和1个数差值的最左位置，前缀和的思想更新答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n;
char s[N];
int cnt[2],mp[2*N];
int main(void){
//    freopen("in.txt","r",stdin);
    scanf("%d",&n);
    scanf("%s",s+1);
    int ans1=0,ans2=0;
    memset(mp,-1,sizeof(mp));
    mp[(int)1e5]=0;
    for(int i=1;i<=n;i++){
        cnt[0]+=s[i]=='0';
        cnt[1]+=s[i]=='1';
        if(mp[(int)1e5+cnt[0]-cnt[1]]==-1){
            mp[(int)1e5+cnt[0]-cnt[1]]=i;
        }
        ans1=max(ans1,i-mp[(int)1e5+cnt[0]-cnt[1]]);
    }
    ans2=min(cnt[0],cnt[1])*2;
    printf("%d %d\n",ans1,ans2);
    return 0;
}

F Planting Trees

题意

给一个矩阵，求出最大的子矩阵满足最大值和最小值之差不超过\(m\)。

分析

数据范围给的是\(n^3\)的做法，对于二维的一个子矩阵，需要\(n^2\)的时间来枚举上下底，然后使用单调队列维护横向的最大值与最小值之差。

关键一点在于枚举上下底\(i\)行和\(j\)行后，中间的二维矩阵的每一列其实就可以用这一列的最大值和最小值来表示，其他数值都已经无关紧要了，从而转化为一维数组的情况。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=505;
const int INF=0x3f3f3f3f;
int T,n,m,a[N][N];
int mx[N],mn[N];
int mxq[N],mnq[N];
int main(void){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        int ans=0;
        //枚举列
        for(int i=1;i<=n;i++){
            for(int j=0;j<=n;j++){
                mx[j]=0;
                mn[j]=INF;
            }
            for(int j=i;j<=n;j++){
                int l=1;
                int l1=1,r1=0;
                int l2=1,r2=0;
                //枚举右边界，维护最小可行左边界
                for(int r=1;r<=n;r++){
                    mx[r]=max(mx[r],a[r][j]);
                    mn[r]=min(mn[r],a[r][j]);
                    //维护两个单调队列mxq(最大值递减),mnq(最小值递增)
                    while(l1<=r1 && mx[r]>mx[mxq[r1]]){
                        r1--;
                    }
                    mxq[++r1]=r;
                    while(l2<=r2 && mn[r]<mn[mnq[r2]]){
                        r2--;
                    }
                    mnq[++r2]=r;
                    //维护两个单调队列使得max-min<=m
                    while(l<=r && l1<=r1 && l2<=r2 && mx[mxq[l1]]-mn[mnq[l2]]>m){
                        l++;
                        //删去无效元素
                        while(l1<=r1 && mxq[l1]<l){
                            l1++;
                        }
                        while(l2<=r2 && mnq[l2]<l){
                            l2++;
                        }
                    }
                    ans=max(ans,(j-i+1)*(r-l+1));
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

J LRU management

题意

模拟题，有\(n\)次操作，\(m\)个\(cache\)块，0操作是插入一个块，如果已存在，返回块的值，并将原来的块取出放到队尾，如果不存在，那就插入，并返回插入的值，如果插入后超过\(m\)个块，队头的块就要出去；1操作是询问某一块或者其上一个或者下一个是否存在，不影响队列结构。

分析

学到两个技巧

\(unordered_map<string,list<pair<string,int> >::iterator> mp\)在这道题中很好用，可以直接确定某个块在链表中的位置。
数字串可以转化为\(long long\)来表示以节省内存，考虑前导零，只需在前面多加一个1。

代码

#include <bits/stdc++.h>
using namespace std;
unordered_map<string,list<pair<string,int> >::iterator> mp;
list<pair<string,int> > ls;
int T,n,m,o,v;
char s[20];
int main(void){
    // freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        mp.clear();
        ls.clear();
        scanf("%d%d",&n,&m);
        while(n--){
            scanf("%d%s%d",&o,s,&v);
            if(o==1){
                auto it=mp.find(s);
                bool ac=true;
                int ans=0;
                if(it==mp.end()){
                    ac=false;
                }else{
                    //list<int>::iterator
                    auto kv=it->second;
                    if(v==-1){
                        if(kv==ls.begin()){
                            ac=false;
                        }else{
                            kv--;
                            ans=kv->second;
                        }
                    }else if(v==0){
                        ans=kv->second;
                    }else if(v==1){
                        kv++;
                        //end是最末元素指针＋１
                        if(kv==ls.end()){
                            ac=false;
                        }else{
                            ans=kv->second;
                        }
                    }
                }
                if(ac){
                    printf("%d\n",ans);
                }else{
                    printf("Invalid\n");
                }
            }else if(o==0){
                int ans=0;
                auto it=mp.find(s);
                if(it!=mp.end()){
                    ans=it->second->second;
                    ls.erase(it->second);
                    ls.push_back({s,ans});
                    auto t=ls.end();
                    t--;
                    it->second=t;
                }else{
                    ans=v;
                    ls.push_back({s,v});
                    auto t=ls.end();
                    t--;
                    mp[s]=t;
                    if(ls.size()>m){
                        mp.erase(ls.begin()->first);
                        ls.erase(ls.begin());
                    }
                }
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

2019牛客多校第三场

B Crazy Binary String

题意

分析

代码

F Planting Trees

题意

分析

代码

J LRU management

题意

分析

代码