C2020 2020.10.25模拟赛

信息学——模拟赛

---

考试情况

期望得分VS实际得分

期望得分：

T1	T2	T3	总分
50	100	100	250

实际得分：

T1	T2	T3	总分
0	100	100	200

虽然只有我一个人切了T2，但由于我T1抱灵，所以并不影响我只拿了$Rank3$……

T1 Reduction

$1^o$ 分析

由于求面积要求$x,y$的最值，所以很显然的结论：我们删得时候也要删当前带最值的点。

那么就有4个方向可以删，而删得点只有3个，不难想到直接搜索这三个点分别来自哪个方向的最值。

但问题在于，一个点可能同时是多个方向的最值。

那么这个时候我们只要将这个点跳过继续找下一个点并且删点数不增加就好了（参照代码理解）。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define INF INT_MAX
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=INF;
struct node1{
    int x,id;
}a[50005];
struct node2{
    int y,id;
}b[50005];
bool vst[50005];
inline bool operator < (node1 x,node1 y)
{
    return x.x<y.x;
}
inline bool operator < (node2 x,node2 y)
{
    return x.y<y.y;
}
inline void search(int maxx,int minx,int maxy,int miny,int len)
{
    if (len==4)
       {
       while (vst[a[minx].id])
             minx++;
       while (vst[a[maxx].id])
             maxx--;
       while (vst[b[miny].id])
             miny++;
       while (vst[b[maxy].id])
             maxy--;
       ans=min(ans,(a[maxx].x-a[minx].x)*(b[maxy].y-b[miny].y));
       return ;
       }
    for (register int i=1;i<=4;++i)
        {
        if (i==1)
           {
           if (vst[a[minx].id])
              search(maxx,minx+1,maxy,miny,len);
           else
              vst[a[minx].id]=1,search(maxx,minx+1,maxy,miny,len+1),vst[a[minx].id]=0;
           }
        if (i==2)
           {
           if (vst[a[maxx].id])
              search(maxx-1,minx,maxy,miny,len);
           else
              vst[a[maxx].id]=1,search(maxx-1,minx,maxy,miny,len+1),vst[a[maxx].id]=0;
           }
        if (i==3)
           {
           if (vst[b[miny].id])
              search(maxx,minx,maxy,miny+1,len);
           else
              vst[b[miny].id]=1,search(maxx,minx,maxy,miny+1,len+1),vst[b[miny].id]=0;
           }
        if (i==4)
           {
           if (vst[b[maxy].id])
              search(maxx,minx,maxy-1,miny,len);
           else
              vst[b[maxy].id]=1,search(maxx,minx,maxy-1,miny,len+1),vst[b[maxy].id]=0;
           }
        }
}
int main(){
    //freopen("reduction.in","r",stdin);
    //freopen("reduction.out","w",stdout);
    n=read();
    for (register int i=1;i<=n;++i)
        a[i].x=read(),b[i].y=read(),a[i].id=b[i].id=i;
    sort(a+1,a+n+1),sort(b+1,b+n+1);
    search(n,1,n,1,1);
    printf("%d",ans);
    return 0;
}

$2^o$ 反思与总结

其实挺简单的一题，不知道为什么考试的时候非要放到最后一个做，结果就没调出来。（觉得码量大？还是我脑抽了？）

然后要注意的一个点，首先就是要考虑到一个点可能是多个方向下的最值。

还有就是最后统计答案的时候必须要用4个$while$找到每个方向第一个未被删除的点。

T2 Diamond

$1^o$ 分析

挺好的一道思维题。

这题的麻烦之处在于有两个架子，并且两个架子之间会互相影响。

我们先考虑一个架子怎么做。

一个显然的$O(n\log n)$算法：

对数组排序，枚举每一个点$i$，二分（这里用$upper$_$bound$）出第一个大于$a[i]+k$的位置，设为$r[i]$。

那么以点$i$的答案就是$r[i]-i$

考虑再加一个架子怎么做。

变化无非就是少了$i$到$r[i]$这一串，让我们再取出尽量长的一串。

然后可以发现$[1,i-1]$与$[r[i],n]$不会跨越一起连接成一串，也就是答案要么在前面的区间，要么在后面的区间。

但我们考虑如果算了前面的区间，由于$i$的枚举顺序，答案会算重复（虽然似乎没什么影响）。

所以我们只考虑后面的区间取到最长的一串。

那就变成了一个子问题，考虑做一个后缀$max$记为$f[i]$表示第$i$位之后的最长一串。

$$f[i]=\max{(f[i+1],r[i]-i)}$$
则最后答案为：
$$Ans=\max{(r[i]-i+f[r[i]])}$$

//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],r[50005],f[50005],ans;
int main(){
    //freopen("diamond.in","r",stdin);
    //freopen("diamond.out","w",stdout);
    n=read(),k=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    sort(a+1,a+n+1);
    for (register int i=1;i<=n;++i)
        {
        r[i]=upper_bound(a+i,a+n+1,a[i]+k)-a;
        if (a[r[i]]-a[i]==k)
           r[i]++;  
        }
    for (register int i=n;i>=1;--i)
        f[i]=max(f[i+1],r[i]-i);
    for (register int i=1;i<=n;++i)
        ans=max(ans,(r[i]-i)+f[r[i]]);
    printf("%d",ans);
    return 0;
}

$2^o$ 反思与总结

一个要注意的点，二分取$r[i]$的时候，如果刚好是$a[i]+k=a[r[i]]$，那就要把$r[i]++$。

本题是一个比较好的小思维题，算法难度不高，但逻辑性很强。

T3 Closing

$1^o$ 分析

看到要维护图的联通性，第一反应并查集。

但我们发现这题是逐渐删边的，但是并查集并没有撤销的操作。

这时我们就考虑将算法离线，倒序算答案，这样并查集维护的就是连边的操作而不是删边。

则最开始是没有点的，按照倒序依次加入点进来，将所有与之相邻的点合并。

然后考虑如何判断当前是否联通。

第一种：

可以暴力枚举每一个当前存在的点，看所有点的$father$是否相同，时间复杂度$O(n^2+m)$，可过。

第二种：

考后$@QaQw$神仙讲了一种$O(m)$的算法。

既你记一个$sum$表示当前连通块的数量，如果当前加入一个点，就把$sum+1$，如果合并了两个集合，就把$sum-1$

这样如果当前$sum=1$，那就说明联通，否则不连通，时间复杂度$O(m)$

//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,m;
int father[3005],q[3005];
struct node{
    int v,nex;
}edge[6005];
int head[3005],ans[3005],len;
inline void make_map(int u,int v)
{
    len++;
    edge[len].nex=head[u];
    edge[len].v=v;
    head[u]=len;
}
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;
}
int main(){
//    freopen("closing.in","r",stdin);
//    freopen("closing.out","w",stdout);
    n=read(),m=read();
    for (register int i=1;i<=m;++i)
        {
        int u=read(),v=read();
        make_map(u,v),make_map(v,u);
        }
    for (register int i=1;i<=n;++i)
        q[i]=read();
    for (register int i=n;i>=1;--i)
        {
        int x=q[i],f1,flag=0;
        father[x]=x;
        f1=Find(x);
        for (register int j=head[x];j;j=edge[j].nex)
            {
            int y=edge[j].v;
            if (!father[y])
               continue;
            int f2=Find(y);
            if (f1!=f2)
               unnion(f1,f2);
            }
        f1=Find(x);
        for (register int j=1;j<=n;++j)
            if (father[j]&&Find(j)!=f1)
               {
               flag=1,ans[i]=0;
               break;
               }
        if (!flag)
           ans[i]=1;
        }
    for (register int i=1;i<=n;++i)
        {
        if (ans[i])
           printf("YES\n");
        else
           printf("NO\n");
        }
    return 0;
}

$2^o$ 反思与总结

注意判断的时候只要判断当前加入了的点。

$@QaQw$神仙的$O(m)$算法其实并不难想，只不过看到数据范围可过大多数人就不想了，我们应该多去思考更优秀的解法，不要仅仅局限于当前的题目。