首页 > 代码库 > 济南-1029试题解题报告

济南-1029试题解题报告

济南-1029试题解题报告

By shenben

本解题报告解析均为100分解题思路。

上午

T1

题意:给你两个日期,问这两个日期差了多少毫秒

解析:标程用ctime库函数写的,编译器版本高了才会过(NOIP编译器版本不会太高);

只能老老实实打模拟。

小技巧:最后多输出“000”,计算秒就好了。(特判两个时间相同,只输出“0”)

T2

题意:m个站口,有n个人按顺序排队,求n+1个人最少等多长时间

解析:(标程显然 同下)

n<m 输出0(显然)

n>=m 建一个小根堆(可以用优先队列),把前m个人的时间扔到堆里

贪心策略:每次都放在用时较短的人的后面

每次取出堆顶t,删掉堆顶,把(当前时间+t)再扔到堆里。循环n-m

最后输出堆顶(就是答案)。

T3

题意:一个n*m的场地,有n11*2的砖,有n21*3的砖,每一块砖都有一定的价值,求可以铺下的最大价值。

解析:

解法一:基于连通性的状态压缩dp(不会)

解法二:贪心

       预处理出前缀和

sa[i]表示前i大的1*2的砖的价值和是sa[i];

sb[i]表示前i大的1*3的砖的价值和是sb[i];

先铺1*3的砖,对应1*2的砖的数目可求,那么本次价值t O(1)的时间 可求

       0->n*m/3扫一遍 ans=max(ans,t);

       输出ans

       注意:要特判n*m=2*2,2*5……的情况

            2*2为例,只能放两块1*2的砖,1*3的一块也放不了

 

 

下午

T1

题意:(祖玛游戏)给你一个只包含ABC的串,m次操作,每次在p位置,插入c字符,输出每次操作后的字符串。

脑补:

祖玛游戏 每次射击一个字符,若>=3个相同的连在一起,即可消去。消去后,两边的珠子像空隙靠拢、相连,若还有>=3个相同的连在一起,再次消去。

    但,若初始有>=3个相同的连在一起,不击打当前位置,依旧不会消除。

解析:

   手动打模拟。

T2

题意:n个元素按顺序进栈,求字典序最大的出栈序列。

解析:

贪心策略:

1、压到nn出栈,输出n      

2、如果后面有大于栈内元素的(这里可以用RMQ维护一下),继续压栈;

否则,出栈,输出当前元素。(对栈内每一个元素都操作)

3、输出栈内剩余的元素

T3

题意:n条线段,m次询问,每次一个p点的坐标,求线段OP n条线段会产生多少个交点

解析:

题目保证任意两条线段不相交,说明n条线段任意两两互相平行,即n条线段的斜率均为k

那么,先配对,再排序,再二分答案。

求出op与当前线段的交点。若交点在横坐标在(0x1&&纵坐标在(0y1),则线段op与当前线段有交点,即为合法解。否则,….

二分出op最远可与线段x有交点,则当先询问有x个交点(当前询问的答案)。

 

上午

T1代码:

#include<cstdio>#include<cstring>#include<ctime>#include<iostream>#define ll long longusing namespace std;int mth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};ll solve(){    int Y=0,M=0,D=0,h=0,m=0,s=0;    scanf("%d-%d-%d %d:%d:%d",&Y,&M,&D,&h,&m,&s);    Y-=2000;    ll ans=365*Y;    ans+=(Y+3)/4;    for(int i=1;i<M;i++) ans+=mth[i];    ans+=(!(Y%4)&&M>2)?1:0;    ans+=D;    ans*=86400;    ans+=(h*60+m)*60+s;    return ans;}int main(){    freopen("two.in","r",stdin);    freopen("two.out","w",stdout);    ll s1=solve();    ll s2=solve();    printf("%I64d%s\n",s2-s1,s2-s1?"000":"");    return 0;}

std版(不一定会过)

#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>using namespace std;#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endiftm *s,*t;int year,month,day,hour,minute,second;int main(){    freopen("two.in","r",stdin);    freopen("two.out","w",stdout);    scanf("%d-%d-%d %d:%d:%d",&year,&month,&day,&hour,&minute,&second);    s=new tm();    s->tm_year=year-1900;s->tm_mon=month-1;s->tm_mday=day;s->tm_hour=hour;s->tm_min=minute;s->tm_sec=second;    scanf("%d-%d-%d %d:%d:%d",&year,&month,&day,&hour,&minute,&second);    t=new tm();    t->tm_year=year-1900;t->tm_mon=month-1;t->tm_mday=day;t->tm_hour=hour;t->tm_min=minute;t->tm_sec=second;    printf(LL "\n",(long long)fabs(difftime(mktime(s),mktime(t)))*1000);    return 0;}

T2代码:

#include<cstdio>#include<iostream>#include<queue>#include<vector>#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;const int N=1e5+10;priority_queue<ll,vector<ll>,greater<ll> >q;ll n,m,a[N];inline const ll read(){    register ll x=0,f=1;    register char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=(x<<3)+(x<<1)+ch-0;ch=getchar();}    return x*f;}int main(){    freopen("death.in","r",stdin);    freopen("death.out","w",stdout);    n=read();m=read();    for(ll i=1;i<=n;i++) a[i]=read();    for(ll i=1;i<=m;i++) q.push(a[i]);    for(ll t,i=m+1;i<=n;i++){         t=q.top();q.pop();         q.push(t+a[i]);    }    ll ans=q.top();    printf(LL,ans);    return 0;} 

T3代码:

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int N=1e5+10;int T,n,m,n1,n2,a[N],b[N];int delta,ans,sa[N],sb[N];int main(){    freopen("eyesight.in","r",stdin);    freopen("eyesight.out","w",stdout);    scanf("%d",&T);    while(T--){        ans=0;        scanf("%d%d%d%d",&n,&m,&n1,&n2);        for(int i=1;i<=n1;i++) scanf("%d",&a[i]);        for(int i=1;i<=n2;i++) scanf("%d",&b[i]);        sort(a+1,a+n1+1,greater<int>());        sort(b+1,b+n2+1,greater<int>());        for(int i=1;i<=n1;i++) sa[i]=sa[i-1]+a[i];        for(int i=1;i<=n2;i++) sb[i]=sb[i-1]+b[i];        /*不严密的特判         if(n==2&&m==2){            printf("%d\n",sa[2]);            continue;        }        if((n==2&&m==5)||(n==5&&m==2)){            int t1=sb[2]+sa[2];            int t2=sb[1]+sa[3];            int t3=sa[5];            printf("%d\n",max(t1,max(t1,t2)));            continue;        }*/        delta=((n%3==2&&m%3==2)&&(n==2||m==2))?4:n*m%3;        int v=n*m;        int v1=min((v-delta)/3,n2);        for(int j,i=0;i<=v1;i++){            j=(v-i*3)>>1;            if(j>n1) j=n1;            ans=max(ans,sb[i]+sa[j]);        }        printf("%d\n",ans);    }    fclose(stdin);    fclose(stdout);    return 0;}

下午

T1代码:

#include<cstdio>#include<iostream>#include<cstring>#define name "ha"using namespace std;inline const int read(){    register int x=0,f=1;    register char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=(x<<3)+(x<<1)+ch-0;ch=getchar();}    return x*f;}inline const char in(){    for(register char ch=getchar();;ch=getchar()) if(ch>=A&&ch<=Z) return ch;}const int N=1e4+10;char a[N];int n,cas;char c;int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    gets(a+1);//注意空串     n=strlen(a+1);    cas=read();    for(int i=0,pos,l,r;i<cas;i++){        pos=read();c=in();        for(int i=n+1;i>=pos+2;i--) a[i]=a[i-1];        n++;        a[pos+1]=c;        for(;;){            for(l=pos;(l>=1)&&(a[l]==a[pos+1]);l--) continue;            for(r=pos+2;(r<=n)&&(a[r]==a[pos+1]);r++) continue;            int len=r-l-1;            if(len>=3){                pos=l;n-=len;                for(int i=pos+1;i<=n;i++) a[i]=a[i+len];                for(int i=n+1;i<=n+len;i++) a[i]=0;                a[n+1]=0;            }            else break;        }        if(n==0)            printf("-\n");        else            printf("%s\n",a+1);    }    return 0;}

T2代码:

#include<cstdio>#include<iostream>#include<string>#include<cmath>#define name "haha"using namespace std;inline const int read(){    register int x=0,f=1;    register char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=(x<<3)+(x<<1)+ch-0;ch=getchar();}    return x*f;}const int N=1e6+10;int n,a[N];int top,s[N];int f[N][21];short vis[N];inline void RMQ(){    for(int i=1;i<=n;i++) f[i][0]=a[i];    for(int j=1;j<=20;j++){        for(int i=1;i+(1<<j)-1<=n;i++){            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);        }    }}inline int query(int i,int j){    int k=log(j-i+1)/log(2);    return max(f[i][k],f[j-(1<<k)+1][k]);}int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    n=read();    int now=n;    for(int i=1;i<=n;i++) a[i]=read();    RMQ();    for(int i=1,mz;i<=n;i++){        s[++top]=a[i];        vis[a[i]]=1;        if(i==n) break;        mz=query(i+1,n);        if(mz>s[top]) continue;        for(;s[top]==now&&now&&top;){            printf("%d ",s[top]);            vis[s[top]]=0;            now--;top--;        }        if(s[top+1]==now+1){            /*mz=query(i+1,n);            if(mz>s[top]) continue;*/            for(;vis[now]&&s[top]>mz&&now&&top;top--){                printf("%d ",s[top]);vis[s[top]]=0;                if(s[top]==now&&top) now--;            }            for(;s[top]>mz&&top;top--)    printf("%d ",s[top]),vis[s[top]]=0;        }        for(;s[top]>mz&&top;top--)    printf("%d ",s[top]),vis[s[top]]=0;    }    for(;top;top--) printf("%d ",s[top]);    return 0;}

T3代码:

#include<cstdio>#include<algorithm>#define DB double#define name "hahaha"using namespace std;inline const int read(){    register int x=0,f=1;    register char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=(x<<3)+(x<<1)+ch-0;ch=getchar();}    return x*f;}const int N=2e5+10;int n,m,X[N],Y[N];DB B[N],K[N];bool check(DB x1,DB y1,int mid){    if(K[mid]*x1+B[mid]>y1) return 0;    return 1;}int main(){    freopen("hahaha.in","r",stdin);    freopen("hahaha.out","w",stdout);    n=read();    for(int i=1;i<=n;i++) X[i]=read();    for(int i=1;i<=n;i++) Y[i]=read();    sort(X+1,X+n+1);sort(Y+1,Y+n+1);    for(int i=1;i<=n;i++){        B[i]=(DB)Y[i];        K[i]=-(DB)Y[i]/(DB)X[i];    }    m=read();    for(int i=1,x,y;i<=m;i++){        x=read();y=read();        int l=1,r=n,mid,ans=0;        while(l<=r){            mid=l+r>>1;            if(check(x,y,mid)) ans=mid,l=mid+1;            else r=mid-1;        }        printf("%d\n",ans);    }    return 0;}

济南-1029试题解题报告