CF559B Equivalent Strings TJ

文章目录

前言

题目传送门

正解：模拟，递归。

考试的 T4，还是想复杂了 qwq。

这题不要用 STL，容易 TLE \texttt{TLE} TLE！！

---

题意简述

翻译够简了。

对了给一下样例解释的翻译：

第一个样例的第一组测试数据中，对于 a = a a b a a=aaba a=aaba 和 b = a b a a b=abaa b=abaa，可以分成 a 1 = a a , a 2 = b a , b 1 = a b , b 2 = a a a1=aa,a2=ba,b1=ab,b2=aa a1=aa,a2=ba,b1=ab,b2=aa；其中 a 1 a1 a1 和 b 2 b2 b2 全等。对于 a = b a a=ba a=ba 和 b = a b b=ab b=ab，可以分成 a 1 = b , a 2 = a , b 1 = a , b 2 = b a1=b,a2=a,b1=a,b2=b a1=b,a2=a,b1=a,b2=b；其中 a 1 a1 a1 和 b 2 b2 b2 全等， a 2 a2 a2 和 b 1 b1 b1 全等。所以 a a b a aaba aaba 和 a b a a abaa abaa 相似。

第一个样例的第二组测试数据中， a a b b aabb aabb 和 a b a b abab abab 不满足相似。

第一个样例的第一组测试数据中，对于 $a=aaba$ 和 $b=abaa$，可以分成 $a1=aa,a2=ba,b1=ab,b2=aa$；其中 $a1$ 和 $b2$ 全等。对于 $a=ba$ 和 $b=ab$，可以分成 $a1=b,a2=a,b1=a,b2=b$；其中 $a1$ 和 $b2$ 全等，$a2$ 和 $b1$ 全等。所以 $aaba$ 和 $abaa$ 相似。

第一个样例的第二组测试数据中，$aabb$ 和 $abab$ 不满足相似。

---

分析

鉴于数据的特殊性 （简称水），我们可以直接按照题意递归即可。

因为输入的是两个字符串，而每次递归都需要两个新的字符串，而这两个新的字符串都是在以前的字符串上截取一段形成的。所以，我们根本不需要传字符串，只需要传在输入的字符串中截取的部分开始、结束的下标即可。

当然，因为每次判断都要传两个字符串，所以需要有两对参数，这里， l 1 , r 1 l1,r1 l1,r1 代表第一个字符串（从输入的第一个字符串中截取）， l 2 , r 2 l2,r2 l2,r2 代表第二个字符串（从输入的第二个字符串中截取）。

首先，两个不同的判断条件打成两个函数 f1 ⁡ \operatorname{f1} f1 和 f2 ⁡ \operatorname{f2} f2，分别判断奇数和偶数字符串长度的相似判定。

f1 ⁡ \operatorname{f1} f1 的实现是很简单的，只需要逐字判断是否相等即可。

不过需要注意细节，在计算字符串的长度时，不需要 + 1 +1 +1。具体原因：本来计算长度的时候是要 + 1 +1 +1 的，但是因为 l 1 l1 l1 和 l 2 l2 l2 已经提供了字符串开始的地方，所以我们在这两个数的基准上加的数就是从 0 ∼ r 1 − l 1 0\sim r1-l1 0∼r1−l1 共 r 1 − l 1 + 1 r1-l1+1 r1−l1+1 个数字，就不需要 + 1 +1 +1 了。

具体函数如下：

bool f1(int l1,int r1,int l2,int r2){
	int t=r1-l1; //计算需要枚举判断的长度
	for(int i=0;i<=t;i++) if(a[l1+i]!=b[l2+i]) return 0; //不一样直接返回
	return 1; //所有的都一样
}

接着分析较难的递归函数 f2 ⁡ \operatorname{f2} f2。这个函数也是我们在主函数中调用的函数。

首先看传过来的字符串长度是奇数还是偶数。如果是奇数，直接返回 f1 ⁡ \operatorname{f1} f1 的判断就可以了。

如果是偶数，那么就需要判断一分为二之后是否相似。定义两个变量 m i d 1 , m i d 2 mid1,mid2 mid1,mid2 分别表示两个字符串中间的下标，也就是分开的地方（注意这两个变量表示的是分开后前面那个字符串的最后一个元素），接着根据题意模拟即可，因为有两组配对，所以两组都要判断。注意先 && 再 ||。

这个地方容易打错，记得好好检查。

（对了提醒大家一定要记得不要把函数名给打掉了，我就是这么错的 qwq。）

f2 ⁡ \operatorname{f2} f2 的代码如下（别在意多余的空格，因为放一个框框里怕是有点不美观，我格式化了一下代码）：

bool f2(int l1, int r1, int l2, int r2) {
    if ((r1 - l1 + 1) & 1)
        return f1(l1, r1, l2, r2);
    int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
    return f2(l1, mid1, l2, mid2) && f2(mid1 + 1, r1, mid2 + 1, r2) ||
           f2(l1, mid1, mid2 + 1, r2) && f2(mid1 + 1, r1, l2, mid2);
}

最后写好主函数，就可以把这道题切了 qwq。

---

不要做一些不道德的行为，洛谷的管理员会让你挂上牌子/xyx。

C o d e Code Code

//格式化了下代码哈 
#include <bits/stdc++.h>
using namespace std;
char a[200005], b[200005];
int len;
bool f1(int l1, int r1, int l2, int r2) {
    int t = r1 - l1;
    for (int i = 0; i <= t; i++)
        if (a[l1 + i] != b[l2 + i])
            return 0;
    return 1;
}
bool f2(int l1, int r1, int l2, int r2) {
    if ((r1 - l1 + 1) & 1)
        return f1(l1, r1, l2, r2);
    int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
    return f2(l1, mid1, l2, mid2) && f2(mid1 + 1, r1, mid2 + 1, r2) ||
           f2(l1, mid1, mid2 + 1, r2) && f2(mid1 + 1, r1, l2, mid2);
}
int main() {
    scanf("%s %s", a + 1, b + 1);
    len = strlen(b + 1);
    if (f2(1, len, 1, len))
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

---

写在最后

题目不难，细节有点 duliu。大家打代码一定一定要注意细节啊 awa。