省常中联测题选VI HGOI1024

差一个常数就AK了!!!!

为了保证正确性二分边界略大了一点。

于是超时3个点。


T1 Equation

题目描述

石神给学⽣生出了⼀一道简单的求导题。题中保证不出现指数相同的项,同时要求不改变求导前后每一项的顺序。

解析

  • 字符串处理题。除了一些细节外略水。
  • 用stringstream水过

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
string src,tmp;
ll len,cnt=0;
stringstream ssr;
#define SGN(X) ((X)=='+'||(X)=='-')
#define STA(X) (!SGN(X)&&!isdigit(X)&&(X)!='^')
int main(){
    //freopen("equation.in","r",stdin);
    //freopen("equation.out","w",stdout);
    cin>>src;
    len=src.length();
    for (Rint i=0;i<len;i++){
        if (STA(src[i])) {
            if (i==0||SGN(src[i-1]))ssr<<1;
            ssr<<src[i];
            if (i==len-1)ssr<<"^1";
            cnt++;
        }else if (SGN(src[i])){
            if (i&&STA(src[i-1]))ssr<<"^1";
            ssr<<src[i];
        }else{
            ssr<<src[i];
        }
    }
    ll t1,t2;char cc='*',cc2,cc3='*';
    if (cnt==0){puts("0");return 0;}
    for (Rint i=1;i<=cnt;i++){
        ssr>>t1>>cc;
        if (SGN(cc)){i--;cc3=cc;continue;}
        if (cc3!='*'&&i>1)putchar(cc3);
        ssr>>cc2>>t2;
        if (t2>2)printf("%lld%c^%lld",t1*t2,cc,t2-1);
        else if(t2==2)printf("%lld%c",t1*t2,cc);
        else printf("%lld",t1*t2);
        ssr>>cc3;
    }
    return 0;
}

T2 Survey

题目描述

这⼀一次的考试,学生的成绩分为k等,成绩单上按照学生的学号排序。此外,学校要抽一些同学的考卷去调研,石神将这个任务委派给了你。
抽取的样本有如下要求:
学号连续的学生
得到1等的学生数量在[l_1,r_1]区间内
得到2等的学生数量在[l_2,r_2]区间内
…
现在请问有多少种抽取样本的方法。

解析

  • 略有难度的一道题。
  • 一开始考虑到前缀和加二分,然而数据范围过大无法允许这样操作。
  • 然后想到Two Pointer。但是可以发现,若一个区间可行,并不是其所有其子区间都可行(因为下界的限制)
  • 所以可以使用Three Pointer来解决这道问题。第一个指针表示区间左端点第二个指针表示最早可行的区间端点的下一个,第三个指针表示最早不可行的区间端点。那么其中间的所有区间就满足条件
  • 第三个指针很好处理,只需要一直向右,直到任意一个超过限制停止。
  • 第二个指针就需要一定的技巧(我在考场上想了很久orz)。我使用了一个计数变量cnt,表示还没有达到下界的等第有几种。所以只需一直向右扫,直到cnt等于零就为最早可行端点的下一个。
  • 值得注意的是,若当前情况不论怎么样都无法让所有的上界和下界都满足,则会出现第二个指针大于第三个指针的情况,这里就不能加到答案里去。
  • 别的细节详见程序。

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
ll m,n;
ll src[200010],liml[200010],limr[200010],sum1[200010],sum2[200010];
int main(){
    ////freopen("survey.in","r",stdin);
    //freopen("survey.out","w",stdout);
    n=read(),m=read();
    ll cnt=m;
    for (Rint i=1;i<=n;i++)
        src[i]=read();
    for (Rint i=1;i<=m;i++){
        liml[i]=read(),limr[i]=read();
        if(liml[i]==0)cnt--;
    }
    ll t1=1,t2=1,res=0;
    for (Rint i=1;i<=n;i++){
        while(t1<i)t1++;
        while(t2<i)t2++;
        if(i>1){
            if (sum1[src[i-1]]==liml[src[i-1]])cnt++;
            sum1[src[i-1]]--;
            sum2[src[i-1]]--;
        }
        while(t2<=n&&sum2[src[t2]]<limr[src[t2]]){
            sum2[src[t2]]++;
            t2++;
        }
        while(t1<=n&&cnt){
            if (sum1[src[t1]]==liml[src[t1]]-1)cnt--;
            sum1[src[t1]]++;
            t1++;
        }
        if (t1<=t2&&cnt==0){
            res+=t2-t1+1;
        }
    }
    printf("%lld",res);
    return 0;
}

T3 Track

题目描述

    整个城市的地图形成了一棵树,初始时石神在其中的S点,两个陌生人分别在P和Q点。为了更好地描述他们的移动方法,将其看成3秒为周期(k=0,1,2,3,...):
第3k+1秒石神可以静止或者移动到任意相邻的结点,两个陌生人暂不行动。
第3k+2秒和第3k+3秒两个陌生人朝着石神的方向走到相邻的结点,石神暂不行动。
现在请问石神最迟在第几秒的时候被追上。

解析

  • 三十分钟打完的题。
  • 第一眼看到就觉得没有那么难,稍加思考想到了分步广搜来解决。
  • 首先因为石神可以瞎走,所以我处理时就将它可能走到的所有位置都进行了处理,同时也处理出陌生人某个时刻能够走到的所有范围。
  • 倘若任意一个时刻陌生人能够走到的范围完全覆盖了石神的行走范围,那么石神无路可走,这样的时间长度他就会被抓。
  • 于是对于每个时间段,只需要判断此时石神剩余的不会被抓的行走范围即可。
  • 我在考试里使用了二分进行操作

然而这道题根本不用二分!!!!!!!!!

  • 只需要从小到大枚举时刻,判断两个范围是否覆盖即可
  • 这里我用了两个队列,相当于在两个同样的图中进行广搜

AC程序(改编优化的考场版本,使用了根本没用的二分。)

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
ll n,s,p,q;
ll hd[200010],nxt[400010],eds[400010],et=0;
inline void ad(ll u,ll v){
    eds[++et]=v;
    nxt[et]=hd[u];
    hd[u]=et;
}
ll fg1[200010],fg2[200010],rst;
queue<ll>q1,q2;
ll check(ll x){
    rst=0;
    memset(fg1,-1,sizeof(fg1));
    memset(fg2,-1,sizeof(fg2));
    while(!q1.empty())q1.pop();
    while(!q2.empty())q2.pop();
    fg1[s]=0,fg2[p]=0,fg2[q]=0;
    q1.push(s),q2.push(p),q2.push(q);
    rst=1;
    ll now;
    for (Rint i=0;i<x;i++){
        if (!(i%3)){
            while(!q1.empty()){
                now=q1.front();
                if(fg1[now]==(i/3)+1)break;
                q1.pop();
                for (Rint i=hd[now];i;i=nxt[i])
                    if (fg1[eds[i]]==-1){
                        if (fg2[eds[i]]==-1){
                            rst++;
                            q1.push(eds[i]);
                            fg1[eds[i]]=fg1[now]+1;
                        }       
                    }
            }
        }else{
            while(!q2.empty()){
                now=q2.front();
                if(fg2[now]==(i/3*2+i%3))break;
                q2.pop();
                for (Rint i=hd[now];i;i=nxt[i])
                    if (fg2[eds[i]]==-1){
                        q2.push(eds[i]);
                        fg2[eds[i]]=fg2[now]+1;
                        if(~fg1[eds[i]])rst--;
                        if(rst==0)return true;
                    }//原来我把push放在外面,会导致超时。 
            }
        }
    }
    return false;
}
int main(){
    n=read(),s=read(),p=read(),q=read();
    ll t1,t2;
    for (Rint i=1;i<n;i++){
        t1=read(),t2=read();
        ad(t1,t2);
        ad(t2,t1);
    }
    ll l=0,r=2*n,mid,ans=-1;//r原来是3*n+1,会超时 
    while(l<=r){
        mid=(l+r)>>1;
        if (check(mid)){
            ans=mid;
            r=mid-1;
        }else
            l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}

发表评论

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