这题有很多方法(主要是4x4太水了)
首先,这道题目最重要的点,就是结果不受按的顺序的影响(就是先按后按都行)
方法1:DFS
我们可以依次对每个把手dfs
,
每个把手有两种可能,按或不按
按了做一下处理,再回溯还原现场
复杂度$O(2^{16} \times 14 \times 16)$
AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[5][5],ans=1e9;
vector<pair<int,int> > v,q;
void f(int xi,int yi)
{
for(int i=0;i<4;i++)
{
a[xi][i]^=1;
if(i!=xi) a[i][yi]^=1;
}
}
bool check()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(a[i][j]==0)
return 0;
return 1;
}
void dfs(int x,int y)
{
if(x>=3&&y>=4)
{
if(check())
if(v.empty()||q.size()<v.size())
v=q;
return ;
}
if(y>=4) y=0,x++;
f(x,y);
q.push_back(make_pair(x,y));
dfs(x,y+1);
q.pop_back();
f(x,y);
dfs(x,y+1);
}
int main()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
char c;
cin>>c;
a[i][j]=(c=='+'?0:1);
}
dfs(0,0);
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++)
cout<<v[i].first+1<<' '<<v[i].second+1<<endl;
return 0;
}
方法2:位运算
跟方法1相似,我们可以用一个16位的二进制数枚举出所有可能的方案, $1$ 表示按, $0$ 表示不按
对于每种方案,暴力统计按完是否符合条件,取答案,效率为 $O(2^{16} \times 16 \times 7)$
优化了一点点
AC代码:
#include<bits/stdc++.h>
using namespace std;
int tmp[5][5],a[5][5],ans=1e9;
queue<pair<int,int> > q,qq;
void f(int xi,int yi)
{
q.push(make_pair(xi,yi));
for(int i=0;i<4;i++)
{
tmp[xi][i]^=1;
if(i!=xi) tmp[i][yi]^=1;
}
}
bool check()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(tmp[i][j]==0)
return 0;
return 1;
}
int main()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
char c;
cin>>c;
a[i][j]=(c=='+'?0:1);
}
for(int v=1;v<(1<<16);v++)
{
memcpy(tmp,a,sizeof(tmp));
int cnt=0;
q=qq;
for(int i=0;i<16;i++)
if((v>>i)&1)
f(i/4,i%4),cnt++;
if(check()) ans=min(ans,cnt),qq=q;
}
q=qq;
cout<<ans<<endl;
while(q.size())
cout<<q.front().first+1<<' '<<q.front().second+1<<endl,
q.pop();
return 0;
}
方法3:数学 (瞎猜的,还真就过了)
对于一个把手$(x,y)$,它的把手全部打开之前,有两种情况
一、
全都关着,共有$7$个把手关闭,按了一下$(x,y)$,全部打开
二、
除了$(x,j)$,$j \neq y$和$(i,y)$,$i \neq x$两个把手关闭,其他都开着。
按了一下$(i,j)$,全部打开
由于按其他的把手只会影响偶数个关闭的数量,所以对于一个把手$(x,y)$,从始至终,
只要不按,它管理的$7$个把手里关闭的个数奇偶性不变
我们假设$(x,y)$管理的$7$个把手里有$k$个关闭,
再联系那两种情况,我们可以发现:
若$k$为偶数,不按;若为奇数,按。
则程序效率为$O(16 \times 7)$
老实说,比第一种快多了
AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[5][5],ans;
queue<pair<int,int> > q;
int main()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
char c;
cin>>c;
a[i][j]=(c=='+'?1:0);
}
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
int cnt=-a[i][j];
for(int k=0;k<4;k++)
cnt+=a[k][j]+a[i][k];
if(cnt%2==1)
{
q.push(make_pair(i,j));
ans++;
}
}
cout<<ans<<endl;
while(q.size())
cout<<q.front().first+1<<' '<<q.front().second+1<<endl,
q.pop();
return 0;
}
老傻子%%%
(捕获一只野生lsz)大佬~
accc
啊错错错
某个五年级狂切二次函数的人才是大佬
看来不是我,我5升6
某个五升六狂切二次函数的人才是大佬
二次函数是什么?能吃么?
我今天发现一个五升六狂切圆的人才是大佬