题解：CF2093F Hackers and Neural Networks

可以通过几个结论推出做法。

1.对于目标字符串数组

a [n]

，只有所有

a [i]

都能在下面至少一个对应的位置

b[i]

找到，才有答案~~（那不然怎么拼好串）~~。

那要是没答案，就输出

-1

就好了。

2.现在就是有答案的情况了：

我们不关心具体怎么拼出这个串，我们只要求最小次数。

在已有一个部分匹配的串的基础上：

如果进行操作

2

擦除再操作

1

加入，很显然要

2

次才可以纠正一个位置的字符串，所以我们要尽可能让这个部分匹配的串尽可能多匹配一些（初始匹配只要一次）。

具体实现也很简单，只需要遍历找出和

a

重合度最高的那个

b

即可。

答案初始为

ans = 0

。

把

b

加进来则

ans = ans + n

。

现在

ans = n

。

后续修改，由于已经除去了不成立的情况，剩下一定可以找到一个

b

满足条件，则只需要加

ans

即可。

容易知道，每有一个不同的字符串

ans = ans + 2

（修改计

2

次）。

代码如下：

CPP

#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 505
using namespace std;
int n,m;
int cnt[INF];
bool vis[INF];
void solve()
{
	scanf("%d%d",&n,&m);
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	string strtar[INF];
	string str[INF][INF];
	for(int i=1;i<=n;i++)
	{
		cin>>strtar[i];
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>str[i][j];
			if(str[i][j]==strtar[j])
			{
				vis[j]=1;
				cnt[i]++;
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	sum+=vis[i];
	if(sum<n)
	{
		puts("-1");
		return;
	}
	
	int maxn=-1;
	for(int i=1;i<=m;i++)
	maxn=max(maxn,cnt[i]);
	
	int ans=n+(n-maxn)*2;
	printf("%d\n",ans);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}

（第一次写没加句号被打回了，审核大人辛苦了）。

题解：CF2093F Hackers and Neural Networks

文章操作

相关推荐

评论

题解：CF2093F Hackers and Neural Networks