[MemSQL Start[c]UP 3.0 - Round 1][Codeforces 859]E. Desk Disorder
[2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest][Codeforces 883 F]Lost in Transliteration

[2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest][Codeforces 883 E]Field of Wonders

Zarxdy34 posted @ 2017年10月23日 08:50 in Codeforces with tags 字符串 , 100 阅读

    题意:给出长度均为n的的由小写字符构成的m个已知字符串和一个部分未知的字符串S(未知部分用'*'表示),S是m个已知字符串的其中一个,且S中的同一字母要么全部出现要么全部未知,问有多少个字母一定出现在S中(不包括S中已经出现的)。

    题解:首先判断m个已知字符串中有多少个必定不为S(S中出现字母的位置和已知字符串不完全相同),然后对剩下的字符串中每个字母的数量取最小值,大于0则该字母一定出现。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;

char readchar() {char ch;while (((ch=getchar())<'a' || ch>'z') && ch!='*');return ch;}

vector<int> A[maxn][26];
bool valid[maxn];
int v[26];
int n,m;
int ans;

bool Check(int x)
{
	for (int i=0;i<26;i++) if (A[0][i].size()>0)
	{
		if (A[0][i].size()!=A[x][i].size()) return false;
		for (int j=0;j<(int)A[0][i].size();j++) if (A[0][i][j]!=A[x][i][j]) return false;
	}
	return true;
}

int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		char ch=readchar();
		if (ch!='*') A[0][ch-'a'].push_back(i);
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	for (int j=0;j<n;j++)
	{
		char ch=readchar();
		A[i][ch-'a'].push_back(j);
	}
	for (int i=1;i<=m;i++) valid[i]=Check(i);
	for (int i=0;i<26;i++) if (A[0][i].size()==0) v[i]=1;
	for (int i=1;i<=m;i++) if (valid[i])
		for (int j=0;j<26;j++) v[j]=min(v[j],(int)A[i][j].size());
	for (int i=0;i<26;i++) ans+=v[i];
	printf("%d\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Back to Top