USACO23OPEN-Silver B

题目来源

洛谷： USACO23OPEN-Field Day (B)

SPOJ：USACO23OPEN-Field Day (B)

题解： USACO23OPEN-Field Day (B)

题目描述

$\qquad$$Farmer\ John$ 的 $N$ 个牛棚都会选出包含 $C$ 只奶牛的队伍去参加户外聚会。所有奶牛的品种都只可能是根西牛（G）或荷斯坦奶牛（H）。

$\qquad$我们将两个奶牛队伍中，同一位置对应的两头奶牛品种不同的所有位置 $i\ (1 \le i \le C)$ 的个数，定义为的两个奶牛队伍的差异。对于编号 $1\dots N$ 的每个奶牛队伍 $t$，请计算出 $t$ 和其它所有队伍的差异的最大值。

输入格式

$\qquad$第一行包含两个整数 $C$ 与 $N$。

$\qquad$接下来 $N$ 行，每行有一个长度为 $C$ 的，仅包含字母 G 和 H 的字符串，每行对应一支奶牛队伍。

输出格式

$\qquad$对于每个队伍，输出差异最大值。

样例

输入数据 1

5 3
GHGGH
GHHHH
HGHHG

输出数据 1

5
3
5

样例1解释

$\qquad$第 $1$ 个和第 $3$ 个队伍的差异为 $5$。

$\qquad$第 $2$ 个和第 $3$ 个队伍的差异为 $3$。

数据规模与约定

• $2 \leq N \leq 10^5$,$1 \leq C \leq 18$。
• 对于测试点 $2～5$：$C=10$。
• 对于测试点 $6～9$：所有答案最少为 $C-3$。
• 对于测试点 $10～20$：没有额外条件。

题解（Solution）

$\qquad$ USACO23OPEN] Field Day S - 题解

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i<=r;i--)
using namespace std;
inline int input(){int x;return cin>>x,x;}
const int N = 101234;
const int C = 24;
int c,n,a[N],f[(1<<18)+100];
char s[C];
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("b");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	memset(f,0x3f,sizeof(f));
	cin>>c>>n;For(i,1,n){
		cin>>(s+1);int sum=0;
		For(j,1,c) sum=(sum<<1)+(s[j]=='G');
		f[sum]=0;a[i]=sum;
	}For(i,1,c) For(j,0,(1<<c)-1) f[j^(1<<i-1)]=min(f[j^(1<<i-1)],f[j]+1);
	For(i,1,n) cout<<(c-f[(1<<c)-1-a[i]])<<'\n'; 
	return 0; 
}