学习记录——第五周

?????上个周没写博客，空了一周，两个周下来学的东西还是挺多的，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;
}