自动搬运

查看原文

来自洛谷，原作者为

	elainya_stars elainya_qwq

搬运于2025-08-24 22:29:17，当前版本为作者最后更新于2025-07-15 10:13:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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