課程總結（第五周）

識訓的dp技巧：
1.根據題目意思，首先要考慮陣列元素的含義，
2.找出陣列元素的關系式（也就是狀態轉移方程），比如dp[i][j]通常和dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]有特定關系，要根據具體情況找出規律，
3.找出初始值，感覺這一步同樣非常重要，有點題目初始值定義為無窮大（0x3f3f3f3f3f）,有些定義為0或1，

最簡單實用的博弈判斷技巧：
我看了好多種對于必勝點（P|positive）和必敗點（N|negative）的定義，找到以一種適合我的，

1.只要當前狀態可以轉移到的狀態中有一個是必敗點，那么該點是必勝點，
2.反之，如果當前狀態能轉移到的所有狀態都為勝態，那么該狀態為敗態，

（這就暫時規避掉了兩個選手誰會獲勝的考慮，如果每次到一個點，都要考慮是上一位選手獲勝（必敗點），還是下一位獲勝的話（必勝點），這樣也可以，就是思路會亂），

SG函式：定義難理解，簡單來說就是一個函式，利用了遞回，x節點的SG值是去除x的后繼節點的SG值后的最小非負整數，
SG（x）=0，當前節點x為必敗點，
SG（x）>0，當前節點為必勝點，
（非常有用，但具體如何使用sg打表格解題，還要慢慢體會，雖然找規律也很方便，但也要掌握套路）

巴什博弈，斐波那契博弈，有些懂了，有些沒必要懂，這些博弈有很多通過數學原理進行論證，有些理解不了，但我把關鍵性的結論記住，我的目的是能應用到題目中，那些證明程序不懂就算了，就深入淺出的總結一下識訓：

巴什博弈：n個物品，每次取不超過m個，取完的人贏，（題目分為很多，有的是對每次取得物品進行限制，局限到一個范圍中；有的是規定取完的人輸），
*核心公式：（m+1）r+s (r為自然數，s小于等于m）
只要是（m+1）的倍數就是必勝點，而對于上一個選手來說只要將物品取到（m+1）的倍數就一定會獲勝，簡而言之：if（n%(m+1)==0),后取者贏;否則，先取者贏，

斐波那契博弈：n塊石頭，每次取的石頭數不超過前一次取的人的兩倍，取完者勝，
總之，只要是斐波那契數字都是必敗點，其余為必勝點
還是要根據具體問題分析，

J題識訓：
此題類似于連續子段求最大的那題，而本題要求連續子段絕對值和最小
---->>>1.我的想法是用一個dp[n]陣列記錄每個位置絕對值最小的情況，然后用for回圈進行比較，案例是過的，但是無論怎么改都無法ac，最后發現，因為dp[i-1]可能是經過絕對值的，下一個a[i]加上去時，會導致dp[i]結果不準，思路正確，但是實作方式有問題，

 for(int i=1;i<=n;i++)
        {
            dp[i]=min(abs(dp[i-1]+a[i]),abs(a[i]));
        }
        int minn=1000000;
        for(int i=1;i<=n;i++)
        {
          if(dp[i]<minn) minn=dp[i];
        }

----->>>2.然后發現題目給出的陣列其實很小，只有1000，是可以進行暴力解題，分別就出所有子段和進行比較，便能求出最小的，

 int minn=abs(a[1]);
        for(int i=1;i<=n;i++)
        { int sum=0;
            for(int j=i;j<=n;j++)
            {  sum+=a[j];
                if(abs(sum)<minn) minn=abs(sum);
            }
        }

----->>>3.但是我還是想用DP去解決這個問題，共n個數，可以求出每個數到這個數為止的最小絕對值，再用for回圈進行比較，很好的實作方式，有時雖然min()函式會很方便，但會忽視掉很多細節處理

for(int i=1;i<=n;i++)
        {
            dp[i]=abs(a[i]);
            num=a[i];
            for(int j=i-1;j>=1;j--)
            {
                num+=a[j];
                if(dp[i]>abs(num)) dp[i]=abs(num);
            }
        }

A題識訓：
一頭牛獲得跳高能力，奇數時間服用藥劑能力上升，偶數時間服用藥劑能力下降，
我的思路：
1.開始沒有理解意思，后來想明白，牛每個單位時間都要服用藥劑，但可以選擇跳過藥劑，讀懂題意，下一步，
2.因為時間分奇偶服用藥劑，開始誤以為是二維線性，實際上只需要開兩個表示奇偶的陣列即可，分別表示在奇數點最大跳高能力，偶數點最大跳高能力，
3.思路已經挺清楚了，但一直考慮時間這個因素，認為偶數時間要減，奇數時間加，這其實沒必要，只會更加混亂，之后明白，因為中間會跳過藥劑，所以給出藥劑的時間不是真正服用藥劑的時間，所以可以忽略這個因素，
3.只要關注奇偶陣列就可，列出狀態轉移方程：奇陣列減去藥劑值和偶陣列當前值進行比較；偶陣列加上藥劑值與奇陣列當前值進行比較，
感覺這題理解比較困難，但是理解后的實作其實是很自然的，

E題識訓:
1.我一開始的思路是分成幾種情況討論，若雇傭人數和上一周期相等，則直接發薪水即可；若是本星期雇傭人數大于上一星期人數，則直接雇傭差額人數就好；若是本星期雇傭人數小于上一星期雇傭人數，用min（）來比較裁人的花費和直接不裁直接發薪水的花費，過了樣例，但是一直wr，
2.然后發現，自己把問題想的簡單了，因為本星期的裁人會影響下一星期的雇傭人數，比如：本星期裁掉的人數，其實并不是和上一星期的差額，只有裁掉這個范圍內適合的人數，才能保證下一星期雇傭的人花費少，并且本星期需要的人數也并非是個固定值，雖然對于本星期的花費并非最優，但從整體來看，是最優的，
3.情況一下子就復雜了起來，只能用for回圈對每一種情況逐一排查，看了下別人的思路，其實方法有點像暴力求解，把所有實際需要雇傭的人便利到最大人數，再把上月需要雇傭的人數遍歷到最大，情況特別多，再把這個星期所可能雇傭到的人進行比較，取一個最小值，

本題還有一個難點，因為要求的是最少花費，要將陣列設定為無窮大，于是學到了一種無窮大的最好實作方式 memset(dp,0x3f3f3f3f,sizeof(dp));，

X題識訓：理解題目后，發現不知道怎么去實作，想了幾種方法也都是行不通，并且都是圍繞著洗掉某個’a’或‘b’，這樣做會很難，自己也不會，最后發現，只要做好統計即可.
dp[0][i]表示記錄‘a’開頭的字符數目，dp[1][i]表示記錄第一組‘a’結束后‘b’加進去的字符數目，
dp[2][i]表示記錄b統計到最大后‘a’加進去的字符數目，
感覺很難想到，三大類共六種情況，

codeforces上幾道題：
div.2的第一題：一段字符，插入一個‘a’，使其不是一個回文字符，若是，輸出”NO”，不是，輸出“YES”，
對于我的兩個難點：
1.開始沒想明白怎么在這段字符中隨意插入“a”---->>>之后明白使用insert()即可實作，
2.因為之前都是判斷一個字串是不是回文字串，此題要求插入“a”使其不是一個回文字串，因為插入a的方式的方式有很多，腦子一下子沒轉過來，
其中一個方式：從字串末尾開始遍歷，找到一個不是“a”的位置，在字符前一直對應的位置插入a，輕松的構造了一個非回文字串，特別好的方法！！！

4.7 訓練賽：
Array with Odd Sum ：這題題目一直沒看明白，是隊友告訴我的，發現自己是被困擾在“：=”這個被題目定義的符號上，我以為這是運算子我不知道，還誤以為是“/=”，兩個數做除數，真的不應該，
一句話說明大意：一個陣列數可相互替換，要求和為奇數，
思路是一下就有了，若全為偶數或者n個數全為奇數且n為偶數，則輸出“NO”，其余輸出“YES”，
識訓：看題時不要加上自己的主觀臆斷，題意的理解真的非常重要，這在我們做D題時也充分體現，

第二題一下便過了，沒什么波折，

D - Fight with Monsters：
這題我們經過深入思考，最后發現是一個（分類討論+貪心）的問題，排除多種方法，我們最后想法是：用怪獸的血量對兩人的攻擊和取余，若是在我攻擊范圍內我直接打死；若在二人攻擊范圍之間，再對a進行取余，存入陣列（自然聯想到要進1）的問題；若大于b的攻擊范圍，我直接打死，
這個思路顯然是錯的，刪刪改改，代碼已經不滿足題意了，但是最后還是過了這個題，也是很奇怪，
問題點：
1.a和b的大小不確定，2.當時還沒有判斷出誰先打怪獸，
然后舍棄了分類討論： x[i]=((x[i]-1)%(a+b))/a;這個式子，直接取代了三種討論的情況，然后經分析樣例，發現每次都是a先打，但是，我一直覺得這個式子有點問題，比如：a=2，b=3，boss血量是50，我為了自己打死這個怪獸當怪獸血量剩3的時候就用武器，用2次；如果用這個式子得話怪獸血量是4的時候，用兩次武器，雖然都是2次，但是 是對于不同的怪獸血量而言，這里還是涉及到進1的問題，

4.8 訓練賽：
第一題我們是第一個過的，然后挑了道我們所學范圍之外的題目，涉及位運算，雖然我們的思路是對的，但是代碼由于知識點還沒了解，敲不出來，然后又去把另一道水題過了，但已經相對落后很多了，

4.9訓練賽：
主要分析B題，修馬路，要保證修的馬路一般是好的，題意關鍵在于：n個馬路是必須要修的，要求保證一般是好的，剛開始題目理解錯了，只是簡單分類討論，
1.將n小于g時，直接輸出n；大于g時，
2.求出一半馬路是好的所要天數，
感覺沒什么問題，但一直不過，問題出在（1）上面，想了真的很久，發現：如果好的天數大于等于壞的天數，不管怎么修，都能保證好的馬路占一半以上，這一點一直被忽略，因為思路一直放在好的天數上面，沒有去想不好天數所起到的作用，

做題目的順序很重要！！！

感慨良多，最后只想說：
摒棄雜念，想要什么就要努力爭取；
全力以赴，使最初的選擇顯得正確，