hdu-6282 String Transformation--補題 找規律

題意：給出兩個隻有a,b,c組成的字元串，可以通過删除或者是增加aa,bb,abab改變字元串，問能不能從第一個字元串變成第二個字元串。

條件：1 字元串隻有a,b,c組成

            2 通過删除或者是增加aa,bb,abab改變字元串

            3 樣例：ab->aababb->babb->ba啟示，在沒有c的情況下ab的位置是沒有關系，那麼就隻用考慮ab的奇偶個數關系，以每個c為分界點。

思路：以每個c為分界點，考慮每個分成的集合裡面ab的奇偶關系，對比兩個字元串就好了。比較奇偶的時候可以通過位運算來計算：a^0=a ,a^a=0，b^a^a=b，這樣就可以求出每一段剩餘的。

代碼：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=10000;
int l[2][maxn+5];
int transform_s(int x,string s)
{
    int sum=0,num=0;
    for(int i=0;i<=s.size();i++)
    {
        if(i==s.size()||s[i]=='c')
        {
            l[x][num++]=sum;
            sum=0;
        }
        else
            sum^=s[i];
    }
    return num;
}
int main()
{
    string a,b;
    while(cin>>a>>b)
    {
        memset(l,0,sizeof(l));
        int numa=transform_s(0,a);
        int numb=transform_s(1,b);
        int flag=0;
        int i;
        for(i=0;i<numa&&i<numb;i++)
        {
            if(l[0][i]!=l[1][i])
            {
                flag=1;
                break;
            }
        }
        if(numa!=numb)
            flag=1;
        if(flag==1)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}
           

總結：1 當時有種畏難情緒，最近組隊訓練感覺貢獻太少了有點失落