【bzoj4171】Rhl的游戏

Source

bzoj4171

Hint

请先思考后再展开

高斯消元

Solution

请先思考后再展开

首先每个位置按不按是一个bool,然后会有许多异或方程
如果n很小可以直接枚举第一行的状态,但这题不行,那就设未知数
不难发现f(i,j)可以用若干个第一行的未知数的异或表示,直接bitset递推一下
最后就会得到n个未知数,n+k个方程,直接高斯消元
复杂度为 $O(Tn^3/32)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=256+10;
const ll MOD=1e13;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
typedef bitset<MAX_N> bs;
bs f[MAX_N][MAX_N],a[MAX_N*2];
void guass(int n,int m)//n个元,m个方程
{
int cnt=0;
for(int i=n;i>=1;i--)
{
int to=-1;for(int j=cnt+1;j<=m;j++) if(a[j][i]) to=j;
if(to<0) continue;cnt++;
swap(a[to],a[cnt]);
for(int j=1;j<=m;j++) if(j!=cnt and a[j][i]) a[j]^=a[cnt];
}
for(int i=n+1;i<=m;i++) if(a[i]._Find_first()==n+2) {puts("NO");return;}
puts("YES");
}
char str[MAX_N][MAX_N];
void main()
{
int T=qread();
for(int tt=1;tt<=T;tt++)
{
int n=qread(),m=qread(),ss=qread();
for(int i=1;i<=n;i++) scanf("%s",str[i]+1);
for(int j=1;j<=m;j++) f[1][j][j]=1;
for(int i=2;i<=n;i++) for(int j=1;j<=m;j++)
{
f[i][j]=f[i-1][j]^f[i-1][j-1]^f[i-1][j+1]^f[i-2][j];
f[i][j][m+2]=f[i][j][m+2]^(str[i-1][j]=='B');
}
for(int j=1;j<=m;j++)
{
a[j]=f[n][j]^f[n][j-1]^f[n][j+1]^f[n-1][j];
a[j][m+2]=a[j][m+2]^(str[n][j]=='B');
}
for(int i=1;i<=ss;i++)
{
int x=qread(),y=qread();
a[m+i]=f[x][y];
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j].reset();
printf("Case #%d:\n",tt);guass(m,m+ss);
}
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/3b9d.html
转载请注明出处,谢谢!