Codeforces Gym 101173 部分题题解

B.Bipartite Blanket

题目链接

Bipartite Blanket

简要题解

我们发现,一个点集合法,当且仅当存在一组匹配边,使得这组匹配边覆盖了点集中所有的点,注意并不要求恰好覆盖!
既然不要求恰好覆盖,那么我们就可以对左右两边的点分开考虑。
假设我们现在在左边选了一个点集\(A\),那么如果存在一组匹配边覆盖了\(A\),我们就可以把\(A\)作为左边的一个合法点集。
枚举左边的所有点集并作判断,会得到若干合法点集,同理右边会得到若干合法点集。
那么我们在左右两边各取一个合法点集,并起来的点集一定合法,因为将两点集各自的匹配边取并集,就得到了一组覆盖整个点集的匹配边。
我们对两边合法点集对应的点权和排序,维护两个单调指针,就可以快速算出点权和不小于\(t\)的合法点集数量。
这一部分的时间复杂度是\(O(n*2^n)\)的。

现在只剩下一个问题:如何判断一个点集是否合法?
假设我们从左边选了一个点集\(A\),如果找出所有与\(A\)连通的边,就得到了一个子二分图,只要这个子二分图存在完美匹配,那么这个点集就合法。
\(Hall\)定理可以快速判断一个二分图是否存在完美匹配。
我们设二分图两边的点集为\(X,Y\),那么\(Hall\)定理可以写成:
若二分图存在大小为n的完美匹配,则对于\(\forall 1\leq k\leq n\),满足从X中任取k个点,都能直接连向Y中的至少k个点。

点数很小,于是我们可以采用状态压缩。
设\(F[S]\)表示,当左边的点集为\(S\)时,右边与\(S\)直接相连的点集状态。
我们再设\(G[S]\),当状态\(S\)的点数不超过\(F[S]\)的点数时\(G[S]=1\),否则\(G[S]=0\)。
之后对于每一个\(S\),我们枚举\(S\)的子集,只有\(S\)的所有子集对应的\(G\)值为\(1\)时,点集\(S\)才合法。
这个枚举子集的过程,我们可以采用子集\(Dp\)的技巧将时间复杂度优化至\(O(n*2^n)\)。
代码如下:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=(1<<20)+10;
bool Pl[MAXN],Pr[MAXN];
int n,m,Tl,Tr,Lim,Ls,Rs,El[MAXN],Vl[MAXN],Er[MAXN],Vr[MAXN];
int Cnt[MAXN],Gl[MAXN],Gr[MAXN];
ll Ans;
int Lowbit(int K){   return K&(-K);   }
int main()
{   scanf("%d%d",&n,&m),Tl=(1<<n)-1,Tr=(1<<m)-1;
    for(int i=1;i<(1<<20);i++) Cnt[i]=Cnt[i>>1]+(i&1);
    for(int i=0;i<n;i++)
        for(int j=0,C;j<m;j++)
        {   for(C=getchar()-'0';C!=0&&C!=1;) C=getchar()-'0';
            El[1<<i]|=C<<j,Er[1<<j]|=C<<i;
        }
    for(int i=0;i<n;i++) scanf("%d",&Vl[1<<i]);
    for(int i=0;i<m;i++) scanf("%d",&Vr[1<<i]);
    scanf("%d",&Lim);
    for(int i=0,K;i<=Tl;i++)
    {   K=Lowbit(i),El[i]=El[K]|El[i^K],Vl[i]=Vl[K]+Vl[i^K],Pl[i]=Cnt[El[i]]>=Cnt[i];
        for(int j=i;j;j^=K) K=Lowbit(j),Pl[i]&=Pl[i^K];
        if(Pl[i]) Gl[++Ls]=Vl[i];
    }
    for(int i=0,K;i<=Tr;i++)
    {   K=Lowbit(i),Er[i]=Er[K]|Er[i^K],Vr[i]=Vr[K]+Vr[i^K],Pr[i]=Cnt[Er[i]]>=Cnt[i];
        for(int j=i;j;j^=K) K=Lowbit(j),Pr[i]&=Pr[i^K];
        if(Pr[i]) Gr[++Rs]=Vr[i];
    }
    sort(Gl+1,Gl+Ls+1),sort(Gr+1,Gr+Rs+1);
    for(int Le=1,Ri=Rs;Le<=Ls;Le++)
    {   while(Ri>=1&&Gl[Le]+Gr[Ri]>=Lim) Ri--;
        Ans+=Rs-Ri;
    }
    printf("%lld\n",Ans);
}

H.Hangar Hurdles

题目链接

Hangar Hurdles

简要题解

对于每个询问,我们可以理解为,是在特定条件下判断两个点连通性的问题。
那么可以思考一下这个条件是什么,什么情况下,从某个点\(A\)出发,能够走到另一个点\(B\)?
既然我们需要一步步走过去,那么不如先想想,什么情况下,从某个点\(A\)出发,能够走到相邻的点\(C\)?
我们设一个\(F[A]\),表示在\(A\)点能放下的最大正方形的边长。
那么如果当前正方形的边长不超过\(Min(F[A],F[C])\),我们就可以从\(A\)点走到\(C\)点。
假设当前正方形边长为\(L\),那么当存在从\(A\)到\(B\)的一条路径,使得路径上所有点的\(F\)值不小于\(L\)时,就可以从\(A\)点走到\(B\)点。

这是\(Kruskal\)重构树的经典模型。
我们把相邻点之间连一条边,边权设为两点\(F\)的较小值,然后对这个图跑\(Kruskal\)最大生成树,同时建立\(Kruskal\)重构树。
我们维护一个并查集,这个并查集表示的是,在重构树上,当前节点所在树的根,显然这个并查集不影响求最大生成树。
我们按照边权从大到小枚举边,如果当前边的两端点连通,就无视这条边。
否则,我们在重构树上新建一个节点,表示这条边,点权设为边权,并将这个点和两端点所在树的根连边。
最终我们得到了一棵\(Kruskal\)重构树,对于每个询问,答案就是两个点在重构树上的\(LCA\)的点权。
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
char M[1010][1010];
int n,Qs,Dis[1010][1010];
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;
}
int Min(int A,int B){   return A<B?A:B;   }
int Max(int A,int B){   return A>B?A:B;   }
int Id(int H,int L){   return (H-1)*n+L;   }
namespace PRE
{   bool Vis[1010][1010];
    queue<pair<int,int>>Team;
    void Prepare()
    {   for(int i=0;i<=n+1;i++) M[i][0]=M[0][i]=M[i][n+1]=M[n+1][i]='#';
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++)
                if(M[i][j]=='#') Team.push(make_pair(i,j)),Vis[i][j]=1;
                else Dis[i][j]=n;
        for(int Nh,Nl;!Team.empty();)
        {   Nh=Team.front().first,Nl=Team.front().second,Team.pop();
            for(int i=-1;i<=1;i++)
                for(int j=-1,Sh,Sl;j<=1;j++)
                {   Sh=Nh+i,Sl=Nl+j;
                    if(Sh<1||Sh>n||Sl<1||Sl>n) continue ;
                    if(M[Sh][Sl]=='.'&&!Vis[Sh][Sl])
                        Dis[Sh][Sl]=Dis[Nh][Nl]+1,Vis[Sh][Sl]=1,Team.push(make_pair(Sh,Sl));
                }
        }
    }
}using namespace PRE;
namespace Kruskal
{   int Ds,Fa[MAXN*2][22],Bel[MAXN*2],Val[MAXN*2],Deep[MAXN*2];
    vector<pair<int,int>>Edge[1010];
    int Find(int S){   return Bel[S]==S?S:Bel[S]=Find(Bel[S]);   }
    void Rebuild()
    {   for(int i=1;i<=Ds;i++) Bel[i]=i;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {   if(M[i][j]=='.'&&M[i][j-1]=='.') Edge[Min(Dis[i][j],Dis[i][j-1])].push_back(make_pair(Id(i,j),Id(i,j-1)));
                if(M[i][j]=='.'&&M[i-1][j]=='.') Edge[Min(Dis[i][j],Dis[i-1][j])].push_back(make_pair(Id(i,j),Id(i-1,j)));
            }
        for(int i=n;i>=1;i--)
            for(pair<int,int>Np:Edge[i])
            {   int A=Find(Np.first),B=Find(Np.second);
                if(A!=B) Ds++,Bel[A]=Bel[B]=Bel[Ds]=Ds,Val[Ds]=i,Fa[A][0]=Fa[B][0]=Fa[Ds][0]=Ds;
            }
        for(int j=1;j<=21;j++)
            for(int i=1;i<=Ds;i++) Fa[i][j]=Fa[Fa[i][j-1]][j-1];
    }
}using namespace Kruskal;
int Find_Deep(int Np){   return Deep[Np]?Deep[Np]:(Deep[Np]=1+(Fa[Np][0]==Np?0:Find_Deep(Fa[Np][0])));   }
int Get_Lca(int A,int B)
{   if(Find(A)!=Find(B)) return 0;
    if(Deep[A]<Deep[B]) swap(A,B);
    for(int i=0,Dt=Deep[A]-Deep[B];i<=21;i++)
        if(Dt>>i&1) A=Fa[A][i];
    if(A==B) return A;
    for(int i=21;i>=0;i--)
        if(Fa[A][i]!=Fa[B][i]) A=Fa[A][i],B=Fa[B][i];
    return Fa[A][0];
}
int main()
{   n=Read();
    for(int i=1;i<=n;i++) scanf("%s",M[i]+1);
    Qs=Read(),Prepare(),Ds=n*n,Rebuild();
    for(int i=1;i<=Ds;i++) Find_Deep(i);
    for(int i=1,A,B,H1,L1,H2,L2,Lca;i<=Qs;i++)
    {   H1=Read(),L1=Read(),H2=Read(),L2=Read(),A=Id(H1,L1),B=Id(H2,L2);
        Lca=Get_Lca(A,B),printf("%d\n",Lca?2*Val[Lca]-1:0);
    }
}

J.Jazz Journey

题目链接

Jazz Journey

简要题解

这道题实际上是给了很多条边,按顺序构成了一条路径,还给了若干通过边的方法及其代价,询问的是按顺序走完整条路径所需要的最小代价。
通过边有两种方法,一种是单程,另一种是往返,两种方法的差异只会在一个点对内部体现。
容易发现,不同点对之间的代价不会相互影响,因此我们可以对每个点对分别计算通过边的贡献。

假设我们现在只考虑\(A\)和\(B\)之间的边,令从\(A\)到\(B\)的边为0,从\(B\)到\(A\)的边为1,那么路径上相应的边组成了一个01串。
我们通过边的方法,可以认为是消除这个01串的代价。
比如,从\(A\)到\(B\)单程票的代价,可以认为是在01串中消去1个0的代价。
从\(B\)到\(A\)的往返票,可以认为是在01串中消去1个1以及它右边的1个0的代价。
我们现在就是要求,消去这个01串的最小代价。

由于我们的操作很少,因此可以分类讨论哪一种方法更优,然后贪心地尽量选择最优的操作来消除01串。
比如,若从\(A\)到\(B\)的往返票最便宜,我们肯定是对于每一个0,尽量找到它后面的某一个1进行配对,然后一起消掉。
又比如,若从\(A\)到\(B\)的往返票价超过了从\(A\)到\(B\)的单程票价与从\(B\)到\(A\)的单程票价之和,我们肯定不会选择往返票。
具体分类讨论可以自己推导。
为了便于处理点对,本题使用了\(map\),因此时间复杂度为\(O(nlogn)\),理论上时间复杂度最优可达线性。
代码如下:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+10;
const ll Inf=1e18;
char Tk;
int n,m,D,Ds,A[MAXN],Pos0[MAXN],Pos1[MAXN];
ll Dis[MAXN][4];
ll Ans;
vector<bool>Bet[MAXN];
map<ll,int>Map;
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;
}
ll Min(ll A,ll B){   return A<B?A:B;   }
ll Max(ll A,ll B){   return A>B?A:B;   }
int Id(int A,int B){   return Map[A<B?1ll*A*MAXN+B:1ll*B*MAXN+A];   }
int New(int A,int B)
{   ll Id=A<B?1ll*A*MAXN+B:1ll*B*MAXN+A;
    return Map.find(Id)==Map.end()?Map[Id]=++Ds:Map[Id];
}
ll Solve(int Nd)
{   int C0=0,C1=0,C2=0,C3=0,P0=1,P1=1,Cs;
    ll Ret=0,V0=Dis[Nd][0],V1=Dis[Nd][1],V2=Dis[Nd][2],V3=Dis[Nd][3];
    for(int i=0,End=Bet[Nd].size();i<End;i++) Bet[Nd][i]?Pos1[++C1]=i+1:Pos0[++C0]=i+1;
    if(V0+V1<=V2&&V0+V1<=V3) return V0*C0+V1*C1;
    if(V2<V0+V1&&V0+V1<=V3)
    {   while(P0<=C0&&P1<=C1)
            if(Pos0[P0]<Pos1[P1]) Ret+=V2,P0++,P1++;
            else Ret+=V1,P1++;
        return Ret+(C0-P0+1)*V0+(C1-P1+1)*V1;
    }
    if(V3<V0+V1&&V0+V1<=V2)
    {   while(P0<=C0&&P1<=C1)
            if(Pos1[P1]<Pos0[P0]) Ret+=V3,P0++,P1++;
            else Ret+=V0,P0++;
        return Ret+(C0-P0+1)*V0+(C1-P1+1)*V1;
    }
    Cs=Min(C0,C1);
    if(V2<=V3&&V3<V0+V1)
    {   while(P0<=C0&&P1<=C1)
            if(Pos0[P0]<Pos1[P1]) Ret+=V2,P0++,P1++,C2++;
            else P1++;
        return Ret+(Cs-C2)*V3+(C0-Cs)*V0+(C1-Cs)*V1;
    }
    if(V3<V2&&V2<V0+V1)
    {   while(P0<=C0&&P1<=C1)
            if(Pos1[P1]<Pos0[P0]) Ret+=V3,P0++,P1++,C3++;
            else P0++;
        return Ret+(Cs-C3)*V2+(C0-Cs)*V0+(C1-Cs)*V1;
    }
}
int main()
{   n=Read(),D=Read();
    for(int i=1;i<=D;i++) A[i]=Read();
    for(int i=1;i<D;i++) Bet[New(A[i],A[i+1])].push_back(A[i]>A[i+1]);
    for(int i=0;i<=Ds;i++) Dis[i][0]=Dis[i][1]=Dis[i][2]=Dis[i][3]=Inf;
    m=Read();
    for(int i=1,A,B,P;i<=m;i++)
    {   A=Read(),B=Read(),scanf("%c",&Tk),P=Read();
        ll &S=Dis[Id(A,B)][(Tk=='O'?0:2)|(A>B)];
        S=Min(S,P);
    }
    for(int i=1;i<=Ds;i++)
        Dis[i][0]=Min(Dis[i][0],Dis[i][2]),Dis[i][1]=Min(Dis[i][1],Dis[i][3]),Ans+=Solve(i);
    printf("%lld\n",Ans);
}

L.Lost Logic

题目链接

Lost Logic

简要题解

这是一道构造题。
题目给了我们三种合法情况,要求我们给出一个约束方案,使得其他情况全都不合法。
由于约束条件是针对两个变量的,我们自然想知道某两个变量在三种合法情况中所有的组合情况。
因此我们利用状态压缩,将每一个变量在三种合法情况中的值用一个三位01串来表示。
那么对于一个位置来说,就有\(000,001,010,011,100,101,110,111\)八种状态,即我们把变量分成了八类。

如果某个变量的状态是\(000\)或者\(111\),那么它肯定只有唯一取值,因此我们可以给出形如\(x->!x\)的约束条件来满足唯一取值。
对于状态相同的变量,它们的值必须保持一样,因此我们可以任选一个变量,然后将其他变量跟这个变量进行约束,如\(i->j\)和\(!i->!j\)。
对于状态相反的变量,实际上只要从两个状态中各选一个变量进行约束即可,如\(i->!j\)和\(!i->j\)。
那么我们只剩下三种状态没有相互约束了,假设为\(001\),\(010\),\(100\)。
如果这三种状态只出现了一种,那么合法情况只有两个,而题目给出了三个不同的合法情况,因此这个肯定不会发生。
如果这三种状态出现了两种,不加约束的话,两种状态任取0/1,会有四个合法情况,因此我们需要加上一个约束。
如果这三种状态都出现了,那么无解。对于\(001\),\(010\),\(100\)来说,我们会发现,无论如何约束,三种状态全取0都是合法的,那么就有四个合法情况了,不满足题意。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,Ans,Seq[60],Al[510],Ar[510];
vector<int>St[8];
void New(int L,int R){   Ans++,Al[Ans]=L,Ar[Ans]=R;   }
void Special()
{   int Pa=0,Pb=0,Ps=0;
    for(int i=1;i<=3;i++)
    {   if(St[i].empty()) continue ;
        if(Ps==2) puts("-1"),exit(0);
        if(Ps==1) Pb=St[i][0],Ps++;
        if(Ps==0) Pa=St[i][0],Ps++;
    }
    if(Seq[Pa]==1||Seq[Pa]==6) New(Pa*(Seq[Pa]&1?1:-1),Pb*(Seq[Pb]&1?1:-1));
    if(Seq[Pa]==2||Seq[Pa]==5) New(Pa*(Seq[Pa]&2?1:-1),Pb*(Seq[Pb]&2?1:-1));
    if(Seq[Pa]==3||Seq[Pa]==4) New(Pa*(Seq[Pa]&4?1:-1),Pb*(Seq[Pb]&4?1:-1));
}
int main()
{   scanf("%d",&n);
    for(int i=2;i>=0;i--)
        for(int j=1,S;j<=n;j++) scanf("%d",&S),Seq[j]+=S<<i;
    for(int i=1;i<=n;i++) St[Seq[i]].push_back(i);
    for(int i:St[0]) New(i,-i);
    for(int i:St[7]) New(-i,i);
    for(int i=1;i<=6;i++)
        for(int A:St[i]) if(A!=St[i][0]) New(A,St[i][0]),New(St[i][0],A);
    for(int i=4;i<=6;i++)
        for(int A:St[i]) if(!St[7^i].empty()) New(A,-St[7^i][0]),New(-A,St[7^i][0]);
    for(int i=4;i<=6;i++)
        for(int A:St[i]) St[7^i].push_back(A);
    Special(),printf("%d\n",Ans);
    for(int i=1;i<=Ans;i++)
    {   if(Al[i]<0) putchar('!'),Al[i]*=-1;
        printf("x%d -> ",Al[i]);
        if(Ar[i]<0) putchar('!'),Ar[i]*=-1;
        printf("x%d\n",Ar[i]);
    }
}
上一篇:[Gym 102798K] Tree Tweaking


下一篇:Defuse the Bombs Gym - 102822D