課程總結 第六周

識訓：
尼姆博奕：看了好多博客，開始還是比較容易理解，深層面的較難看懂，尤其是尼姆博奕的變型，還有后面涉及SG打表那一塊，總結一下自己的認識,簡單的跳過，
先看奇異局勢，（s[1],s[2],s[3]…… s[n]）,逐步進行異或運算，
若結果為0：那么先手必敗；若不為0，那么先手必勝，(也就是說面對奇異局勢的人必輸）

階梯博弈演算法（尼姆博弈進階）：啃了兩三天，頭都暈了，證明程序也看的迷迷糊糊，
題目形式：一個樓梯上每層都放有一些石子（硬幣也可），每回合將i臺階上石子移動到（i-1）階上，最后無法移動的輸，也就是其他階都為空，移動第一階得人贏，
公式：所有的奇數階上的石子進行異或運算>0,則確定是勝方，因為對于敗方來說，若移動奇數階的石子，勝方便有可將奇數階石子異或為0，成為奇異局勢；若移動偶數階石子，勝方可將敗方移動的石子往前移動，對奇數階石子無影響，

到這里還好，可根據階梯博弈變化的題目真的很難，看都看不明白，會繼續認真看的，
舉一個階梯博弈變化的題目，一個盒子從1到n被標記，滿足：
（A>B&&(A+B)%2==1&&(A+B)%3==0）,不能移動盒子的人輸，
我的思路：想到了階梯博弈，可還是不會用，發現條件可轉化為(A+B)%6==3,然后舉例了1到15數字的移動情況，不難發現最終都會移動到（1,3,4）這個盒子中，經查閱資料：發現要對所有奇數步盒子的禮品數進行異或運算，而所有滿足奇數步盒子都滿足*(A+B)%6==0或2或5*，這一步簡直太難想了！！

威佐夫博弈：核心公式：（1.0+sqrt(5.0)）/2*(a-b) 大體是兩堆石頭，要么從一堆中取任意數，要么從兩堆中取相同數目，先去玩的獲勝，這里的奇異局勢和尼姆博弈的很像，但沒有尼姆博弈難，畢竟尼姆博弈是從n堆石頭中取，
需要注意的點：
1.從一堆中取可能可以得到奇異局勢，2.從兩堆中取一樣的石頭也可能得到奇異局勢，要根據題目要求靈活改變，

k倍動態減法：這個同樣非常難，看了好久都還是很懵，也能看做是斐波那契博弈的變型，只是不再是兩倍了，當k=1時，2的i次方都是必敗點，將n化為用二進制，每次拿走最后的一個1，而對手不能拿走倒數第二個1，因為他拿的數量不能多于你拿的；當k=2時，斐波那契數列都是必敗點；當k>=3時，開兩個陣列a[n],b[n],a[n]存的數字都是必敗點，b[t]是a[1到t]所能表示的最大數，最后要使得

b[i]=b[t]+a[i] （a[t]*k<a[i]）

具體實作代碼：（還沒完全理解），目前還是先記住再說，適用性廣

while(n>a[i])
        {
            i++;
            a[i]=b[i-1]+1;
            while(a[j+1]*k<a[i])
                j++;
            if(k*a[j]<a[i])
                b[i]=b[j]+a[i];
            else
                b[i]=a[i];
        }

記憶化搜索：看了很多資料，感徑訓是難在理解遞回式狀態轉移方程那里，
1.概念其實很好理解，搜索程序中，避免重復計算，記錄一些狀態的答案，在接下來狀態中可以直接使用，2.記憶化搜索只是類似于動態規劃，不是屬于，具體是倒著的遞推式動態規劃，

題G:

Y題識訓：題意省略
1.開一個二維陣列，如果要對其中某一行進行初始化memset(dp[1],0,sizeof(dp[1]));這個代碼是可以實作的，但要注意：只能初始化為0，若初始化為1或其他數，會出現亂碼，
2.然后就是我的思路：首先確定要定義一個二維陣列dp[i][j],想到用i來控制最大值為多少的方案數案數，j來表示具體取得末尾的數字，記錄的是方案數，當i等于k時，表示最大數字為k，再從1到n遍歷所有方案數累加
大致思路沒問題，有些細節沒想到：1.如何控制取得的數，由于題目中后一個數字要整除前一個數字，于是又要加一重回圈來控制乘的跨度（1,2,3…），問題看似處在代碼實作上，其實還是思路沒想好，
3.就是取模要及時，每次累加都要，一個注意點，

F題識訓：給定一個字母矩陣，規定可替換的字母，要求所有字母一樣的最大子矩陣的面積，（花了一個上午，弄得我心累的一題）
首先是題意：和我理解的有偏差，我并沒從題目看出求面積的意思，我認為只要求出最大子矩陣相同字母的個數即可，----->>>方向上就錯了，雖然自己也不太會做，
我的思路：雖然自己沒思路，但也想了好久，我發現，替換的情況有很多，肯定是分類討論，也想到了將字母全變成a或b或c，全變成a去找最大子矩陣（b，c同理），到這里是對的，然后我想直接去找字母見得關系，比如最大子矩陣a，如果左邊或上邊是a累加1，其實行不通，這只是在記錄a的次數而已，
查了題解后,題解都看了好久才懂，很多困擾的難點都有了解釋，
1.為了方便記錄，用數字代替字母，出現a則標記為1；然后先只考慮縱向上a出現的次數，若a上方也是a，累加1，

2.更妙的是他計算面積的方式，因為在步驟1中考慮了縱向，接下來考慮橫向就好，dp[i][j]是第i行第j個字母，所表示的值便是這個子矩陣的高，以它為中心，然后向右取比它大的，向左取比它大的，得到最大寬，計算面積取最大，是之前沒見過的查找方式！！！（關鍵是另外開兩個陣列）

 for(int j=1;j<=n;j++)
       {
           while(dp[i][j]<=dp[i][l[j]-1])
            l[j]=l[l[j]-1];
       }
       for(int j=n;j>=1;j--)
       {
           while(dp[i][j]<=dp[i][r[j]+1])
            r[j]=r[r[j]+1];
       }

L - Sonya and Problem Wihtout a Legend 識訓：
本題用了離散化和一些數學知識，看完資料后，才懂了一點，慢慢用到了高數知識和結論了，題意：要求用最少的步數構造一個嚴格的上升陣列，
數學結論：如果是上升陣列，肯定滿足 (a[j]-a[i])>=(j-i),所以便得到 (a[j]-j)>=(a[i]-i),所以用陣列b[n]存盤（a[i]-i）的值，并進行排序，abs（a[i]-b[j]）為正在處理第i位時以b[j]為基準最小花費步數，而dp[i][j]為處理到第i位時以b[j]為基準總體上最小花費步數，是需要加上 上一步同樣以b[j]為基準總體上最小花費步數，和同樣處理到第i位時以b[j-1]為基準最小花費進行比較取最小，
構造狀態轉移方程：dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(b[j]-a[i]));

4.14訓練賽：
1.我負責的那道題沒有過，因為忽略了一種情況，一直卡住，所以比別人少做一道題，很自責，加油吧！！！
思路：大致都是對的，兩端的樹就往兩邊倒，中間的樹減去相應距離或加上相應距離不和兩端的樹相交，然后累加，之所以沒過：非要用ans去記錄才差值想著方便一點，結果把自己搞暈了，因為ans的值需要不斷更新，
2.D題我的思路是找規律，規律已經快出來了，但還需要時間，隊友直接模擬，我覺得也很好，卡住我們的難點：要過菜品個數進行排序（保證剩余的的菜品先進行配對，這樣才能保證最多，參考樣例：2 3 2），
3.A題我們思路是完全正確的，但是代碼實作上有問題，就被擱置了，沒想到別人都過了，特別虧，其實代碼實作也很簡單，一個數找0和8，2個數兩重回圈列舉遍歷，三位數類似，
教訓：
1.有些問題是自己想得復雜，不是題目復雜，可能和心態有關，心態要放平，
2.如果確定思路正確，就不要輕易的放棄代碼實作，代碼是可以慢慢調的，
3.我負責那題就是我把問題復雜化，定義了一個ans記錄位置

4.15訓練賽：
1.一個代碼實作出現了問題，整個隊浪費了將近40多分鐘，忽略了一個問題，如果這個‘1’是在最后出現的，那么沒有一個‘0’去累加這組1的長度，難受了！

**4.16訓練賽：**主要兩個差距，前半段一直是領先的，后面心態問題特別著急，導致一個簡單題目沒做出來：另一個是H題，沒寫出來，和其他組的差距，要努力追趕并超越！！！
H題：
兩方面原因：1.看題不仔細，看的有點快，沒發現輸入一欄中的條件
1<=b[i]<=2n，2.還有就是代碼實作，沒法將思路很好的轉化，識訓到一個沒想到的代碼實作形式，

for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            m[a[i]]=1;    //將出現的元素標記！！
        }
        int temp;
        for(int i=1;i<=n;i++)
        {
            b[i*2-1]=a[i];      //若一個陣列是另外一個陣列的兩倍，可根據特征記錄）
            temp=a[i];
            while(m[temp]==1)
            {
                temp++;
            }
     （后面代碼就很平常，省略）

技巧，注意點：
1.除要用double，
2.異或運算
1.異或的一個運算規律： A^B=C --->>> C^B=A;
2.‘^’ 的優先級小于 '> , <'，注意加 '( )'

賽后補題：（不放代碼，主要是思路，錯誤的點和識訓）
一.C. Divisibility by Eight
思路：是完全正確的，能被8整除的數：1000+b；只要保證b能被8整除即可，分別遍歷1位數，2位數，3位數.（采用回圈方式，暴力做即可）
錯誤的點：個位如果取了這個數字，十位數是從這個數字前開始取，百位也是從十位取得數之前取，
識訓：（整理一下數字特征）
能被2整除的數：奇，偶取模于2即可，
能被3整除的數：各個位上數之和能被三整除，
能被4整除：最末兩位數字能被4整除即可，
能被5整除：末位為0或5.
能被6整除：同時能被2和3整除的條件，即是偶數，且各個位數之和能被3整除，“12”同理，
能被7整除：abc def ghi jkl，滿足（jkl-ghi+def-abc）能被7整除，“13”同理，
能被8整除：最后三位數字能被8整除，
能被9整除：各個數字之和能被能被9整除，
能被10整除：末位為0，
可被11整除：（奇位數字和-偶位數字和）能被11整除，

二：B. Balanced Array（水題跳過，過了一遍代碼，當時敲的時候思路不清，整理一下）

三…A. Candies(水題，唯一要注意的點）
識訓：pow（）函式的計算方式存在誤差
---->>>處理方式：加上一條常變數const int eps=1e-6; （放主函式外面），不然就用double

四:C. Alternating Subsequence
我的思路：
1.首先要保證取得子段最長，將觀察發現，如果第一個元素是正，那么最長的便是“+-+-+-+-”這種形式；如果第一個元素是負，那么最長的便是“-+-+-+-+-+”這種，
2.之后兩種實作方式，第二種更巧妙一些，都是找同符號下最大的元素累加，
關鍵實作方式：如果找到了正號下最大的元素，那么是在負號陳述句中加；同理，負號最大的元素在正號陳述句中加，不然無法實作加和最大，卡了好久，還有最后的和并未加上最后一個找到的同符號最大值，
第二種實作形式：用乘積來判斷正負號，如果和前一項同號，乘積為正，然后找最大值；之后再乘積為負的時候加上去，

五.Tetrahedron
做了那么多的dp題目，發現自己根本就不會dp！！！學的好亂，一定要花時間整理，即使本題是一個很水的dp，我都做不出來，有很多零星的想法，代碼寫不出來，真的會很失落，簡要講一下思路：
首先：確定dp[i][j]表示的含義，第i步時到達某點的最大方案數，
其次：找dp轉移方程，因為一個點有三種方式到達，所以要再加一重for回圈，

dp[i][j]+=dp[i-1][g]  (g表示從除自己所處點之外某個點，表示上一步g點的最大方案數）

雖然每次訓練賽因為各種原因都輸的很不甘心，但只有不斷的完善，找到隊伍的問題，總結自身的原因，不斷鞭策自己，不斷追趕別人，也還不錯，但說到底，沒有人愿意輸，相信一定會追上并超越，不用怕爬的慢，不為給他們看！！！