[USACO23JAN] Lights Off G题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了[USACO23JAN] Lights Off G题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

洛谷[USACO23JAN] Lights Off G

题目大意

贝西想要睡觉，但是农场的灯一直开着，影响它睡觉。贝西有两个长度为 $n$ 的 $01$ 字符串，分别表示 $n$ 盏灯的序列和开关的序列。其中，表示灯的序列， $0$ 表示关灯， $1$ 表示开灯；表示开关的序列， $1$ 表示可操控的， $0$ 表示不可操控。

一次操作由下面几个步骤组成：

将一个开关的状态变换，即由可操控变成不可操控；或者不可操控变成可操控
对每一个可操控的开关，按下开关，对应的灯的状态将发生变换，开变成关，关变成开
将开关循环移位，即开始的开关是 $s_0s_1\dots s_{n-1}$ ，循环移位后变成 $s_{n-1}s_0\dots s_{n-2}$

求最小的操作次数，使得所有的灯都关掉。

有 $t$ 组数据。

$1\leq t\leq 2\times 10^5,2\leq n\leq 20$

题解

设灯的 $01$ 串为 $a$ ,开关的 $01$ 串为 $b$ 。

首先，操作次数不会超过 $3 n$ 。先用最多 $n$ 次来将所有开关全部关闭，然后每连续两次，分别打开、关闭开关来把某个灯关掉。

因为操作一是需要设定的，而操作二和操作三是一定的，所以可以将两者分开处理。

对于操作二和操作三，就是 $a=a\oplus b$ ，然后将 $b$ 循环移位，再进行 $a=a\oplus b$ ，进行的次数与操作次数一致。

对于操作一，设 $f_{i,j}$ 表示前 $i$ 次是否能达到状态 $j$ ，那么 $f_{i,j}$ 可以由 $f_{i-1,j\oplus x}$ 转移得到，其中 $x$ 可取所有长度为 $i$ 的连续段。

这样做的话，总时间复杂度为 $O(n^2\cdot 2^n+nT)$ 。但因为常数较大，所以我们还需要进一步优化。

如果两个状态 $x, y$ 可以用过循环移动得到，那么显然 $f_{i,x}=f_{i,y}$ ，所以可以用最小的 $j$ 作为所有能通过循环移动得到 $j$ 的元素的代表 $v_j$ 。这样的话，能通过循环移动得到的 $j$ 只需计算一次。那么，固定 $x$ 移动 $j$ ，即可处理 $j$ 经过各个 $x$ 来更新 $f_{i,j}$ 的情况。

总时间复杂度为 $O(n\cdot 2^n+nT)$ 。文章来源地址https://www.toymoban.com/news/detail-537212.html

code

#include<bits/stdc++.h>
using namespace std;
int qt,n,v1,v2,v[1<<21];
bool f[65][1<<21];
char s[105],t[105];
int tn(int x){
	return (x>>1)|((x&1)<<n-1);
}
int gt(int x,int y){
	if(x==0) return 0;
	for(int i=1;i<=3*n;i++,y=tn(y)){
		x^=y;
		if(f[i][v[x]]) return i;
	}
}
int main()
{
	scanf("%d%d",&qt,&n);
	memset(v,-1,sizeof(v));
	for(int i=0;i<1<<n;i++){
		int p=i;
		while(v[p]==-1){
			v[p]=i;p=tn(p);
		}
	}
	f[0][0]=1;
	for(int i=1,x=0;i<=3*n;i++){
		x^=1<<(i-1)%n;
		for(int j=0;j<1<<n;j++){
			f[i][v[j]]|=f[i-1][v[j^x]];
		}
	}
	while(qt--){
		scanf("%s%s",s+1,t+1);
		v1=v2=0;
		for(int i=1;i<=n;i++){
			v1=v1<<1|(s[i]-'0');
			v2=v2<<1|(t[i]-'0');
		}
		printf("%d\n",gt(v1,v2));
	}
	return 0;
}