跳过正文
  1. Posts/

codeforces 560 D. Equivalent Strings(分治)

·1 分钟

问两个长度相同的字符串是否等价.

相等的条件是,两个字符串相等,或者两个偶数长度(因为要分成长度相同的两段,所以一定是偶数长度才可分)字符串平均分成两部分,每部分对应相等(不考虑顺序)

一开始有一点没想清楚.

如果字符串a分成相等长度的两部分a1,a2,字符串b分成相等的两部分b1,b2

我错误得以为,如果a1和a2等价&&b1;和b2等价,那么a 和 b 就相等了(a和b一定等价,但不一定相等),于是只判断了 equal(a1,b2)&&equal;(a2,b1)

wa了一次.

<

 1/*************************************************************************
 2	> File Name: code/cf/#313/D.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com
 5	> Created Time: 2015年08月17日 星期一 08时42分25秒
 6 ************************************************************************/
 7
 8#include<iostream>
 9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=2E5+7;
32string a,b;
33int len;
34
35bool equal( string x,string y,int len)
36{
37  //  cout<<"x:"<<x<<" y:"<<y<<" len:"<<len<<endl;
38    if (x==y) return true;
39    string x1,x2,y1,y2;
40    x1 = x.substr(0,len/2);
41    x2 = x.substr(len/2,len);
42    y1 = y.substr(0,len/2);
43    y2 = y.substr(len/2,len);
44    if (len%2==0&&equal(x1,y2,len/2)&&equal(x2,y1,len/2))
45    {
46	return true;
47    }
48    if (len%2==0&&equal(x1,y1,len/2)&&equal(x2,y2,len/2))
49    {
50	return true;
51    }
52    return false;
53}
54int main()
55{
56    cin>>a;
57    cin>>b;
58    len = a.length();
59    if (equal(a,b,len))
60    {
61	puts("YES");
62    }
63    else
64    {
65	puts("NO");
66    }
67
68	return 0;
69}

相关文章

codeforces 560 B. Gerald is into Art (模拟)

·1 分钟
1/************************************************************************* 2 > File Name: code/cf/#313/B.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: Wed 22 Jul 2015 09:52:54 PM CST 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30 31 int a1,b1,a2,b2,a3,b3; 32bool judge (int x2,int y2,int x3,int y3) 33{ 34 if (x2<=a1&&x3<=a1&&y2+y3<=b1) 35 return true; 36 if (y2<=b1&&y3<=b1&&x2+x3<=a1) 37 return true; 38 return false; 39} 40int main() 41{ 42 cin>>a1>>b1>>a2>>b2>>a3>>b3; 43 if (judge(a2,b2,a3,b3)||judge(b2,a2,a3,b3)||judge(b2,a2,b3,a3)||judge(a2,b2,b3,a3)) 44 { 45 puts("YES"); 46 } 47 else 48 { 49 puts("NO"); 50 } 51 52 return 0; 53}

codeforces 520 A. Pangram (暴力)

·1 分钟
给一个字符串,问这个字符串中是否26个字母都出现过(大小写只出现一个就算出现过) 开个布尔数组,扫一遍即可。 嘛,做两道水题放松下== 反正也是要清的。