题解：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 次）。

代码如下：

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

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