题目链接:
https://codeforces.com/problemset/problem/559/B
分析:
比赛的时候以为是一道比较难的字符串题,用python交了一次递归的做法,结果runtime error了,可能是代码有问题。
后来结束以后看别人的代码,才发现暴力的按照题目的分治递归就能过了。也不是那么难,比赛的时候没有去好好的多试试几次,可惜了。
#include <iostream>
#include <cstdio> //定义输入/输出函数
#include <stack> //STL 堆栈容器
#include <map> //STL 映射容器
#include <vector> //STL 动态数组容器
#include <string> //字符串类
#include <iterator> //STL迭代器
#include <cstdlib> //定义杂项函数及内存分配函数
#include <cstring> //字符串处理ed
#include<algorithm>
#include<queue>
#include<cmath>
#include<ctime>
#include<sstream>
using namespace std;
#define FOR(ITER,BEGIN,END) for(int ITER=BEGIN;ITER<END;ITER++)
#define PER(ITER,TIMES) FOR(ITER,0,TIMES)
#define TIME(TIME_NUMBER) PER(_PETER_MRSCO_ITER_,TIME_NUMBER)
#define ll long long
#define close_stdin ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
bool solve(string a, string b, int len) {
if (a == b)return true;
if (len & 1)return false;
int n = len >> 1;
if (solve(a.substr(0, n), b.substr(n, n), n) && solve(a.substr(n, n), b.substr(0, n), n))return true;
if (solve(a.substr(0, n), b.substr(0, n), n) && solve(a.substr(n, n), b.substr(n, n), n))return true;
return false;
}
int main() {
close_stdin;
cin.tie(0);
cout.tie(0);
string a, b;
cin >> a >> b;
cout << (solve(a, b, a.length()) ? "YES\n" : "NO\n");
}你以为这就是正解?
那我告诉你这样写纯属只是运气
如果这两行换一下,就过不了了 ,这只是纯粹的数据问题而已。
OK,那么幻想过后进入正题吧。
以下是正解:
首先我们看神奇的字符串的判断条件,其实根本上只有一个条件就是判相等,条件二我们可以看成是一个变换操作。
然后条件2的(1)(2) 其实是可以相互转换的, 比如判断aa|bb 和bb|aa 你可以理解成条件2(2) 来判断,
但是你也可以理解成将 串1 交换左右两部分以后 再进行条件 2(1)来判断,所以我们可以得出结论,将一个字符串的前半段和后半段交换以后 不影响他的神奇性。
那么我们进一步理解一下题意,其实就是将各个部分的前后段交换以后,使得两个字符串相等,则是神奇字符串。
以下给出正解代码:
#include <iostream>
#include <cstdio> //定义输入/输出函数
#include <stack> //STL 堆栈容器
#include <map> //STL 映射容器
#include <vector> //STL 动态数组容器
#include <string> //字符串类
#include <iterator> //STL迭代器
#include <cstdlib> //定义杂项函数及内存分配函数
#include <cstring> //字符串处理ed
#include<algorithm>
#include<queue>
#include<cmath>
#include<ctime>
#include<sstream>
using namespace std;
#define FOR(ITER,BEGIN,END) for(int ITER=BEGIN;ITER<END;ITER++)
#define PER(ITER,TIMES) FOR(ITER,0,TIMES)
#define TIME(TIME_NUMBER) PER(_PETER_MRSCO_ITER_,TIME_NUMBER)
#define ll long long
#define close_stdin ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
string solve(string s) {
int n = s.size();
if (n %2==1) { return s; }
else {
string s1 = solve(s.substr(0,n/2));
string s2 = solve(s.substr(n / 2, n / 2));
return min(s1 + s2, s2 + s1);
}
}
int main() {
close_stdin;
string a;
string b;
cin >> a >> b;
string aa = solve(a);
string bb = solve(b);
cout << (aa == bb ? "YES\n" : "NO\n");
}谢谢浏览哈!

京公网安备 11010502036488号