Codeforces 494E. Sharti

Description

有一个 \(n*n\) 的矩形,给出 \(m\) 个子矩形,这些矩形内部的点都是白色的,其余的点都是黑色,每一次你可以选择一个变长不超过 \(k\) 的正方形,满足这个正方形的右下角是白色的,并将这个正方形内的颜色取反

两个人轮流操作,不能操作者输,求是否先手必胜

题面

Solution

这是翻硬币游戏的模型,用到结论:局面的 \(SG\) 值等于局面中每个正面朝上的棋子单一存在时的 \(SG\) 值的异或和

这样就可以打一个表找规律

打表发现这个题的 \(SG[i][j]=min(lowbit(i),lowbit(j),maxbit(k))\)

然后就只需要把所有白点的 \(SG[i][j]\) 异或起来看是否为 \(0\) 就好了

可以用扫描线维护,一种直接的做法是考虑每一个二进制为作为 \(lowbit\) 时的贡献

一个二进制位 \(i\) 作为 \(lowbit\) 的特点是:

1.低位不能有 \(1\)

2.\(i\) 这一位为 \(1\)

3.\(i\) 的高位的随便选

因为是求异或和,所以 \(lowbit(i)\) 出现了偶数次的话,贡献就可以抵消了,所以只需要出现偶数次的二进制了

把行列分开考虑,扫描线处理,列用线段树维护,最后再将行和列合并

考虑算出一个区间 \([l,r]\) 的 \(lowbit\) 的异或和

\(i\) 作为 \(lowbit\) 出现的次数是 \(\frac{r}{i}-\frac{l-1}{i}-(\frac{r}{i<<1}-\frac{l-1}{i<<1})\)

后面减去的是 \(i\) 这一位不为 \(1\) 的方案数

最后再将行列合并就行了

依旧是考虑每一位作为 \(lowbit\) 出现的次数,注意合并时是将行的 \(lowbit\) 和列的 \(lowbit\) 取 \(min\)

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

inline int gi(){

	register int str=0;register char ch=getchar();

	while(ch>'9' || ch<'0')ch=getchar();

	while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();

	return str;

}

struct node{

	int x,l,r,d;

	bool operator <(const node &p)const{return x<p.x;}

}e[N];

struct data{

	int ls,rs,w,la,fi;

}tr[N*30];

int n,m,k,K,rt=0,tt=0;

inline int lowbit(int l,int r){

	l--;int ret=0;

	for(int i=1;i<=k;i<<=1)

		ret|=(((r/i-l/i)-(i*2<=k?r/i/2-l/i/2:0))&1)*i;

	return ret;

}

inline void upd(int o){

	if(tr[o].la)tr[o].w=tr[o].fi;

	else tr[o].w=tr[tr[o].ls].w^tr[tr[o].rs].w;

}

inline void Modify(int &o,int l,int r,int sa,int se,int t){

	if(!o)o=++tt,tr[o].fi=lowbit(l,r);

	if(sa<=l && r<=se){tr[o].la+=t;upd(o);return ;}

	int mid=(l+r)>>1;

	if(se<=mid)Modify(tr[o].ls,l,mid,sa,se,t);

	else if(sa>mid)Modify(tr[o].rs,mid+1,r,sa,se,t);

	else Modify(tr[o].ls,l,mid,sa,mid,t),Modify(tr[o].rs,mid+1,r,mid+1,se,t);

	upd(o);

}

int main()

{

	cin>>n>>m>>k;

	for(K=1;K<=k;K<<=1);

	int xl,xr,yl,yr,cnt=0,x,y,sum=0,ans=0;

	for(int i=1;i<=m;i++){

		xl=gi();yl=gi();xr=gi();yr=gi();

		e[++cnt]=(node){xl,yl,yr,1};

		e[++cnt]=(node){xr+1,yl,yr,-1};

	}

	sort(e+1,e+cnt+1);

	for(int i=1;i<=cnt;i++){

		if(e[i].x!=e[i-1].x){

		   x=lowbit(e[i-1].x,e[i].x-1);y=tr[rt].w;

			xl=xr=sum=0;

			for(int j=K;j;j>>=1){

				sum=-xl*xr;xl+=((x&j)>0);xr+=((y&j)>0);sum+=xl*xr;

				if(sum&1)ans^=j;

			}

		}

		Modify(rt,1,n,e[i].l,e[i].r,e[i].d);

	}

	if(ans)puts("Hamed");

	else puts("Malek");

	return 0;

}

巴特西

Codeforces 494E. Sharti

Description

Solution

最新文章

热门文章