[Codeforces][559B][560D] B. Equivalent Strings

原題：http://codeforces.com/problemset/problem/559/B
AC：http://codeforces.com/contest/559/submission/12532597

解題方向：模擬


題目大意：給你兩個等長的字串，定義兩字串$A,B$等價，是滿足下其中之一的條件：

1. $A = B$
2. 若能將A分成等長的字串$A1,A2$，也把B分成$B1,B2$，則滿足其中之一：

• $A1$等價$B1$，且$A2$等價$B2$
• $A1$等價$B2$，且$A2$等價$B1$

判定給定字串是否等價。
註 第二點的分割方法是指 $A=A1A2,B=B1B2$

解法：

感覺複雜度不大對，但是暴力做會AC，而且滿快的$(45ms)$，頗奇妙。
分析複雜度 $T(N) = 4T(\frac{N}{2})+2n$，主導者定理得到複雜度$O(N^2)$，但是大小$200000$還是過了，得找點資料研究下哪裡有問題。

#include<bits/stdc++.h>
using namespace std;

char A[200001];
char B[200001];
int L;

bool check(const char *a,const char *b,int len)
{
    if( strncmp(a,b,len) == 0 ) return true;
    if( len%2 == 1 )return false;
    len/=2;
    return check(a,b+len,len)&&check(a+len,b,len)||
           check(a,b,len)&&check(a+len,b+len,len);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>A>>B;
    L = strlen(A);
    cout<< (check(A,B,L)?"YES":"NO") <<'\n';
}

PS. 如果設定正確的話應該會出現在FB上

[Codeforces][559A][560C] A. Gerald's Hexagon

原題：http://codeforces.com/contest/559/problem/A
AC：http://codeforces.com/contest/559/submission/12473071

解題方向：數學


題目大意：有一個六邊形，皆為整數，且內角皆為$120^{\circ}$，問這圖形需要幾個邊長為$1$的正三角形組成 (一定給合法數值)。

解法：

對於旁邊的平行四邊形是$2$倍的邊長乘積，中間空下的正三角形邊長$P= \left |A-D  \right | = \left |B-E  \right | = \left |C-F \right | $ 就隨便選一個，所需要的三角形個數為$P^2$，全部加起來就好了。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int A,B,C,D,E,F;
    cin>>A>>B>>C>>D>>E>>F;
    cout<< 2*(A*B+C*D+E*F) + (A-D)*(A-D) <<'\n';
}

PS. 我覺得我好友的AC Code有夠醜 = =

[Codeforces][560B] B. Gerald is into Art

原題：http://codeforces.com/contest/560/problem/B
 AC：http://codeforces.com/contest/560/submission/12460603

解題方向：模擬

因為論壇壞了，把Code搬來這裡。

題目大意：有一個大矩形，問裡面能不能放入另外兩個矩形 (不能重疊，只考慮水平與垂直翻轉)

解法：可發現若兩矩形邊長為$A \times B$、$C \times D$，那最小包覆矩形至少要$(A+C,min(B,D))$，自己把ABCD排列組合一下，有任何一種狀況能滿足就可以了。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a[2],b[2],c[2];
    cin>>c[0]>>c[1];
    cin>>a[0]>>a[1]
       >>b[0]>>b[1];
    bool flag = false;
    for(int k=0;k<=1;++k)
        for(int i=0;i<=1;++i)
            for(int j=0;j<=1;++j)
                if( a[0^i]+b[0^j] <=c[0^k] && max(a[1^i],b[1^j]) <= c[1^k] )
                    flag = true;
    cout<< (flag?"YES":"NO") << '\n';
}