题目链接:
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"); }
谢谢浏览哈!