题解
一句话总结:使得 \((i,j)\) 内的元素为1,且为所在列的唯一一个1,需要翻转哪些行?
在我看来,用了 随机概率异或哈希
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve()
{
int n,m;
cin>>n>>m;
vector<vector<bool> > table(n+5,vector<bool>(m+5));
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
for(int j=0;j<m;j++)
{
table[i][j+1]=s[j]-'0';
}
}
ll rand1[n+3],rand2[n+3];
for(int i=1;i<=n;i++)
{
rand1[i]=rnd();
rand2[i]=rnd();
}
int ans=0;
map<pair<ll,ll> ,int> state;
pair<int,int> last;
for(int j=1;j<=m;j++)
{
ll sum1=0,sum2=0;
for(int i=1;i<=n;i++)
{
if(table[i][j])//先把所有1翻转
{
sum1^=rand1[i];
sum2^=rand2[i];
}
}
for(int i=1;i<=n;i++)//使得元素(i,j)为1,且为当前列的唯一一个1,需要翻转哪些行
{
sum1^=rand1[i];
sum2^=rand2[i];
state[{sum1,sum2}]++;//状态记录
if(ans<state[{sum1,sum2}])
{
ans=state[{sum1,sum2}];
last={i,j};
}
sum1^=rand1[i];
sum2^=rand2[i];
}
}
cout<<ans<<"\n";
string res(n,'0');
for(int i=1;i<=n;i++)//要使得答案最大的最后一个元素为1,需要翻转哪些行
{
if(i==last.first)
{
if(!table[i][last.second])
{
res[i-1]='1';
}
}
else if(table[i][last.second]) res[i-1]='1';
}
cout<<res<<"\n";
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
标签:int,题解,long,vector,solve,XORificator
From: https://www.cnblogs.com/pure4knowledge/p/18218690