C2020 2020.10.31模拟赛

信息学——模拟赛

考试情况

期望得分VS实际得分

期望得分：

实际得分：

吐槽一句：这几乎三暴力的码力赛实在是打得累……

T1 pairup

$1^o$ 分析

可以得到一个显然的贪心：从小到大排序后，所有的首尾组对一定包含最优解。（正确性太显然，不证了）

但我们发现$m$范围最大可到$10^9$，暴力做显然会T

考虑题面中$n$的范围较小，所以考虑复杂度与$n$有关，显然我们会发现，在暴力匹配的过程中，会有很多冗余，即我们会把相同的两个数匹配多次，考虑去掉这样的冗余。

我们可以按块匹配，这样复杂度就成了$O(n\log n)$

//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,ans;
struct node{
    int num,val;
}a[100005];
inline bool operator <(node x,node y)
{
    return x.val<y.val;
}
int main(){
    //freopen("pairup.in","r",stdin);
    //freopen("pairup.out","w",stdout);
    n=read();
    for (register int i=1;i<=n;++i)
        a[i].num=read(),a[i].val=read();
    sort(a+1,a+n+1);
    int r=n,num=a[n].num;
    for (register int i=1;i<=r;++i)
        {
        ans=max(ans,a[i].val+a[r].val);
        while (a[i].num>=num)
              a[i].num-=num,r--,num=a[r].num;
        num-=a[i].num;
        }
    printf("%d",ans);
    return 0;
}

T2 genomics

$1^o$ 分析

阅读理解题，题面较难读。

本质就是要我们找符合要求的三元组数量，考虑按题意模拟。

枚举这三个位置，开个标记记录有斑点的串，看无斑点的串是否被打上过标记即可。

//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,m;
int a[505][55],b[505][55],bj[55][55][55],cnt[55][4],flag,ans;
int main(){
    //freopen("cownomics.in","r",stdin);
    //freopen("cownomics.out","w",stdout);
    n=read(),m=read();
    char c;
    for (register int i=1;i<=n;++i)
        {
        for (register int j=1;j<=m;++j)
            {
            while (!isalpha(c=getchar()));
            a[i][j]=(c=='A'?1:(c=='C'?2:(c=='G'?3:4)));
            }
        }
    for (register int i=1;i<=n;++i)
        {
        for (register int j=1;j<=m;++j)
            {
            while (!isalpha(c=getchar()));
            b[i][j]=(c=='A'?1:(c=='C'?2:(c=='G'?3:4)));
            }
        }
    for (register int i=1;i<=m;++i)
        for (register int j=i+1;j<=m;++j)
            for (register int k=j+1;k<=m;++k)
                {
                flag=1;
                for (register int p=1;p<=n;++p)
                    bj[a[p][i]][a[p][j]][a[p][k]]=1;
                for (register int p=1;p<=n;++p)
                    if (bj[b[p][i]][b[p][j]][b[p][k]])
                       flag=0;
                ans+=flag;
                for (register int p=1;p<=n;++p)
                    bj[a[p][i]][a[p][j]][a[p][k]]=0;
                }
    printf("%d",ans);
    return 0;
}

$2^o$ 反思与总结

复杂度跑满了似乎可以被卡掉的，但偏偏跑不满。

当然这里实现的时候，一个非常常用的卡常技巧就是很多时候数组清空是可以不用$memset$的，只把用过的清零，这样复杂度不容易跑满。

T3 where

$1^o$ 分析

可以看到$n$非常小，而也没有其他的值非常大的，基本就考虑模拟了。

首先用$O(n^4)$的时间枚举矩形的两个端点（左上与右下）。

然后枚举这个矩形中的每个点，统计颜色，通过BFS求联通块，这里复杂度$O(n^2)$。

总复杂度$O(n^6)$（这复杂度……）

但到这里还不行，题目还要求考虑包含的情况，所以我们需要把每个解的矩形（左上端点与右下端点）存下来判断一遍包含关系。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define mp make_pair
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 sx,sy,ex,ey;
};
int n;
int a[25][25],go[4][2]={{0,1},{0,-1},{1,0},{-1,0}},col,col1,col2,tot1,tot2,ans;
bool b[35],vst[25][25];
vector <node> vec; 
queue < pair<int,int> > q;
inline void search(int lx,int ly,int rx,int ry,int sx,int sy,int col)
{
    q.push(mp(sx,sy)),vst[sx][sy]=1;
    while (!q.empty())
          {
          int x=q.front().first,y=q.front().second;
          q.pop();
          for (register int i=0;i<4;++i)
              {
              int nx=x+go[i][0],ny=y+go[i][1];
              if (nx<lx||ny<ly||nx>rx||ny>ry||vst[nx][ny]||a[nx][ny]!=col)
                 continue;
              q.push(mp(nx,ny)),vst[nx][ny]=1;
              }
          }
}
inline bool check(int x)
{
    int sz=vec.size();
    for (register int i=0;i<sz;++i)
        if (i!=x&&vec[i].sx<=vec[x].sx&&vec[i].sy<=vec[x].sy&&vec[i].ex>=vec[x].ex&&vec[i].ey>=vec[x].ey)
           return 0;
    return 1;
}
inline bool work(int sx,int sy,int ex,int ey)
{
    memset(vst,0,sizeof(vst));
    memset(b,0,sizeof(b));
    col=col1=col2=tot1=tot2=0;
    for (register int x=sx;x<=ex;++x)
        for (register int y=sy;y<=ey;++y)
            if (!vst[x][y])
               {
               if (!b[a[x][y]])
                  {
                  col++;
                  if (!col1)
                     col1=a[x][y],b[a[x][y]]=1;
                  else
                  if (!col2)
                     col2=a[x][y],b[a[x][y]]=1;
                  if (col>2)
                     return 0;
                  }
                if (a[x][y]==col1)
                   search(sx,sy,ex,ey,x,y,a[x][y]),tot1++;
                if (a[x][y]==col2)
                   search(sx,sy,ex,ey,x,y,a[x][y]),tot2++;
               }
    if ((tot1==1&&tot2>=2)||(tot2==1&&tot1>=2))
       return 1;
    return 0;
}
int main(){
   //freopen("where.in","r",stdin);
   //freopen("where.out","w",stdout);
    n=read();
    char c;
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            {
            while (!isalpha(c=getchar()));
            a[i][j]=c-'A'+1;
            }
    for (register int sx=1;sx<=n;++sx)
        for (register int sy=1;sy<=n;++sy)
            for (register int ex=sx;ex<=n;++ex)
                for (register int ey=sy;ey<=n;++ey)
                    if (work(sx,sy,ex,ey))
                       vec.push_back((node){sx,sy,ex,ey});
    int sz=vec.size();
    for (register int i=0;i<sz;++i)
        if (check(i))
           ans++;
    printf("%d",ans);
    return 0;
}

$2^o$ 反思与总结

细节较多，这种算法比较明显的题就拼码力，细节和实现技巧了。

事实证明实现技巧比较重要。