CF1368G Shifting Dominoes

Shifting Dominoes

题目大意

有一个 \(n\times m\) 的棋盘,被 \(1\times 2\) 的骨牌覆盖,保证 \(2|n\times m\)

你可以执行一下操作:

  • 移去一个骨牌。

  • 将其他骨牌沿着其长边进行移动。

  • 你需要保证每张骨牌的最终位置与初始位置至少有一个交点。

只关心两个空位的位置,求有多少种不同的局面。

分析

染色

先观察一下这道题给我们的棋盘,如果我们想要移动一个骨牌,则必须满足骨牌长边方向上有空位,且移动过后,这个空位将会转移,转移到的位置是骨牌移动后空出的那个位置。

如下图:

CF1368G Shifting Dominoes

如图所示,我们能够非常直观的发现,对于骨牌的移动,我们能够很自然的将其转化为空位的移动

观察空位移动的位置,每次移动无非是横纵坐标的其中一个加减 \(2\) ,如果我们把整个棋盘黑白间隔染色,实际上空位只能在同色的格子上移动

对于一块骨牌,它所在的两个格子必定为不同颜色

建图

于是我们可以考虑对于每一个位置向它能够到达的位置建边。

if(i+2<=n&&mtx[i+1][j]==‘U‘&&mtx[i+2][j]==‘D‘) Add(HASH(i,j),HASH(i+2,j));
if(i-2>=1&&mtx[i-1][j]==‘D‘&&mtx[i-2][j]==‘U‘) Add(HASH(i,j),HASH(i-2,j));
if(j+2<=m&&mtx[i][j+1]==‘L‘&&mtx[i][j+2]==‘R‘) Add(HASH(i,j),HASH(i,j+2));
if(j-2>=1&&mtx[i][j-1]==‘R‘&&mtx[i][j-2]==‘L‘) Add(HASH(i,j),HASH(i,j-2));

比较直观的理解这个代码,其实就是根据旁边骨牌的摆放方式进行连边选择。

以第一行为例:

如果当前位置为空位,想向下移动两格,则必须要求下方的骨牌是竖直拜访的,其它同理。

是否存在环

仔细想一想我们建出来的这个图,事实上我们发现每个点的入度最多为 \(1\) ,这不难想象,当有一个点向它连边后,其他点都是不可能象其连边的。

那他是否存在环呢?

先画一个 \(3\times 3\) 的图试一下:

CF1368G Shifting Dominoes

这是最简单的环,而且我们能够迅速发现其不合法,中间被围起来的部分是个奇数大小的块,显然我们是不能对其进行覆盖的。

这给了我们一定的启发,如果不存在环,那所有环围起来的多边形大小一定是奇数,考虑证明这一点。

CF1368G Shifting Dominoes

入图又是一个环,我们据此讨论更一般的情况。

对于这样的多边形,我们有一种叫做 \(Pick\) 公式的东西可以求它的面积:

\[S=I+\frac{B}{2}-1 \]

其中,\(I\)\(B\) 分别表示边界内格子的数量和边界外格子的数量。

我们能够很容易的发现, \(B\) 一定是个偶数,因为它围成了一个多边形,所以上下、左右的格子肯定可以两两相对,并且还可以以此发现 \(B\) 是四的倍数,因此 \(\frac{B}{2}\) 同样为一个偶数。

又因为:

\[I=S-\frac{B}{2}+1 \]

所以 \(I\) 必定是一个奇数。

至此,我们证得了这道题不存在环

扫描线求答案

据上面的分析,我们很容易发现,不同颜色的格子是互不干预的,也就是说分成了两个完全不同的部分。

于是我们可以把不同颜色的格子分开考虑,并分别求出 \(dfn\) 序。

且我们目前获得了两棵树,分别代表两种不同颜色的格子。

则对于两颗树里面的某两颗子树,其出现不同情况的概率,即为两个子树大小的乘积。

我们把这个转化到二维上面去即是一个矩形的面积。

同时,由于子树中可能会出现重复的计算,我们需要考虑到这些情况,所以我们需要 \(dfn\) 序。

构造出的举证左下方的点为 \((dfn[u],dfn[v])\) ,右上角的点为 \((dfn[u]+size[u],dfn[v]+size[v])\)

这样,我们就可以用扫描线求出最终的答案了。

完。

CODE

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;
const int N=6e5+10;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w*=-1; ch=getchar(); }
	while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar();
	return s*w;
}
int n,m,cnt,tot,num,yl,yr,ans,io;
int yy[4*N],length[4*N],cover[4*N];
int vis[N],in[N],id[N],siz[N],dfn[N];
char s[N];
vector<char> mtx[N];
vector<pair<int,int> > P[N];
vector<int> ver[N];
struct ScanLine{
	int x; //x坐标
	int uy,dy; //上边的y坐标与下边的y坐标
	int flag; //出入边
	ScanLine(){}
	ScanLine(int xx,int yy,int yyy,int c):x(xx),uy(yy),dy(yyy),flag(c){}
}line[N];
inline int HASH(int x,int y) { return (x-1)*m+y; }
inline bool cmp(ScanLine &a,ScanLine &b) { return a.x<b.x; }
inline void Add(int x,int y)
{
	ver[x].push_back(y);
	in[y]=1;
}
inline void DFS(int u)
{
	siz[u]=1,dfn[u]=++tot;
	for(register int i=0;i<ver[u].size();i++)
		DFS(ver[u][i]),siz[u]+=siz[ver[u][i]]; 
}
inline void pushup(int l,int r,int rt)
{
    if(cover[rt]) length[rt]=yy[r]-yy[l];
    else if(l+1==r) length[rt]=0;
    else length[rt]=length[ls]+length[rs];
}
inline void update(int yl,int yr,int io,int l,int r,int rt)
{
    if(yl>r||yr<l) return ;
    if(yl<=l&&yr>=r){
        cover[rt] += io,pushup(l,r,rt);
        return ;
    }
    if(l+1==r)return ;
    int m=(l+r)>>1;
    if(yl<=m) update(yl,yr,io,l,m,ls);
    if(yr>m) update(yl,yr,io,m,r,rs);
    pushup(l,r,rt);
}
signed main()
{
	n=read(),m=read();
	for(register int i=0;i<=n+1;i++) mtx[i].resize(m+1);
	for(register int i=1;i<=n;i++){
		scanf("%s",s+1);
		for(register int j=1;j<=m;j++) mtx[i][j]=s[j];
	}
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			if(i+2<=n&&mtx[i+1][j]==‘U‘&&mtx[i+2][j]==‘D‘) Add(HASH(i,j),HASH(i+2,j));
			if(i-2>=1&&mtx[i-1][j]==‘D‘&&mtx[i-2][j]==‘U‘) Add(HASH(i,j),HASH(i-2,j));
			if(j+2<=m&&mtx[i][j+1]==‘L‘&&mtx[i][j+2]==‘R‘) Add(HASH(i,j),HASH(i,j+2));
			if(j-2>=1&&mtx[i][j-1]==‘R‘&&mtx[i][j-2]==‘L‘) Add(HASH(i,j),HASH(i,j-2));
			if(!id[HASH(i,j)]){ //记录骨牌编号 
				id[HASH(i,j)]=++cnt;
				if(mtx[i][j]==‘L‘) id[HASH(i,j+1)]=cnt;
				if(mtx[i][j]==‘U‘) id[HASH(i+1,j)]=cnt; 
			}
			P[id[HASH(i,j)]].push_back(mp(i,j));
		}
	}
	for(register int i=1;i<=n;i++)
		for(register int j=1;j<=m;j++) 
			if(!in[HASH(i,j)]) DFS(HASH(i,j));
	for(register int i=1;i<=cnt;i++){
		int a=P[i][0].first,b=P[i][0].second,c=P[i][1].first,d=P[i][1].second;
		int u=HASH(a,b),v=(HASH(c,d));
		int L1L=dfn[u],R1R=dfn[u]+siz[u]-1;
		int L2L=dfn[v],R2R=dfn[v]+siz[v]-1;
		if((a+b)&1) swap(L1L,L2L),swap(R1R,R2R); //严格分成两种颜色 
		//cout<<L1L<<" "<<L2L<<" "<<R1R+1<<" "<<R2R+1<<endl;	
		line[++num]=ScanLine(L1L,R2R+1,L2L,1);
		yy[num]=L2L;
		line[++num]=ScanLine(R1R+1,R2R+1,L2L,-1);
		yy[num]=R2R+1;
	}
	sort(yy+1,yy+num+1);
	sort(line+1,line+num+1,cmp);
	memset(cover,0,sizeof(cover));
    memset(length,0,sizeof(length));
	int len=unique(yy+1,yy+num+1)-(yy+1); 
	for(register int i=1;i<=num;i++){
		ans+=length[1]*(line[i].x-line[i-1].x);
		//cout<<length[1]<<" "<<ans<<endl;
		yl=lower_bound(yy+1,yy+len+1,line[i].dy)-yy;
		yr=lower_bound(yy+1,yy+len+1,line[i].uy)-yy;
		io=line[i].flag;
		//cout<<yl<<" "<<yr<<" "<<io<<endl;
	  	update(yl,yr,io,1,len,1);
	}
	printf("%lld\n",ans);
	return 0;
}

CF1368G Shifting Dominoes

上一篇:springboot启动过程


下一篇:maven 打依赖包命令