废话不多说开始写总结：

1.题目：幸运数字(lucky)

题目描述： 给出一个数字x，要求找出比x大的最小的那个幸运数字。如果我们有一个6位数的前3位之和等于后3位之和，那么这个数就是幸运数。

题解：

一个简单的题目，我们只要枚举x后的所有6位数，判断枚举出的6位数是不是幸运数就可以了

反思：

这个题目我居然没拿满分！原因出在当时我有点心不在焉导致我在写程序是误把x的范围当成枚举的范围了导致有一些分丢掉QAQ。下次写题必须要集中精力了。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

//定义变量
int temp_num;
int num[10];

int change(int x){

    int sum=0;
    while (x!=0){
        num[sum]=x%10;
        x/=10;
        sum++;
    }

    return sum;

}

int main(){

    //从文件读入
    freopen ("lucky.in","r",stdin);
    freopen ("lucky.out","w",stdout);

    cin>>temp_num;

    int length=change(temp_num);

    for (int i=temp_num+1;i<=999999;i++){
        change (i);
        int a=num[3]+num[4]+num[5];
        int b=num[0]+num[1]+num[2];
        if (a==b){
            cout<<i<<endl;
            return 0;
        }
    }

    cout<<-1<<endl;

    return 0;

}

2. 题目：售货员(salesman)

题目描述：一个数轴上有n个点x(1),x(2),x(3)。现在可以把任意一个点当作起点，把任意一个点当作终点，从x(i)移动到x(j)的代价为abs(x(i)-x(j))。求花费的最小代价。

题解1：

我最初的思路，因为可以从任何一个点出发，从任何一个点结束，且从x(i)移动到x(j)的代价为abs(x(i)-x(j))(这不是什么都没说吗),所以很容易想到我们把这个数组从小到大排序一下，然后从第二个点往最后一个点遍历，没到一个点就把结果加上x(i)-x(i-1)。最后输出结果。复杂度O(n*log(n))。

题解2：

其实不难发现如果们对上面的那个题解优化一下，发现其实答案就是x()中的最大值-最小值。时间复杂度O(n)。

反思：

做这道题目时看到题目中有一个提示要我们小心只有一个点的情况，于是我就加了一个特判，结果就错了。下次再改之前一定要冷静冷静再冷静！

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int t;//数据数量
int n;//点的个数

int main(){

    //从文件读入
    freopen ("salesman.in","r",stdin);
    freopen ("salesman.out","w",stdout);

    cin>>t;
    for (int i=1;i<=t;i++){
        cin>>n;
        int max_ans=-1,min_ans=1e9,temp_point;
        for (int i=1;i<=n;i++){
            cin>>temp_point;//输入点的信息
            max_ans=max(max_ans,temp_point);
            min_ans=min(min_ans,temp_point);
        }

        //输出答案
        cout<<max_ans-min_ans<<endl;

    }

    return 0;

}

3. 题目：好大的gcd(gcd)：

题目描述：有两个数组 A,B，大小均为N。请在 A中选择一个数 x，B 中选择一个数 y，使得 gcd(x,y) 最大；如果有多组数 gcd 相同，找出 x+y 最大的。

题解：

我们先要有两个数组max_a[],max_b[]，其中maxz_a[i]表示以i为因子的A数组中的最大的数，max_b[i]表示以i为因子的B数组中的最大的数。那我们要如何快速求出max_a,max_b呢？ 首先我们要统计出A数组中每个数的个数，用cnt[]数组来存,cnt[i]的意思是i出现的个数。然后我们再枚举倍数，因为这能降低不少复杂度（复杂度为O(n*sqrt(n)))。 其中枚举倍数的代码如下：

for (int i=1;i<=1e6+6;i++){//枚举因子
    for (int j=i;j<=1e6+6;i++){//这里便是枚举倍数

    }
}

如果我们发现这个倍数再A数组中存在，那么我们就用这个倍数更新max_a[i]的值
所以这个部分完整的代码如下

    for (int i=1;i<=N;i++){//const int N = 1e+6
        for (int j=i;j<=N;j+=i){//枚举倍数,妙哉
            if (cnt[j]){//如果a[]中这个这个倍数j存在
                max_a[i]=max(max_a[i],j);
            }
        }
    }

我们对max_b也进行同样的处理。最后要注意处理max_b之前要对cnt数组清零
最后就是如何输出答案，既然我们有了max_a[],max_b[],那么我们再循环一遍，找到他们共同因子最大的且和最大的数。这部分代码如下：

    int mx=0;
    for (int i=1;i<=N;i++){
        if ((max_a[i]!=0)&&(max_b[i])!=0) mx=i;//如果i同时是A数组中的数与B数组中的数的因子。
    }

最后输出max_a[mx]+max_b[mx]即可

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e6+5;

int n;
int a[N];
int b[N];
int max_a[N],max_b[N];//max_a[i]表示a[]数组中i的倍数的最大值
int cnt[N];

int main(){

    //从文件输入
    freopen ("gcd.in","r",stdin);
    freopen ("gcd.out","w",stdout);

    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    for (int i=1;i<=n;i++){
        cin>>b[i];
    }

    for (int i=1;i<=n;i++){
        cnt[a[i]]++;//统计a[i]中的数出现的次数
    }

    for (int i=1;i<=N;i++){
        for (int j=i;j<=N;j+=i){//枚举倍数,妙哉
            if (cnt[j]){//如果a[]中这个这个倍数j存在
                max_a[i]=max(max_a[i],j);
            }
        }
    }

    for (int i=1;i<=n;i++) cnt[a[i]]=0;

    for (int i=1;i<=n;i++){
        cnt[b[i]]++;//统计b[]数组中的数字的个数
    }

    for (int i=1;i<=N;i++){
        for (int j=i;j<=N;j+=i){
            if (cnt[j]){
                max_b[i]=max(max_b[i],j);
            }
        }
    }

    int mx=0;
    for (int i=1;i<=N;i++){
        if ((max_a[i]!=0)&&(max_b[i])!=0) mx=i;//如果i同时是A数组中的数与B数组中的数的因子。
    }

    cout<<max_a[mx]+max_b[mx]<<endl;

    return 0;

}

我终于搞出第四题了，第四题真的是我见过的最恶心的题目（没有之一）

4. 买买买！(purchase):

题目描述：有n个宝贝，每个宝贝有自己的品牌（ps：不同宝贝可能是同一个牌子），有自己的价格，现在有q个人要买，每个人有d个自己喜欢的品牌(d>=1&&d<=5),每个想要从自己喜欢的宝贝中顺走第k便宜的，请问被每个代言人带走的商品的价格是什么？如果不存在这件商品，输出-1。

题解：

由于林与汪的做法难以理解，（二进制位运算与二分没学好的说），于是我就模仿了一下何的方法。并对之减少了代码量。大概的思路如下： 首先我们对这个问题进行降维打击，从(d==1)的情况开始考虑，如果d==1，那么我们就可以在O(1)地找出这个人喜欢的品牌，然后把这个人喜欢的品牌中的所有商品的价格扔进一个vector里，然后我们再O(1)输出这个vector中第k个元素，如果k大于这个vector地大小，那么就输出-1。不过如果你在d不是1地情况下这么做很有可能会超时(Because 1<=e<=1e5,1<=q<=1e5。)所以我们得换个思路。我们其实主要是在找某个品牌地物品并把价格扔进vector中这个过程会增加程序复杂度。其他地方就是输入输出的复杂度，这部分复杂度难以降下来。所以我们可以提前把每种结果的价格扔进vector，并用二进制码标记，这样我们我们就能O(5)地找出答案（反正我的程序是这样）。
废了半天劲，还是没解释清楚。

不讲了直接上代码

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

//定义常量
const int N=1e5+5;

//定义变量
int n;//宝贝的数量
int q;//代理人的数量
int d;//代理人喜欢的宝贝的数量
vector <int> treasure[N];//treasure[i]表示第i个品牌的价格
int brand[N];
int a[8];
vector <int> temp;//用于储存转换后的二进制码
vector <int> every_price[35];//用于储存每一种情况的价格
struct v{
    int num;//喜欢的宝贝的数量
    vector <int> brand_pep;//代理人喜欢的宝贝品牌
    int k;//代理人喜欢这些宝贝中    
}pep[N];

void fuc (){
    //生成所有可能的选择
    for (int i=1;i<=31;i++){
        int temp_num=i;
        temp.clear();//对这个存放二进制码的数组清空
        temp.push_back(0);//对开始的位置充0,使其第一个元素用标号1的位置开始
        while (temp_num!=0){//这个循环用来转换二进制
            temp.push_back(temp_num%2);
            temp_num/=2;
        }
        for (int j=0;j<(int)temp.size();j++){//枚举所有可能的选择中的品牌
            if (temp[j]){//如果在当前可能中这个品牌要的话
                for (int k=0;k<(int)treasure[j].size();k++){
                    every_price[i].push_back(treasure[j][k]);
                }
            }
        }
        sort (every_price[i].begin(),every_price[i].end());//对每种情况排序
    }
}

int main(){

    //从文件读入
    freopen ("purchase.in","r",stdin);
    freopen ("purchase.out","w",stdout);

    cin>>n;
    //输入宝贝的信息
    for (int i=1;i<=n;i++){
        cin>>brand[i];
    }
    int temp_price;
    for (int i=1;i<=n;i++){
        cin>>temp_price;
        treasure[brand[i]].push_back(temp_price);
    }

    //初始化
    fuc ();

    //输入代理人的信息
    cin>>q;
    for (int i=1;i<=q;i++){
        cin>>d;//输入喜欢的宝贝的数量
        for (int i=0;i<8;i++) a[i]=0;//初始化
        int temp_a;
        for (int j=1;j<=d;j++){
            cin>>temp_a;//输入喜欢的品牌
            a[temp_a]=1;//标记要的品牌
        }
        cin>>pep[i].k;//输入k
        int sum=0,ans=0;//初始化
        for (int j=1;j<=5;j++){
            ans+=a[j]*pow(2,sum);//二进制转码    
            sum++;
        }
        if (pep[i].k>(int)every_price[ans].size()){
            cout<<-1<<endl;
            continue;
        }
        cout<<every_price[ans][pep[i].k-1]<<endl;
    }

    return 0;

}

这篇博客主要用来记录一下这几天学的算法
1. 普通DP：
主要是动态转移方程很难想到，比如说第一天的免费馅饼，开始来晚了，只听了一半，刚好怎么推方程的那一部分我没有听到。没办法，自己去找网上的博客，然后就发现了一种神奇的方法：
1：首先我们先要有一个矩阵martix（中黑客帝国的毒太深了），其中martix的横坐标为time，纵坐标为位子place，这样我们就可以存入每个时间所对应的位置
2：然后你就懂了吧，这样我们可以转换成如何从time=0，place=5这个位子出发，到达time为规定时间的点的最小花费。
（ps：这个规定时间只要在读入时对每次输入的时间取max即可得到）
3:然后在扫一遍time=规定时间那一行的数据，求出这行数据的最大值就可以找到本题的答案了
2:区间DP：
这里先说一个比较坑的地方（论区间DP的正确打开方式)：
首先我们要枚举长度i，再枚举左端点l,这样右端点的值为l+i-1;
这样我们才能从更小的区间转移到更大的区间
区间DP就是从更小的区间中找出此时的状态，这里以匹配括号那道题为例。

题目：
如果有一个全由括号组成的字符串，如何找出其中最长的括号序列长度?(括号序列即匹配的括号的序列)
题解：
这道题目是一个区间DP，我们设dp[l][r]为l~r中的最长括号序列长度,用arr存入输入的字符串。然后我们进行分类讨论:
1：如果

l==r;

那么

dp[l][r]=0;

然后

continue;

2：如果

arr[l]=='(' && arr[r]==')'||arr[l]=='[' && arr[r]==']';

那么

dp[l][r]=dp[l+1][r-1]+2;

3: 然后我们再

int ans_max=-1;
for (int k=l;k<r;k++){
    ans_max=max(ans_max,dp[l][k]+dp[k+1][r]);
}
dp[l][r]=ans_max;

这是为了找出类似于"()()()"这样的情况的最大值

最后再用这样的代码

dp[l][r]=max(max(dp[l+1][r],dp[l][r-1]),dp[l][r]);

判断两边不相等的情况 然后

cout<<dp[1][length]<<endl;//length为输入字符串的长度

即可。

3：树形DP，这个学的不好就不讲了，当然还是要贴一份树的遍历的代码滴!要不然这篇文章就太水了

//有根树
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

vector <int> map[5000];
int  book[5000];

void add(int x,int y){//X is father,y is son.
    map[x].push_back(y);
}

void dfs(int x){
    vector<int>::iterator it;
    for (it=map[x].begin();it!=map[x].end();it++){
        cout<<*it<<endl;//输出儿子
        dfs(*it);
    }

    return ;//返回

}

int main(){

    //调试用
    freopen ("input.in","r",stdin);

    int n;//n个关系
    cin>>n;
    int temp_x,temp_y;//Temp_x is father,temp_y is son.
    for (;;){
        cin>>temp_x>>temp_y;
        if (temp_x==0&&temp_y==0) break;
        book[temp_y]++;
        add(temp_x,temp_y);
    }

    //找根
    int root;
    for (int i=1;i<=n;i++){
        if (book[i]==0){
            root=i;
        }
    }

    dfs (root);

    return 0;

}

算法总结就到这里吧，FIGHTING！

第一次正儿八经地来正睿上课，被虐得好惨，我都快报警了。尤其是徐龙杰小变态，两个月做了一百多道题（┏(゜ロ゜;)┛），这是人吗？幸好两场考试比他考得好（逃）
唔，这也警示了我，以后要好好练了。我一个比他大三岁的人被吊起来打，本来就不多的愉悦感瞬间没了，以后训练时不能继续做白日梦了，要不然最后学会了如何商业胡吹，却做不了几个题目。
所以说啊，以后要好好集中精力写题了
希望以后能把徐龙杰摁在地上摩擦

好吧，其实以上都是都是水的内容。现在我们 进入正题
正睿这几天最大的收获其实就是做题的效率高了很多，比如说以前的八皇后问题写了我两个星期。但跟徐龙杰比起来还差的远。还有胡昊同学做题效率也是贼高。（不对，我怎么又在商业吹捧）。不过，为什么徐龙杰做题做的那么快，值得思考。尤其是学动态规划时，我还在被题目坑得快报警时，徐龙杰早做完了。

这几天的算法总结明天再补充吧，参加了C班的小比赛作业都来不及做了(尽管只做了两道题）。还有两篇作文+数不清的试卷

总之一句话：人和人差距咋那么大？
希望3月18后跟徐龙杰的差距不要太大

恭喜你看完这篇水文，我很抱歉辣了你的眼睛,当然本人不提供医药费!(手动坏笑）