學習記錄——第五周

上個周沒寫博客，空了一周，兩個周下來學的東西還是挺多的，DP，博弈，一些小技巧，還學了點其他的知識，比如進位的問題吧，比如關于超時會有什么問題吧等等，下面就開始整理整理 一.

先從DP開始吧，這些天主要搞的DP

我對DP的理解還是十分有限（一共才做了幾個題），只有個大概的理解，感覺上去DP的本質上就是窮舉，窮舉出子情況然后讓整個問題得到最優的解法，那么窮舉的方法就是利用“狀態轉化方程”來進行的，通過這個方程把每一步應該怎么走搞清楚就好
另外一點就是DP的窮舉和一般的窮舉不太一樣就像是“最大矩陣和”問題它也可通過一般的窮舉來做，但是時間復雜度特別大，利用DP的方法你會發現時間復雜度下降了，占用的空間上去了，所以我覺得DP的窮舉是犧牲空間以換取時間的窮舉

然后，，是做DP的基本步驟

1.確定是動態規劃來解決的題型
一般來講字串，每個區間狀態不定最終要求找出最后狀態，不能排序但是又得找最優解的題都是可以用動態規劃來做
2.確定動態的dp陣串列示的意義
很少有像最大子串這樣的用一個一維的就能解決的動態規劃問題，一般都要一個二維的
dp[i][j]
比如最長公共子串問題里：
dp[i][j]這里的就表示第一個字符，第二個字符的i，j個字符為結尾的最長公共子串長度
在奶牛跳躍問題里dp[i][0]與dp[i][1]表示的就是在奇數偶數時間內吃到的提升跳躍能力的藥水的最大值

3.找出狀態轉化方程
狀態轉化方程，就是每一步應當怎么做，然后遞回出最終答案
比如在編譯距離的問題里，每一步需要解決的問題就是怎么實作操作的步驟最少
4.圍繞狀態轉化方程來構建代碼
這個就沒什么好說的了，基本功；如果不會撰寫，去找題解，在自己能理解狀態轉化方程的基礎上把一個代碼反復編譯每次最后有自己的優化和改造；

題意如其名：給出兩個字串，要求你求一下這兩個字串的最長公共子序列
這里說明一下：子序列（不連續），子串（連續），很多作者沒有注意這一點，也有很多人被誤導了，
舉例：
1.abcdef
2.acef
對與第一個的acef和第二個acef正好匹配
所以最長公共子串為4；
求解思路：
動態規劃；
下面給出一組二維陣列便于理解
　　 b　　a　　b
c　　0　　0　　0
a　　0　　1　　0
b　　1　　0　　1
a　　0　　1　　0

步驟1：找出dp陣列的含義
這個題既然是兩個字串那么很容易就可以知道dp應當是dp[i][j]
設第一個字串的長度為len1，第二個字串長度為len2

第一種情況：
如果當這兩個字串的第i個和第j個字符是一樣的時候，dp[i][j]=dp[i-1][j-1]+1;
也就是說以這個字符為結尾的子序列又多了一個（或者說是又長了）一個字符，

第二種情況：
當這兩個字符的第i個和第j個字符不一樣的時候你可以有兩種選擇
讓這個dp[i][j]=dp[i-1][j]（ 按照第一個字串來保持子序列長度 ）或者是dp[i][j-1]（按照第二個）;
括號里的話看不懂就當是在放屁好了

然而你要最大的公共子序列那么第二種情況下你肯定會選擇最大的
dp[i][j]=max（dp[i-1][j]，dp[i][j-1])

步驟2：
狀態轉換方程
if(s1[i]==s[j])
dp[i][j]=dp[i-1][j-1]+1;
if(s1[i]!=s2[j])
dp[i][j]=max（dp[i-1][j]，dp[i][j-1]);

步驟3：
根據狀態方程構建代碼

#include <bits/stdc++.h>

using namespace std;
int maxd(int a,int b)
{
    return a<b?b:a;
}
int main()
{
    int t;
    for(cin>>t;t;t--)
    {
        string s1,s2;
        int dp[100][100];
        memset(dp,0,sizeof(dp));
        cin>>s1>>s2;
        int len1=s1.size(),len2=s2.size();
        for(int i=1;i<=len1;i++)/*看不懂回去看圖*/
        {
            for(int j=1;j<=len2;j++)
            {
                if(s1[i-1]==s2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        cout<<dp[len1][len2]<<endl;
    }
}

DP最難的還是構建狀態轉換方程，現在會的也就只有，最長公共子串，最大欄位，最長上升序列這些簡單的，，希望以后能會的多一點吧

二.博弈
其實這個博弈到時沒啥好說的，很多東西我是證不出來，但是都有現成的結論可以用，比如巴什博弈的先手勝利調價是n%（m+1）！=1，威佐夫博弈的，斐波那契博弈的，有了這些結論去解決相應的問題就很簡單，但是沒有這些的話估計博弈題就指定GG了，但是我目前接觸到的博弈也就只有5種，去了上面的幾種還有個環形博弈，都是根據已有的知識進行的討論

值得注意的一點就是一個叫P/N分析法的東西，這個是博弈的關鍵
此法有如下定理：
0.終點是必敗點（這也是下兩條的前提）
1.只用一步就到必勝點的必為必敗點
2.只用一步就能走到必敗點的就是必勝點

當遇到博弈題的時候判斷條件不一定就就是最原始的，也有可能會改變勝利的條件，這個時候就要用PN分析來簡單的分析一下再套用公式

三.位運算
原本學了點位運算的操作，但我只記住了|和&的操作，這次多學一點，
比如異或

異或這個操作是可以用來去掉重復的東西，比如一個陣列里

1 1 2 2 3 3 5
我只想要5
那么就可以用異或的操作
如果兩個都相同就會變0否則會變1
>>
二進制位向右移動
<<
二進制位向左移動

四.小技巧

1）學了文本輸入的使用

原本我只是知道有一行代碼可以進行文本輸入的操作而已
然后學了才知道 freopen("in.txt",“r”,stdin);
這行的代碼的in.txt說明和CPP檔案在一個檔案夾下的那個輸入文本檔案的名字叫“in”，然后那個r代表這個是read（讀入）

2）了解幾個會造成超時的玩意兒
1.
memset這個東西居然有的時候會造成超時，我在做反恐訓練營這個題的時候發現的
順帶一提我用for回圈來做初始化的操作就沒超時
2.
scanf和printf真的有的時候是必須的，cin，cout有的時候就算加上了
ios::sync那個和cout.tie這個也不行，
3.
陣列有的時候越界可能是就因為人家規定2000的大小你就開2000，很容易越界，定義成2000+100就可以了

3）
關于進“1”
比如說我m/n（這倆都是整形），我想讓他向上取整咋辦呢
（m+n-1）/n
整的好~

4）
關于進位
小數的進位我今天學了這么個東西
可以用字串
比如char i=4；
可以由 int a=i-‘0’；
這樣a就等于4了
一般使用不到了啦，但是今天做了個小數進位的問題，不能取模，化為整形還賊麻煩，憑空一技讓這個題解出來了
順帶一提string也可這么操作

http://acm.hdu.edu.cn/showproblem.php?pid=6575
這是那個杭電的題
show my code！

#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <string>
using namespace std;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        double sum=0;
        string a;
        for(int i=0;i<n;i++)
        {
            cin>>a;
            double temp=a[a.size()-1]-'0';
            if(temp>=5)
            {
                sum+=10-temp;
            }
            else
            {
                sum-=temp;
            }
        }
        cout<<fixed<<setprecision(3)<<sum/1000.0<<endl;
    }

    return 0;
}