C2020 2020.10.17模拟赛

信息学——模拟赛

考试情况

期望得分VS实际得分

期望得分：

实际得分：

T1 sort

$1^o$ 分析

观察伪代码，他每一次都把相邻的两个逆序对交换了。

所以一开始准备求逆序对，后来发现不用，只需要看一个数到他应该到达的位置走的步数就好了，答案就是最多的一个，

但这样只能拿80，什么问题呢？

可以发现在交换一个逆序对的时候，同时使得一个要向前走的和一个向后走的都减少了一步，所以我们只能统计向前走的或者向后走的，不能都统计。

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

$2^o$ 思考与总结

考场上两个方向都统计了，事实证明不对拍就是会挂。

T2 lemonade

$1^o$ 分析

三道中最水的，显然一个贪心，按$w$从大到小排序，模拟即可（正确性显然，不证了）。

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

T3 multimoo

$1^o$ 分析

很好的一道题，大多数人最后还是用搜索+剪枝写的，这里讲一种复杂度不错的并查集写法。

首先第一问很好并查集，把两个相邻的颜色相同的点合并就好了，并查集多记录一个$num$就可得出结果。

考虑第二问。

此时我们已经处理出了每个联通块所对应的信息，包括颜色和数量。

第二问可以类比第一问，如果我们把每个联通块看成一个点，那么就把两个相邻的颜色不同的点合并就好了。

可问题是这两种不同的颜色是需要枚举的，那么就有两个问题，如何保证复杂度？如何还原并查集？

下面依次解决一下：

$1.$如何保证复杂度

不同的两种颜色显然是要枚举的，考虑如何让合并过程变为$O(n)$

我们发现冗余之处在于我们多搜了很多不属于这两种颜色的点，所以考虑将两个相邻的联通块建边，然后按照两种颜色为关键字排序。

这里注意为了方便处理两种颜色一定要是第一个小，第二个大。

那么我们只要按照这个顺序遍历，当前遍历到的所有边都是链接当前所枚举的颜色的边，显然每条边最多被枚举一次，而最多有$4n$条边，故复杂度降至$O(n^3)$，加上排序就是$O(n^3\log n)$

$2.$如何还原并查集

我们会发现在合并的过程中会改变原来边的状态，导致后面的合并出现问题。

但简单的并查集是无法撤销的，这里给出一种方法：

我们在建边的过程中就找出所有满足$father[i]=i$的点，并对应他的颜色$col$，将这个点放进一个$vec[col]$的$vector$里去。

然后再备份一遍$num$，这样的话当前枚举的颜色统计完之后，就扫对应的$vec[col]$，然后用$father[vec[col]]=vec[col]$还原即可。

总复杂度……大概是$O(n^3\log n)$的，且比较稳定。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define pb push_back
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;
struct node{
    int u,v,col1,col2;
}line[250005];
int len;
int a[255][255],father[62505],num[62505],cnt[62505],go[4][2]={{1,0},{-1,0},{0,1},{0,-1}},ans1,ans2;
vector <int> vec[1000005];
inline bool operator <(node x,node y)
{
    return x.col1!=y.col1?x.col1<y.col1:x.col2<y.col2;
}
inline void make_map(int u,int v,int col1,int col2)
{
    len++,line[len].u=u,line[len].v=v,line[len].col1=col1,line[len].col2=col2;
}
inline int calc(int x,int y)
{
    return (x-1)*n+y;
}
inline int Find(int x)
{
    if (father[x]!=x)
       return father[x]=Find(father[x]);
    return father[x];
}
inline void unnion(int f1,int f2)
{
    father[f2]=f1,num[f1]+=num[f2];
}
inline void update(int x)
{
    int vec_len=vec[x].size();
    for (register int i=0;i<vec_len;++i)
        father[vec[x][i]]=vec[x][i],num[vec[x][i]]=cnt[vec[x][i]];
}
int main(){
    freopen("multimoo.in","r",stdin);
    freopen("multimoo.out","w",stdout);
    n=read();
    for (register int i=1;i<=n*n;++i)
        father[i]=i,num[i]=1;
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            a[i][j]=read();
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            {
            int f1=Find(calc(i,j));
            for (register int k=0;k<4;++k)
                {
                int x=i+go[k][0],y=j+go[k][1];
                if (x<1||y<1||x>n||y>n||a[x][y]!=a[i][j])
                   continue;
                int f2=Find(calc(x,y));
                if (f1!=f2)
                   unnion(f1,f2);
                }
            ans1=max(ans1,num[Find(f1)]);
            }
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            {
            cnt[calc(i,j)]=num[calc(i,j)];
            int f1=Find(calc(i,j));
            if (f1==calc(i,j))
               vec[a[i][j]].pb(calc(i,j));
            for (register int k=0;k<4;++k)
                {
                int x=i+go[k][0],y=j+go[k][1];
                if (x<1||y<1||x>n||y>n||a[x][y]==a[i][j])
                   continue;
                int f2=Find(calc(x,y));
                make_map(f1,f2,min(a[i][j],a[x][y]),max(a[i][j],a[x][y]));
                }
            }
    sort(line+1,line+len+1);
    for (register int i=1;i<=len;++i)
        {
        int col1=line[i].col1,col2=line[i].col2;
        while (line[i].col1==col1&&line[i].col2==col2)
              {
              int f1=Find(line[i].u),f2=Find(line[i].v);
              if (f1!=f2)
                 unnion(f1,f2);
              ans2=max(ans2,num[Find(f1)]);              
              i++;
              }
        update(col1),update(col2);
        }
    printf("%d\n%d",ans1,ans2);
    return 0;
}

$2^o$ 总结与反思

本题为并查集极其灵活的运用，值得多去思考。