20190310模拟赛题解

Posted by

T1 包裹快递

思路:二分最大速度即可。check​ 函数中判定是否每次都能按时到达下一个签收点。依照题意,同时更新时间。由于数据构造原因,此题需要开long​ double​才可通过。

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
static const double esp=1e-3;
static const int MAXN=200050;
using namespace std;
struct node{
    double l,r,s;
}a[MAXN];
int n;
inline bool check(double V){
    long double T=0.0;
    for(int i=1;i<=n;i++){
        T+=a[i].s/V;
        if(T>a[i].r) return false;
        if(T<a[i].l) T=a[i].l;
    }
    return true;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf %lf %lf",&a[i].l,&a[i].r,&a[i].s);
    double l=0,r=2147483647;
    while(r-l>=esp){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.2lf\n",r);
    return 0;
}

T2 迎接仪式

思路:考虑dp​。设状态转移方程dp[i]​ [j]​ [l]​,表示目前处理了前i​个字符,交换了j​'j'​,交换了l​'l'​的最大答案。然后根据不同情况去转移即可。最终答案即为max​ (f[n][i][i])​,其中i​ \in​ [0,k]​

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=550;
static const int MAXK=150;
using namespace std;
int n,k,len,ans,f[MAXN][MAXK][MAXK];
char s[550];
inline int read(){
    int x=0;
    bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();k=read();
    scanf("%s",s+1);
    len=strlen(s+1);
    memset(f,-0x3f,sizeof(f));
    f[0][0][0]=f[1][0][0]=f[1][s[1]=='j'][s[1]=='z']=0;
    for(int i=1;i<=len;i++){
        for(int j=0;j<=k;j++){
            for(int l=0;l<=k;l++){
                f[i][j][l]=f[i-1][j][l];
                if(s[i-1]=='j'&&s[i]=='z')
                    f[i][j][l]=max(f[i][j][l],f[i-2][j][l]+1);
                else if(s[i-1]=='j'&&s[i]=='j'&&j)
                    f[i][j][l]=max(f[i][j][l],f[i-2][j-1][l]+1);
                else if(s[i-1]=='z'&&s[i]=='z'&&l)
                    f[i][j][l]=max(f[i][j][l],f[i-2][j][l-1]+1);
                else if(s[i-1]=='z'&&s[i]=='j'&&j&&l)
                    f[i][j][l]=max(f[i][j][l],f[i-2][j-1][l-1]+1);
            }
        }
    }
    for(int i=0;i<=k;i++) ans=max(ans,f[n][i][i]);
    printf("%d\n",ans);
    return 0;
}

T3 与众不同

思路:

s[i]表示以数字a[i]为结尾的最长完美序列的起始位置,则s[i]=max(s[i-1],last[a[i]]+1),其中last[a[i]]表示数字a[i]出现的最后位置。

记录数组d[i]表示以第i个数为结尾的最长完美序列长度,则d[i]=i-s[i]+1

根据s[i]的递推式,可以发现其单增性。对于lr之间的s[i],可能会出现s[i]<ls[i] \in [l,r]这两种情况,这个点x可以通过二分来找到。

然后对于[l,r]内的最大值,分为左边和右边两部分来求。其中左边的最大值就是x-l,右边的最大值就是求[x,r]之间的最大值。查询可使用ST表或线段树求解。

特别的,由于数据里存在负值,则需要将值加上MAXN来作为下标。

同时数据的区间端点是从0开始算的,在下面的程序中我是以1为起点开始存的,即读入时需+1

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int lim=20;
static const int MAXN=200050;
int n,m,x,ql,qr,l,r,s[MAXN],d[MAXN],Log[MAXN],last[3000000],f[MAXN][lim+5];
inline int read(){
    int x=0;
    bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline void make_st(){
    for(int i=1;i<=n;i++) f[i][0]=d[i];
    for(int j=1;j<=lim;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=std::max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
inline int query(int l,int r){
    int k=Log[r-l+1];
    return std::max(f[l][k],f[r-(1<<k)+1][k]);
}
inline bool check(int x){
    return s[x]<ql;
}
int main(){
    n=read();m=read();
    Log[0]=-1;
    for(int i=1;i<=n;i++){
        x=read();
        s[i]=std::max(s[i-1],last[x+MAXN]+1);
        d[i]=i-s[i]+1;
        Log[i]=Log[i>>1]+1;
        last[x+MAXN]=i;
    }
    make_st();
    while(m--){
        ql=read()+1;qr=read()+1;
        l=ql,r=qr;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) l=mid+1;
            else r=mid-1;
        }
        if(l<=qr) printf("%d\n",std::max(l-ql,query(l,qr)));
        else printf("%d\n",l-ql);
    }
    return 0;
}

 

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注