题解：P7376 [COCI 2018/2019 #5] Ispit

· · 题解

P7376 [COCI 2018/2019 #5] Ispit

思路

由于最终要使两行完全相同，则初始状态除了那连续的 k 行之外都得相同。（这个条件在下文被称作“上述条件”）

我们先遍历哪两行符合上述条件，再把每个符合条件的两行的下标都存起来。

对于每对符合上述条件的两行：

由于让其中 k 列重组，而且除了那 k 列之外都两两相等，所以符合题目要求的两行所含字母一定相等。考虑排序，排序后两行一模一样就符合题目要求，直接输出 DA。

其他说明放在注释了。

Code

#include<bits/stdc++.h>
using namespace std;

const int N=505;
int n,k,tp;
string s[N];
struct xy
{
    int x,y; // 存符合“上述条件”的两行的下标
}p[N*N]; // 一定开n^2，因为x和y分别可以是1~n

signed main()
{
    puts("ctj sb");
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
      cin>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++) // 遍历两行
        {
            int l=0,r=n-1; // 双指针两面夹击，找到中间不分别相等的串的长度
            while(l<n && s[i][l]==s[j][l])
              l++; // 相等就下一个
            l--; // 我们要的是最后一个相等的，不是第一个不等的，所以要撤回一个
            while(r>=0 && s[i][r]==s[j][r])
              r--; // 同上，但从右往左
            r++;
            if(r-l-1<=k) // 如果长度比k要小，说明符合“上述条件”，有可能符合题目要求，所以存起来
              p[++tp]={i,j};
        }
    for(int i=1;i<=tp;i++)
    {
        string tx=s[p[i].x];
        string ty=s[p[i].y];
        sort(tx.begin(),tx.end());
        sort(ty.begin(),ty.end()); // 把两行排序
        if(tx==ty)
          return !puts("DA"); // 相等则符合题目要求，直接结束
    }
    return !puts("NE");
}

最坏时间复杂度 O(n^3 \log n)。

给我赞赞qwq