2020-1-19寒假集训记

· · 个人记录

今天上课一开始教练先说道“说实话我没有想到你们会在Dijkstra这里卡，你们还有谁不会写链前吗”，但说实话emmmm我们几乎在零基础的情况下怎么可能顺便把这些东西全搞懂呀orz、、

emmmm一上课老师就把Dijkstra的模板函数写完了现张贴在此：

#include <bits/stdc++.h>
using namespace std;
priority_queue< pair<int ,int > >q; int dis[N],vis[N];
void Dijkstra(int S)
{
    q.push(make_pair(0,S)); memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); dis[S] = 0;
    while(!q.empty())
    {
        int x = q.top().second; q.pop(); if(vis[x])continue; vis[x] = 1;
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to1=e[i].to;
            if(dis[to1] > dis[x] + e[i].val)
                dis[to1] = dis[x] + e[i].val , q.push(make_pair(-dis[to1],to1));
        }
    }
}

emmm由于一开始是学的是whh大佬的做法，其并没有把to，val，head这些东西放在一个结构体里所以我今天自己照的教练的模板敲了一下相应的题目。目前还算掌握Dijkstra这个算法吧，但是函数可能还需要熟练掌握一下子。

然后教练正准备开全屏广播的时候居然所有电脑都是黑屏呀哈哈哈哈啊哈哈但是后来又点了下课把所有电脑都还原了（所有之前敲的代码也都没了呀orz）[黑线]。后来几个本校高二学长调了一下就好了orz。

然后教练讲了一下子dp但也没有深入讲。

还是像原先一样，ROS还是由题入手，从而讲解算法。

1、【模板】单源最短路径（弱化版） P3371

算法：Dijkstra

这道题原本是按照whh大佬的做法做的，然后今天教练手敲了一下模板于是便运用模板改进了一下做法，也确实算是简短了一些。但其实算法根本思路是不变的。

（本代码中除了dijkstra函数以外其他完全为ROS手敲√）

#include<bits/stdc++.h>
#define M (int)2e6
#define N (int)1e4+10
#define ll long long
using namespace std;
ll n,m,s,cnt;
ll a_,b,c;
ll head[N],vis[N],dis[N];
ll to[M];
priority_queue <pair<ll,ll> > q;
struct node{
    ll to;
    ll next;
    ll val;
}e[M];
void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void Dijkstra(int S)
{
    q.push(make_pair(0,S)); memset(vis,0,sizeof(vis));/*memset(dis,0x3f,sizeof(dis))*/; dis[S] = 0;
    while(!q.empty())
    {
        int x = q.top().second; q.pop(); if(vis[x]) continue; vis[x] = 1;
        for(int i=head[x];i;i=e[i].next)
        {
            int to1=e[i].to;
            if(dis[to1] > dis[x] + e[i].val)
                dis[to1] = dis[x] + e[i].val , q.push(make_pair(-dis[to1],to1));
        }
    }
    return ;
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i = 1; i <= m ; i++){
        scanf("%d%d%d",&a_,&b,&c);
        add(a_,b,c);
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++){
            printf("%lld ",dis[i]);
    }
    return 0;
}

emmm这道题就是有一个问题就是说不能完全套用模板比如这道题目里应该八所有dis数组内的值都初始化为inf（一个很大很大的值），而不能像题目中一样讲所有值都初始化为0x3f（貌似是最大值的意思虽然我不知道为什么是最大值的意义）

2、【模板】单源最短路径（标准版） P4779

算法：Dijkstra

这个说实话ROS懒得仔细做所以就把弱化版的代码直接copy过来然后就WA掉了所有点。

后来又找wxh大佬debug，de了半天没找到。然后cf教练出来了我说几乎和whx一模一样了，又或可以把几乎删掉。然后他说要看数据范围，结果果然是数组开小了orz、、

#include<bits/stdc++.h>
#define M (int)2e6
#define N (int)1e5+10
#define ll long long
using namespace std;
ll n,m,s,cnt;
ll a_,b,c;
ll head[N],vis[N],dis[N];
ll to[M];
priority_queue <pair<ll,ll> > q;
struct node{
    ll to;
    ll next;
    ll val;
}e[M];
void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void Dijkstra(int S)
{
    q.push(make_pair(0,S)); memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis)); dis[S] = 0;
    while(!q.empty())
    {
        int x = q.top().second; q.pop(); if(vis[x]) continue; vis[x] = 1;
        for(int i=head[x];i;i=e[i].next)
        {
            int to1=e[i].to;
            if(dis[to1] > dis[x] + e[i].val)
                dis[to1] = dis[x] + e[i].val , q.push(make_pair(-dis[to1],to1));
        }
    }
    return ;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i = 1; i <= m ; i++){
        scanf("%lld%lld%lld",&a_,&b,&c);
        add(a_,b,c);
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++){
            printf("%lld ",dis[i]);
    }
    return 0;
}

3、采药

算法：dp

做着题的时候ROS没想别的直接就解读是个01背包问题所以按照之前听过的whx大佬的讲解直接开了二维数组求解。

虽然说ROS做这题思路用DP还算清晰了但是还是在此分析一下吧

就运用题面的数据进行最简单容易理解的二维数组模拟DP来进行分析：

70 3
71 100
69 1
1 2

在此解释一下数据：70表示采药可以用的总时间，3表示药的总数；剩下的3行中第一个数表示这种药的采药的时间，第二个数字表示价值。

好的话不多说主要画图分析： （。。。表示省略号）

首先关于这种dp的转移方程先写一下（即dp的核心）：

if(j-val[i]>=0){
    dp[i][j]=max(dp[i-1][j],dp[i][j-val[i]]+val[i])
}
else{
    dp[i][j]=dp[i-1][j]
}

即在进行这个类似于递推的过程中每一个后面的状态是收到前面的已经推导的状态影响的所以需要在每一层推导时推导出这之前的关系。

所以便会有如图的分析过程。

代码实现：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int t,m;
int a[105][3],dp[105][1005];
int main()
{
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a[i][1],&a[i][2]);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=t;j++){
            if(a[i][1]<=j)
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i][1]]+a[i][2]);
            else
            dp[i][j]=dp[i-1][j];
        }
    }
    printf("%d",dp[m][t]);
    return 0;
}

超简短对吧！！！！毕竟还是这个dp太简单了

所以接下来ROS来讲一个进阶版，只运用一维数组模拟dp便完成这个dp过程。

没错你没有听错，就是只用一维数组就模拟出这个过程！！！

虽然一开始ROS也很惊讶但是确实是能够做到的！！

记下来还是开始分析一下：

其实该题可以开一个一维数组以代价为标志来模拟整个结果的dp，然而在整个dp模拟过程中不能够从前往后模拟因为每个药只能购买一次，所以说在dp运用转移方程时只能从后往前模拟，这样才能更新出答案。（从前往前模拟则是这道题：疯狂的采药P1616）

所以代码实现还是很简短的，但是稍微需要点算法分析与构建。

实现代码：

#include<iostream>
#include<cstdio>
#include<cmath> 
using namespace std;
int t,m,a[105],val[105],dp[1050];
int main()
{
    scanf("%d%d",&t,&m);
    for(int i = 1;i <= m; i++){
        scanf("%d%d",&a[i],&val[i]);
    }
    for(int i = 1;i <= m;i++){
        for(int j = t;j >= a[i];j--)
            dp[j] = max(dp[j],dp[j-a[i]]+val[i]);
    }
    printf("%d",dp[t]);
    return 0;
}

炒鸡简短！！！！！！！！！

4、疯狂的采药

算法：dp

这道题的解法其实和上一道采药中用一维数组解题的思维过程是一样的但是这道题要从前往后模拟因为药可以不限量。

实现代码：

#include<iostream>
#include<cstdio>
#include<cmath> 
using namespace std;
int t,m,a[10005],val[10005],dp[100050];
int main()
{
    scanf("%d%d",&t,&m);
    for(int i = 1;i <= m; i++){
        scanf("%d%d",&a[i],&val[i]);
    }
    for(int i = 1;i <= m;i++){
        for(int j = a[i];j <= t;j++)
            dp[j] = max(dp[j],dp[j-a[i]]+val[i]);
    }
    printf("%d",dp[t]);
    return 0;
}

据whh和lyc所说明天讲数论

啊啊啊啊啊啊集训讲的信息量太大了orz、、、