Strings CODE

這裡是奉上我的code的小地方～


MP: 就是上一篇的內容
（code: http://codepad.org/JhbPTUVc）


KMP: MP加上一個優化：若 b[ i + 1] 跟 b[f[i] + 1] 相同時，比對b[ i+1]失敗，可跳過 b[ f[i]+1 ]
（code: http://codepad.org/SLlkwDJR）


SA, RA: 這部份跟之前在似曾相似裡的東西一模一樣，但code寫的不清不楚的，所以重寫一份
（code: http://codepad.org/QFHlMA4F）

LCP: 就是包括求h[]以得height[]最後再用ST做出O(nlgn)-O(1)的RMQ
（code: http://codepad.org/7hPyaKjm）

第一次寫完一題字串提：tioj 1306
（code: http://codepad.org/e8ke7V1f）

如果有人可以的話，寫完這提後，希望可以借看一下code，感謝> <

還記得SA數組嘛？

之前在似曾相識的那一提，有很認真的討論過關於SA數組的construction和他的概念等，並在最後面的地方，隱約提到了有關 h 數組的事情，也提到了幾個定理，但並沒有好好的講清楚，在這裡要將他們一一證明。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝要進入主題了～

Longest Common Prefix:（照字面上就是最長的共同前綴，而他確實是這樣的東西）
    
名詞解釋：
i =x j: 兩個後綴前x個字元相同 
sa[i]: 第i名後綴是第幾個後綴
ra[i]: 第i個後綴是第幾名後綴
lcp( i, j ): 第i個後綴與第j個後綴的最長公共前綴
LCP( i, j ): 第i名後綴與第j名後綴的最長公共前綴（照字典序sort後）
h[i]: LCP( rank[i]-1, rank[i] )

------------------------------------------------------------------------------------- 


一。 LCP Lemma:  LCP( i, j ) = min( LCP( i, k ), LCP( k,  j ) ); { i<=k<=j }


proof: 


1. 設 x = min( LCP(i,k), LCP(k,j) ), 則i =x k 且 k =x j, 故LCP(i,j) >= x


2. 設LCP(i,j) > x, 則 i[x+1] = j[x+1].
    因 i < k < j 且 i =x j =x k, 故 i[x+1]<=k[x+1]<=j[x+1].
    因此i[x+1] = k[x+1] = j[x+1], 矛盾!!!!


3. 由1.和2.可知LCP(i,j) = x = min( LCP(i,k), LCP(k,j) ).


-------------------------------------------------------------------------------------


二。 LCP Theorem: LCP( i, j ) = min( LCP( k, k-1 ) ) { k = i+1~j }

proof:


1. j-i == 0 和 j-i == 1 皆成立


2. 若 j-i == m 成立，則LCP( i, j ) = min( LCP( k-1, k ) ) { k = i+1~j }，
    由LCP Lemma -> LCP( i-1, j ) = min( LCP(i-1, i ), LCP( i, j ) )
    -> LCP( i-1, j ) = min( LCP( k-1, k ) ) { k = i~j } -> j-i == m+1成立


-------------------------------------------------------------------------------------


三。LCP Corollary: LCP( i, k ) <= LCP( j, k ) { i <= j <= k }

proof: LCP( i, k ) = min( LCP( i, j ), LCP( j, k ) ) <= LCP( j, k )

-------------------------------------------------------------------------------------

四。h[]數組的特性：h[i] >= h[i-1] - 1

proof:

LCA和RMQ的詳細討論(?!)

又開始學新的東西，突然發現我了解的東西實在很少阿

今天要講的有LCA和RMQ（兩個關係匪淺的好玩有趣酷炫東西）

講完這個希望可以進入新的一個境界，並進入可怕的『字串』

=============================================入正文

LCA有兩種簡單的作法：

第一種：


我最常用的方法，就是用二分搜的方式。先以 O(nlgn) 做出parent[k][u]，代表 u 往上2^k所到達的點，作法的精隨：parent[k+1][u] = parent[k][parent[k][u]]。接著，對於每個詢問O( lgn )，先讓兩個人的深度相同，再慢慢往上移但不要讓兩人的點相同（這個寫(想)法很酷，是iwi想到的，詳情可以看他的『邏輯腦』）。u, v 是所要詢問的兩點（假設兩點以再同一高度，若不同可以用十進位轉二進位的方法如法炮製），最後回傳的為他們的LCA。 

for( int k = MAX ; k >= 0 ; k-- ) if( parent[k][v] != parent[k][u] ) u = parent[k][v], v = parent[k][u];


return parent[0][u]; //最後還要再往上爬一格才行（超酷><）


第二種：

這才是今天的重點，把它壓扁成一條線，做RMQ！想把樹壓成一條線，唯一作法：時間戳記。但今天要的可能出現在從 u 走到 v 之間的任意點，所以在一個點被邊『走到』都要記錄他的時間戳記，因為在他們的時間戳記之間的所有點的 lev 一定<= 他們的LCA。（若有人 > 他們的LCA，則代表 u 必須走超出他們LCA再走下來才會碰到 v，這樣LCA就不是他們的LCA了，矛盾）所以對於每一個詢問，用RMQ求出之間的最小值即為所求。

==============================================進入RMQ

首先，最基本的RMQ大家都熟到炸開了吧？！也就是所謂的線段樹解法，有點太老梗了在此便不多提。我想要說一下Sparse Table（稀疏的桌子）解法，簡稱ST算法。

//////////////////////////////////////////////////////////////////////////

ST算法：O(nlgn) - O(1)，先建立一個表，tbl[x][k]，代表a[i] { i = x ~ x+2^k-1 } 的最小值，而這個算法的精隨為：tbl[x][k] = tbl[x][k-1]+tbl[x+2^(k-1)][k-1] ，簡單精巧又快速的好方法。

/////////////////////////////////////////////////////////////////////////

+-1 RMQ 算法：O(n) - O(1)，概念：塊狀分解（設c個一塊，共n個）

預處理：對n/c塊做ST -> O( (n/c) * lg(n/c) );
                對所有零碎的可能狀況建表 -> O( 2^c*c^2 ); （你知道只會有2^c種，因為相鄰的接只差一）

詢問：用 ST＋已有的零碎 -> O(1)

經過一番計算，可以發現 c = lgn/2時，預處理時間可以壓到O(n)

//////////////////////////////////////////////////////////////////////////

笛卡爾樹：（一個可以把序列轉換成樹的方式）

Definition: 根為此序列的min值，左子樹由min點左邊的序列所構成，右子樹則是右邊的。

Construction:

void 把一個節點放入一顆笛卡爾樹( int a[i], int root_id ){
       if( 其比此樹的根值大) 把一個節點放入一棵笛卡爾樹( a[i],  root_id*2+1 );
       else 把此樹拔掉，已此點取代後，在把被拔掉的樹當成此點的左子樹;
}

Property: 當要找出某區段L~R的RMQ，即為在此樹上二節點LCA的值。
（原因：LCA的性質便是 l 節點在他的左子樹，而 r 節點在他的右子樹（一般特性），且其為一個包含 l 和 r 的區段中的min（笛卡爾樹），故其為l~r區段中的min值。）


//////////////////////////////////////////////////////////////////////////

有了上述的基礎後－

當你碰上了RMQ，你可以先轉為笛卡爾樹求LCA，再轉回+-1RMQ，以 O(n) - O(1) 解決。

講講KMP好了

所謂的KMP，想要解決的問題如下：

給你兩個字串： A 和 B，問B是否為A的子字串？
（長度為 n 和 m）

於是你想到了一個爛作法（他有一個帥氣的名字叫naive啥鬼的）：

枚舉所有在A上的起點，一一比對，看有沒有跟B一樣
時間複雜度：O( (n-m+1)*m )

這裡呢，我要奉上一個超讚的演算法，由罩神Knuth和他的夥伴所創出的KMP算法。

時間複雜度：O( n+m )

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝廢話到這裡結束

先想想在爛作法中的一些智障缺點，你像下圖這樣比對了一段，但在後面發現你們並沒有辦法在這樣繼續下去了，你把下面的B向後移了一格，又要像剛剛那樣再試一次。

但事實上你已經比對過後面的那些了，這時候，如果可以 O(1) 知道要擺在下面四個位置的哪一個（如果可以還是要選第一個），這樣就不用再一次的重新比較剛剛比過的『灰色箭頭部分』。如此便可以很順利的跑過 n 個字母，並順利的以O(n)結束掉。

其實剛剛你想要瞬間知道的就是，對於B字串，以『直線＋兩顆點點』做結尾的所有後綴，哪一個可以和B的前綴完全相合（且合的越多越好）。

所以我們假設以 i 作結尾的後綴，最長可以和以 G[i] 做結尾的前綴相合。

當我們知道G[1]~G[i]，可否推出G[i+1]呢？來討論一下：

假如B[i+1] == B[G[i]+1]，那你就知道，G[i+1] = G[i]+1。

否則：去試B[G[G[i]]+1]，再不行就是B[G[G[G[i]]]+1]，試到ok 或 試到沒得試了（也就是0）

聽完之後，你想想可能會問為什麼不是O(m^2)，但你知道G只會增加一，最多加到m，所以扣也只能扣m，整體來看就是O(m)。（前面的也是相同的情況）

code: http://codepad.org/JhbPTUVc

tioj 1698 Problem H 神殿裡的觸手

這幾題中最簡單的吧！

沒有任何的陷阱跟怪東西

就是一個Kruskal+找bridge

code: http://codepad.org/O6a4XRME

tioj 1697 Problem G 古墨西哥密碼

奸詐的題目，時間卡好緊＝＝


題目特別解析：（普通解析可以看這裡XDD）

1. 找出 2L～2R 的質數表

2. 以1.的bool表建出一個有向圖（如果x then y成立，則由x連到y）

//簡單的部份到這裡為止

3. 這時你想要解的是：
            找出A～B，使得可以在剛剛的有向圖中以<=K條路徑覆蓋A~B所有點


4. 但你只會算『在一個有向圖中最少要幾條簡單路徑覆蓋所有點』
（這裡要使用的技巧是二分圖匹配，而要解決這個問題，只需要把每一個點拆成入點和出點即可且入點和出點無任何關係，以此做最大匹配(x)，所求的答案便是n-x，原因的話是因為沒有被匹配到的點，象徵著簡單路徑的終點（二分圖左半邊）和起點（二分圖右半邊））


5. 所以你便想用枚舉的方式，但發現時間複雜度O(V*V*V*E)，TLE。這時，你發現可以用雙指針，而且可以將他放入二分圖匹配的步驟之中，瞬間將時間複雜度將為O(V*E)。


6. 最重要的一件事！在Bipartite的時候要從G[p].size()-1~0，不能反過來喔，原因應該跟機率有關，不討論了，但極重要，不這樣寫100%TLE。




code: http://codepad.org/a7gksiSK

Cocos2D

@property float value;

其實就是

- (float)value;

- (void)setValue:(float)newValue;

的宣告(?!)

要在.m檔加上@synthesize value

-----------------------------------------------------------------------------------------------

製作MENU:

CCMenuItemImage *OBJECT = [CCMenuItemImage itemWithNormalImage:@"OBJECT.png" //顯示的

  selectedImage:@"OBJECT.png" //操作的

          target: self //放在哪裡?!

  selector:@selector(FUNC:)]; //點了後要做什麼事

CCMenu *MENU = [CCMenu menuWithItems:OBJECT, nil];

 -(void) FUNC:(id)sender{ }

切換Scene:

[[CCDirector sharedDirector]replaceScene:[CCTransitionFlipX transitionWithDuration:1 scene:[SCENE node]]];

移動Sprites:

id Act = XXXXXXX;

id Rac = [Act reverse]; //和Act 恰恰相反

id Seq = [CCSequence actions: Act, Rac, nil ]; //一連串的動作（若一步步執行，會全部黏在一起）

id Spa = [CCSpawn actions: Act, Rac, nil ]; //正統的黏在一起的動作

id Rep = [CCRepeat actionWithAction: Act, times 3];//重複動作

id ReF = [CCRepeatForever actionWithAction: Act];//無限重複

id Eas = [CCEaseInOut actionWithAction: Act, rate 3];//有加速度

[CCJumpBy actionWithDuration:0.2 position:ccp(0,0) height: 200 jumps: 2]//跳躍多少

[CCMoveBy actionWithDuration:0.2 position:ccp(40,20)]//移多少

[CCScaleBy actionWithDuration:0.2 scale:3];//放大多少

ps. 改成To，就會是『變成原來的幾倍』，非『變成現在的幾倍』

//停住他的動作

[miku stopAllActions];

//執行某一動作

[miku runAction:*CCACTION];

-----------------------------------------------------------------------------------------------

製作MAP:

在 .h 檔中

@interface HelloWorldLayer : CCLayer

{

    CCTMXTiledMap *theMap;

    CCTMXLayer *bgLayer;

}

@property (nonatomic, retain) CCTMXTiledMap *theMap;

@property (nonatomic, retain) CCTMXLayer *bgLayer;

在 .m 檔中

-(id) init

{

if( (self=[super init]) ) {

self.theMap = [CCTMXTiledMap tiledMapWithTMXFile:@"bg.tmx"];

        self.bgLayer = [theMap layerNamed:@"BG"];

        

        [self addChild:theMap z:-1]; // z=-1是位在第幾層

}

return self;

}

- (void) dealloc

{

  //將他們的記憶體釋放

    self.theMap = nil;

    self.bgLayer = nil;

    [super dealloc];

}

-----------------------------------------------------------------------------------------------

基本非可操控部分：

iphone: 480 * 320

圖：resources

CCSprite *OBJECT;

在 init 裡頭的 if 裡頭

// 印出OBJECT

OBJECT = [CCSprite spriteWithFile: @"OBJECT.png" ];

OBJECT.position = ccp( X座標, Y座標 );

[self addChild: OBJECT];

// 移動OBJECT（依據測試dt為一固定值）

[self schedule:@selector(FUNC:):];

-(void) FUNC:(ccTime) dt{

miku.position = ccp( miku.position.x+A*dt, miku.position.y+B*dt ); // A, B 是常數

}

ps: 依據我的推設，函式打+是在每次都會做，打-則是要被呼叫。

-----------------------------------------------------------------------------------------------

觸控式部分：

#import "CCTouchDispatcher"

//舊的（不贊成使用）

[[CCTouchDispatcher sharedDispatcher] addTargetedDelegate:self priority:0 swallowsTouches:YES];

//新版（較佳?!）

[[[CCDirector sharedDirector] touchDispatcher] addTargetedDelegate:self priority:0 swallowsTouches:YES];

四種Touch方式：

ccTouchBegan, ccTouchEnded, ccTouchMove, ccTouchCancelled

因為一定要有開始所以一定要加：

-(BOOL)ccTouchBegan:(UITouch *)touch withEvent:(UIEvent *)event{

    return YES;

}

當把手移開時要做什麼勒？：//得到位置

-(void)ccTouchEnded:(UITouch *)touch withEvent:(UIEvent *)event{

  //一開始得到的POS是UIKit的位置，以左上當(0, 0)，但openGL是以左下當(0,0)

    CGPoint POS = [touch locationInView:[touch view]];

    CGPoint CON = [[CCDirector sharedDirector]convertToGL:POS];

}