C2020 2020.10.24模拟赛

信息学——模拟赛

考试情况

预计分数VS实际分数

预计分数：

实际分数：

T1 cows

$1^o$ 分析

显然的二分答案，二分R，$check$ K，从第一堆草枚举，对于每一堆还没覆盖的草，以当前草为左端点，算出右端点，以此覆盖与K比较即可。

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,k;
int a[50005],maxx;
inline bool check(int r)
{
    int tot=1,now=a[1]+r*2;
    for (register int i=2;i<=n;++i)
        if (a[i]>now)
           now=a[i]+r*2,tot++;
    return tot<=k;
}
inline void erfen()
{
    int l=-1,r=maxx+1;
    while (l+1<r)
          {
          int mid=(l+r)>>1;
          if (check(mid))
             r=mid;
          else
             l=mid;
          }
    printf("%d",r);
}
int main(){
    freopen("cows.in","r",stdin);
    freopen("cows.out","w",stdout);
    n=read(),k=read();
    for (register int i=1;i<=n;++i)
        a[i]=read(),maxx=max(maxx,a[i]);
    sort(a+1,a+n+1);
    erfen();
    return 0;
}

T2 div7

$1^o$ 分析

一段区间的和被7整除，看到区间和自然想到前缀和。

进一步想到如果两个前缀和$mod$ 7同余，那么他们俩相减得到的区间就是被7整除的。

那么只要依次求前缀和，找到与当前余数相同的最早的那个点相减即可。

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int a[50005],f[7],sum,ans;
signed main(){
    freopen("div7.in","r",stdin);
    freopen("div7.out","w",stdout);
    n=read();
    for (register int i=1;i<=n;++i)
        {
        a[i]=read(),a[i]%=7,sum=(sum+a[i])%7;
        if (!a[i])
           ans=max(ans,1);
        if (!f[sum])
           f[sum]=i;
        ans=max(ans,i-f[sum]);
        }
    printf("%d",ans);
    return 0;
}

$2^o$ 总结与反思

提一句，虽然这题比较水，但其思想其实是来源于“剩余系”，一个很好用的思想。

T3 gates

$1^o$ 分析

话说考场莫名$hack$掉题面？感觉这翻译有点捞。

显然是要我们求封闭区间的个数。

考虑如何求，发现只要求交点个数即可，但是由于题面说可以重复走，会影响到判断，所以还需开个标记，记录每次走的出发点与方向，计数时终点反方向走到起点的标记必须为0。（说得好像有点抽象，看代码理解吧）

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
struct node{
    int x,y,to;
};
int n,x,y,ans,op;
int go[4][2]={{-1,0},{1,0},{0,-1},{0,1}},vst[2005][2005];
map <node,int> mapp;
char c;
inline bool operator <(node a,node b)
{
    return a.x!=b.x?a.x<b.x:(a.y!=b.y?a.y<b.y:a.to<b.to);
}
inline int calc(char c)
{
    if (c=='N')
       return 0;
    if (c=='S')
       return 1;
    if (c=='W')
       return 2;
    if (c=='E')
       return 3;
}
inline int inv(int x)
{
    return x&1?x-1:x+1;
}
int main(){
    n=read();
    x=1000,y=1000,vst[x][y]=1;
    for (register int i=1;i<=n;++i)
        {
        while (!isalpha(c=getchar()));
        int to=calc(c),nx=x+go[to][0],ny=y+go[to][1];
        mapp[(node){x,y,to}]=1;
        if (vst[nx][ny]&&!mapp[(node){nx,ny,inv(to)}])
           ans++;
        mapp[(node){nx,ny,inv(to)}]=1,vst[nx][ny]=1;
        x=nx,y=ny;
        }
    printf("%d",ans);
    return 0;
};

$2^o$ 总结与反思

考场上很多人挂了空间，实际上只需要用map维护，由于题目可以有负数所以需要将范围开大，但显然并没有全部打上标记，会浪费很多空间。

我考场上正向走和反向走都判了然后挂了，解释一下为什么不能判正向，有可能有两个封闭区间有重边，而且是同一个方向走来的，这时候你会少算一个。