[考试反思]1025csp-s模拟测试87：生存

想起一句话

课上求生存，课下求发展

发展还好说，如何生存？

生存很困难。。。

没什么可抱怨的。有AK的。高分的也很多。

该说的在《Dust》里说完了，安静会吧。

这场rank43怎么追？

最大240分差，可能这一轮就完蛋了。

知道有多紧迫了吗？

上次爆个0导致追不回来直接滚出第一机房依旧令我印象深刻。

OI不会给你任何一次失手的机会。CSP-S也只有6道题。

这一天下来分数上限就是360了？

再说这样的话Day2还能稳住心态吗？

省一可能都拿不到吧？

不要轻视任何一道题与任意一次考试，希望不要在CSP上付出代价。

时间分配也有一点问题，难易度判断又挂了。

T1：maze

注意，OI坐标系横着是y轴竖着是x轴，与数学坐标系不同。

样例又是精心构造的。

爆零快乐。

二分+最短路，没什么好说的。

 #include<cstdio>

 #include<queue>

 using namespace std;

 struct P{int x,y;double d;friend bool operator<(P a,P b){return a.d>b.d;}};

 priority_queue<P>q;

 #define tx x+xx[i]

 #define ty y+yy[i]

 const int yy[]={,,,-};

 const int xx[]={,-,,};

 int n,m,can[][],sx,sy,ex,ey;double s,dt[][];

 bool chk(double k){

     for(int i=;i<=n;++i)for(int j=;j<=m;++j)dt[i][j]=1e16;

     dt[sx][sy]=;

     q.push((P){sx,sy,});

     while(!q.empty()){

         int x=q.top().x,y=q.top().y;double d=q.top().d;q.pop();

         if(d-dt[x][y]>1e-)continue;

         for(int i=;i<=;++i)if(can[tx][ty]&&dt[tx][ty]>d+k)

             q.push((P){tx,ty,dt[tx][ty]=d+k});

         for(int i=;i<=;++i)if(can[tx][ty]&&dt[tx][ty]>d+)

             q.push((P){tx,ty,dt[tx][ty]=d+});

     }

     return dt[ex][ey]<s;

 }

 int main(){

     scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ex,&ey);

     for(int i=;i<=n;++i) for(int j=;j<=n;++j) scanf("%d",&can[i][j]), can[i][j]^=;

     scanf("%lf",&s);

     double l=,r=;

     while(r-l>1e-)if(chk((l+r)/))l=(l+r)/;else r=(l+r)/;

     printf("%.3lf\n",l);

 }

T2：bird

考场上就能看出来是个朴素的线段树优化dp。

但是分配时间不够，没细想。

因为一只鸟不能被打两遍，所以用线段树上的加减“篡改”一下转移值。

全场倒数第4个改出来。状态极差，效率极低。

 #include<cstdio>

 #include<iostream>

 #include<vector>

 using namespace std;

 vector<int>v1[],v2[];

 int mx[],cl[],cr[],lz[],n,ans,k,l,r,cf[];

 void build(int p,int l,int r){

     cl[p]=l;cr[p]=r;

     if(l==r)return;

     build(p<<,l,l+r>>);build(p<<|,(l+r>>)+,r);

 }

 void down(int p){

     mx[p<<]+=lz[p];mx[p<<|]+=lz[p];

     lz[p<<]+=lz[p];lz[p<<|]+=lz[p];

     lz[p]=;

 }

 int ask(int p,int l,int r){if(r<l)return ;

     if(l<=cl[p]&&cr[p]<=r)return mx[p];

     if(lz[p])down(p);

     return max(l<=cr[p<<]?ask(p<<,l,r):,r>=cl[p<<|]?ask(p<<|,l,r):);

 }

 void add(int p,int l,int r,int w){

     if(l<=cl[p]&&cr[p]<=r){mx[p]+=w;lz[p]+=w;return;}

     if(lz[p])down(p);

     if(l<=cr[p<<])add(p<<,l,r,w);

     if(r>=cl[p<<|])add(p<<|,l,r,w);

     mx[p]=max(mx[p<<],mx[p<<|]);

 }

 int main(){

     build(,,);

     scanf("%d%d",&n,&k);

     while(n--){

         scanf("%d%d",&l,&r);

         l=max(l,);

         if(r<)continue;

         v1[l].push_back(r),v2[r].push_back(l);

         cf[l]++;cf[r+]--;

     }int cnt=;

     for(int i=;i<=;++i){

         if(i)cf[i]+=cf[i-];

         for(int j=;j<v1[i].size();++j)add(,i,v1[i][j],-);

         int x=ask(,,i-k)+cf[i];

         add(,i,i,x);ans=max(ans,x);

         for(int j=;j<v2[i].size();++j)add(,v2[i][j],i,+);

     }printf("%d\n",ans);

 }

T3：stone

第二天早上改题，状态回升。

显然可以打表，考场上也打出了dp。然后没有找到规律。

表太小了看不出来，其实打表得到的1是联通的，中间凭空出现了几个零散的0。

出现0的条件是a[i]=b[j-1]&&a[i-1]=b[j]&&a[i]!=a[i-1]

证明skyh说的挺好的，我太菜不写了

然后用子序列dp干一下处理出每一行的左右端点，再挖去0。

因为只有3种字符，所以手动讨论一下相邻两位的字符，用前缀和统计一下每个字符串在b里出现的次数，在a的lr之间求出即可。

 #include<cstdio>

 #include<iostream>

 using namespace std;

 char a[],b[];int n,m,l[],r[];long long ans;

 int ab[],ac[],ba[],bc[],ca[],cb[];

 int main(){

     scanf("%s%s",a+,b+);

     while(a[n+])n++;

     while(b[m+])m++;

     int p1=,p2=;

     for(int i=;i<=n;++i)if(a[i]==b[p1])l[i]=p1++;else l[i]=p1;

     for(int i=;i<=m;++i)if(b[i]==a[p2])p2++,r[p2]=min(i+,m);else r[p2]=min(i+,m);

     if(!r[])r[]=;

     for(int i=;i<=n;++i)if(!r[i])r[i]=m;

     for(int i=;i<=m;++i){

              if(b[i]=='A'&&b[i-]=='C')ac[i]++;

         else if(b[i]=='A'&&b[i-]=='B')ab[i]++;

         else if(b[i]=='B'&&b[i-]=='A')ba[i]++;

         else if(b[i]=='B'&&b[i-]=='C')bc[i]++;

         else if(b[i]=='C'&&b[i-]=='A')ca[i]++;

         else if(b[i]=='C'&&b[i-]=='B')cb[i]++;

         ac[i]+=ac[i-];ab[i]+=ab[i-];

         bc[i]+=bc[i-];ba[i]+=ba[i-];

         ca[i]+=ca[i-];cb[i]+=cb[i-];

     }

     for(int i=;i<=n;++i)ans+=r[i]-l[i]+;

     for(int i=;i<=n;++i)

              if(a[i]=='A'&&a[i-]=='C')ans-=ca[r[i]]-ca[l[i]-];

         else if(a[i]=='A'&&a[i-]=='B')ans-=ba[r[i]]-ba[l[i]-];

         else if(a[i]=='B'&&a[i-]=='A')ans-=ab[r[i]]-ab[l[i]-];

         else if(a[i]=='B'&&a[i-]=='C')ans-=cb[r[i]]-cb[l[i]-];

         else if(a[i]=='C'&&a[i-]=='A')ans-=ac[r[i]]-ac[l[i]-];

         else if(a[i]=='C'&&a[i-]=='B')ans-=bc[r[i]]-bc[l[i]-];

     printf("%lld\n",ans);

 }

巴特西

[考试反思]1025csp-s模拟测试87：生存

最新文章

热门文章