Codeforces Round #737 (Div. 2) 部分题题解

D.Ezzat and Grid

题目链接

Ezzat and Grid

简要题解

对于这一题,我们不难想出一个\(O(n^2)\)\(Dp\):设\(F[i]\)表示,使前\(i\)行合法,且留下第\(i\)行的最小代价。
那么转移的话,就是枚举一个合法的\(j\),使得第\(i\)行和能够和第\(j\)行相邻,并将中间的行全部删掉,我们有转移方程:

\[F[i]=Min_j(F[j]+i-j-1) \]

现在考虑优化这个\(Dp\),移项我们可以得到:

\[F[i]-i+1=Min_j(F[j]-j) \]

因此我们只需要对于合法的\(j\),找到最小的\(F[j]-j\)即可。
什么时候合法呢?当第\(i\)行和第\(j\)行的区间有交的时候就合法。
于是不难想到区间取\(Min\)和区间查询操作,我们在第\(i\)行的区间上查询\(F[j]-j\)的最小值,然后用\(F[i]-i\)更新第\(i\)行的区间即可。
这个可以用线段树实现,加上离散化可以解决值域区间过大的问题。
时间复杂度\(O(n*logn)\)
代码如下:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+10;
const int Inf=1e9;
struct SEC{   int Le,Ri;   };
int Lsh[MAXN*2];
int n,m,Ans,Ls,F[MAXN],Lf[MAXN],Have[MAXN];
vector<SEC>Sec[MAXN];
int Read()
{   int a=0,c=1;   char b=getchar();
    while(b!=‘-‘&&(b<‘0‘||b>‘9‘)) b=getchar();
    if(b==‘-‘) c=-1,b=getchar();
    while(b>=‘0‘&&b<=‘9‘) a=a*10+b-48,b=getchar();
    return a*c;
}
namespace TREE
{   struct ELE{   int N,P;   }Mins[MAXN*8],Lan[MAXN*8],Nv;
    bool operator < (ELE A,ELE B){   return A.N<B.N;   }
    ELE Min(ELE A,ELE B){   return A.N<B.N?A:B;   }
    void Push_up(int S){   Mins[S]=Min(Mins[S<<1],Mins[S<<1|1]);   }
    void Push_down(int S)
    {   if(Lan[S].N>=0) return ;
        Mins[S<<1]=Min(Mins[S<<1],Lan[S]),Lan[S<<1]=Min(Lan[S<<1],Lan[S]);
        Mins[S<<1|1]=Min(Mins[S<<1|1],Lan[S]),Lan[S<<1|1]=Min(Lan[S<<1|1],Lan[S]);
        Lan[S].N=0;
    }
    ELE Query(int S,int Le,int Ri,int Al,int Ar,int Mid=0)
    {   if(Al<=Le&&Ri<=Ar) return Mins[S];
        Mid=(Le+Ri)>>1,Push_down(S);
        return Min(Al<=Mid?Query(S<<1,Le,Mid,Al,Ar):(ELE){Inf,0},Mid<Ar?Query(S<<1|1,Mid+1,Ri,Al,Ar):(ELE){Inf,0});
    }
    int Modify(int S,int Le,int Ri,int Al,int Ar,ELE Tv,int Mid=0)
    {   if(Al<=Le&&Ri<=Ar) return Mins[S]=Min(Mins[S],Tv),Lan[S]=Min(Lan[S],Tv),0;
        Mid=(Le+Ri)>>1,Push_down(S);
        if(Al<=Mid) Modify(S<<1,Le,Mid,Al,Ar,Tv);
        if(Mid<Ar) Modify(S<<1|1,Mid+1,Ri,Al,Ar,Tv);
        return Push_up(S),0;
    }
}using namespace TREE;
int main()
{   n=Read(),m=Read();
    for(int i=1,H,L,R;i<=m;i++) H=Read(),L=Read(),R=Read(),Sec[H].push_back((SEC){L,R}),Lsh[++Ls]=L,Lsh[++Ls]=R;
    sort(Lsh+1,Lsh+Ls+1),Ls=unique(Lsh+1,Lsh+Ls+1)-Lsh-1;
    for(int i=1;i<=n;i++)
        for(SEC &Ns:Sec[i]) Ns.Le=lower_bound(Lsh+1,Lsh+Ls+1,Ns.Le)-Lsh,Ns.Ri=lower_bound(Lsh+1,Lsh+Ls+1,Ns.Ri)-Lsh;
    for(int i=1;i<=n;i++)
    {   F[i]=i-1;
        for(SEC Ns:Sec[i])
            if(F[i]>(Nv=Query(1,1,Ls,Ns.Le,Ns.Ri)).N+i-1) F[i]=Nv.N+i-1,Lf[i]=Nv.P;
        for(SEC Ns:Sec[i]) Modify(1,1,Ls,Ns.Le,Ns.Ri,(ELE){F[i]-i,i});
    }
    for(int i=1;i<=n;i++)
        if(F[i]+n-i<F[Ans]+n-Ans) Ans=i;
    for(int i=Ans;i;i=Lf[i]) Have[i]=1;
    printf("%d\n",F[Ans]+n-Ans);
    for(int i=1;i<=n;i++)
        if(!Have[i]) printf("%d ",i);
}

E.Assiut Chess

题目链接

Assiut Chess

简要题解

这是一道构造交互题,要求我们在一个\(8*8\)的棋盘内,控制皇后的移动,在\(130\)步之内使得国王无法移动。
此处提供一种构造思路:
由于棋盘不大,一个很自然的想法就是把这个棋盘扫一遍,慢慢把国王逼到角落里。
既然要遍历整个棋盘,那么不如把皇后放在\((1,1)\),然后慢慢往下挪。
假设皇后在第\(i\)行,国王在皇后下方,皇后想走到\(i+1\)行,把国王继续往下逼,那么当皇后往下走时,国王就不能在第\(i+1\)行。
否则皇后往下走之后,国王可以立刻往上走,走到皇后的上方。

我们发现,如果国王在皇后下方,且国王往下走了一步,那么此时一定满足皇后往下走的条件,皇后就可以直接往下走。
否则,我们需要把国王赶出第\(i+1\)行。
实际上,只要皇后把第\(i\)行全部遍历一遍,并且国王没有往上走,那么国王就一定不在第\(i+1\)行,如果国王往上走了,皇后就得重新遍历这一行。
但是国王往上走的次数是有限的,因为国王一旦往下走,皇后就可以跟着往下走,于是保证了皇后的移动次数。
第一行的时候需要判断一下,因为国王有可能就在第一行。
如果是这种情况的话,国王第一步一定会往下走,只要皇后不跟着往下走就好了。

代码如下:

#include<bits/stdc++.h>
using namespace std;
char Str[30];
int T,Nh,Nl,W,Vs,Col;
int Vis[30];
int main()
{   for(scanf("%d",&T);T;T--)
    {   Nh=1,Nl=1,W=1,Col++,Vs=0;
        printf("%d %d\n",Nh,Nl),fflush(stdout);
        Vs+=Vis[Nl]!=Col,Vis[Nl]=Col,scanf("%s",Str);
        if(strstr(Str,"Done")!=NULL) continue ;
        printf("%d %d\n",Nh,++Nl),fflush(stdout);
        Vs+=Vis[Nl]!=Col,Vis[Nl]=Col;
        while(scanf("%s",Str))
        {   if(strstr(Str,"Done")!=NULL) break ;
            if(strstr(Str,"Up")!=NULL) Col++,Vs=0;
            if(strstr(Str,"Down")!=NULL||Vs==8) Col++,Nh++,Vs=0;
            else Nl+=W,W*=(Nl==1||Nl==8?-1:1);
            printf("%d %d\n",Nh,Nl),fflush(stdout);
            Vs+=Vis[Nl]!=Col,Vis[Nl]=Col;
        }
    }
}

Codeforces Round #737 (Div. 2) 部分题题解

上一篇:剑指 Offer 24. 反转链表


下一篇:Map 与 unordered_map 横向与纵向测试,附带原始数据与测试程序