USACO23OPEN-Silver B

题目来源

洛谷： USACO23OPEN-Field Day (B)

SPOJ：USACO23OPEN-Field Day (B)

题解： USACO23OPEN-Field Day (B)

题目描述

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

我们将两个奶牛队伍中，同一位置对应的两头奶牛品种不同的所有位置的个数，定义为的两个奶牛队伍的差异。对于编号的每个奶牛队伍，请计算出和其它所有队伍的差异的最大值。

输入格式

第一行包含两个整数与。

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

输出格式

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

样例

输入数据 1

5 3
GHGGH
GHHHH
HGHHG

输出数据 1

5
3
5

样例1解释

第个和第个队伍的差异为。

第个和第个队伍的差异为。

数据规模与约定

• ,。
• 对于测试点：。
• 对于测试点：所有答案最少为。
• 对于测试点：没有额外条件。

题解（Solution）

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; 
}