2019.2.18总结

又是水题大赛和失误的一天

T1边界出错，二分打错

T4初始值赋错

没什么好讲的

T1上升子序列

T2spfa

T3单调队列

T4背包dp

题意

T1原序列将卡片拿出再放回几次才能有序？

T2走迷宫，有些地块需要更多体力问最少体力消耗

T3给定序列，求该点前m个数中的最小值

T4给定f,s值选取任意个物品使总和最大且f值和与s值和都不小于0

A

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
int q[500009],lenq;
int n; 
int find(int l,int r,int k)
{
    int mid,re=0;
    while(l<=r)
    {
        //cout<<l<<" "<<r<<" "<<re<<" 233"<<endl;
        int mid=(l+r)>>1;
        if(q[mid]<=k) re=mid,l=mid+1;
        else r=mid-1;
    }
    return re;
}
int main ()
{
    //freopen("card.in","r",stdin);
    //freopen("card.out","w",stdout);
    n=read();
    for(int i=1,x;i<=n;i++)
    {
        q[0]=-2000000000;
        x=read();
        if(x>=q[lenq]) q[++lenq]=x;
        else
        {
            q[find(0,lenq,x)+1]=x;
        }
    }
    printf("%d",n-lenq);
    return 0;   
}

B

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
struct gzw
{
    int x,y;
};
int T,n,m;
int mp[509][509];
bool mark[509][509];
int dis[509][509];
int stx,sty,edx,edy;
int ans=-1;
int tot[509][509];
queue<gzw> q;
inline int true_calc(int x,int y)
{
    return abs(edx-x)+abs(edy-y);   
}
int main ()
{
    T=read();
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        mark[0][i]=1;
        mark[i][0]=1;
        mark[i][m+1]=1;
        mark[n+1][i]=1;
        for(int j=1;j<=m;j++)
        {
            dis[i][j]=2000000000;
            mp[i][j]=read();
            if(mp[i][j]==5) stx=i,sty=j;
            else if(mp[i][j]==9) edx=i,edy=j;
        }
    }
    q.push((gzw){stx,sty});
    mark[stx][sty]=1;
    dis[stx][sty]=0;
    while(!q.empty())
    {
        gzw now=q.front();
        q.pop();
        int x=now.x,y=now.y;
        if(dis[x][y]+(mp[x+1][y]==1?5:1)<dis[x+1][y]) {dis[x+1][y]=dis[x][y]+(mp[x+1][y]==1?5:1);if(!mark[x+1][y])q.push((gzw){x+1,y}),mark[x+1][y]=1;}
        if(dis[x][y]+(mp[x-1][y]==1?5:1)<dis[x-1][y]) {dis[x-1][y]=dis[x][y]+(mp[x-1][y]==1?5:1);if(!mark[x-1][y])q.push((gzw){x-1,y}),mark[x-1][y]=1;}
        if(dis[x][y]+(mp[x][y+1]==1?5:1)<dis[x][y+1]) {dis[x][y+1]=dis[x][y]+(mp[x][y+1]==1?5:1);if(!mark[x][y+1])q.push((gzw){x,y+1}),mark[x][y+1]=1;}
        if(dis[x][y]+(mp[x][y-1]==1?5:1)<dis[x][y-1]) {dis[x][y-1]=dis[x][y]+(mp[x][y-1]==1?5:1);if(!mark[x][y-1])q.push((gzw){x,y-1}),mark[x][y-1]=1;}
        mark[x][y]=0;
    }
    printf("%d",(T-dis[edx][edy])>0?(T-dis[edx][edy]):-1);
    return 0;   
}

C

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
struct gzw
{
    int val,pos;    
}q[1000009];
int head=1,tail;
int n,m;
int main ()
{
    //freopen("min.in","r",stdin);
    //freopen("min.out","w",stdout);
    n=read(),m=read();
    for(int i=1,x;i<=n;i++)
    {
        while(head<=tail&&q[head].pos+m<i) head++;
        x=read();
        while(head<=tail&&x<q[tail].val) tail--;
        q[++tail]=(gzw){x,i};
        printf("%d ",q[head]);
    }
    return 0;   
}

D

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
int f[109][200009]; 
int n;
int ans=0;
int s[109],ff[109]; 
int main ()
{
    //freopen("smrtfun.in","r",stdin);
    //freopen("smrtfun.out","w",stdout);
    for(int i=0;i<=100;i++)
    {
        for(int j=0;j<=200000;j++)
        {
            f[i][j]=-200000000;
        }
    }
    n=read();
    for(int i=1;i<=n;i++)
    {
        s[i]=read(),ff[i]=read();   
    }
    f[0][100000]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=200000;j>=0;j--)
        {
            if(f[i-1][j]!=f[0][0])
            {
                if(f[i-1][j]+ff[i]>f[i][j+s[i]]) {f[i][j+s[i]]=f[i-1][j]+ff[i];if(j+s[i]>=100000&&f[i][j+s[i]]>=0) ans=max(ans,j+s[i]-100000+f[i][j+s[i]]);}
                f[i][j]=max(f[i][j],f[i-1][j]);
            }
        }
    }
    printf("%d ",ans);
    return 0;   
}