本次比赛题解：戳这里 ——> 题解

写在前面

迟到的总结。
不过个人觉得这一次题出的很好(*￣︶￣)。

T1 货物收集

题目传送门：货物收集

题目描述

图片说明

分析

直接贪心就好，每次选武力值最小的就好，反正答案不会更劣。
题解的做法，二分也可以。

代码

/*********************
User:fxyly
Language:c++
problem：Nowcoder 
Algorithm 
*********************/
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;

int n,w,size,first[maxn];
long long a[maxn];
bool vis[maxn];

struct Edge{
    int v,nt;
    long long w;
}edge[maxn << 1];

template<class T>inline void read(T &x){
    x = 0;char ch = getchar();bool flag = 0;
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
}

template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}

void eadd(int u,int v,int w){
    edge[++size].v = v;
    edge[size].w = w;
    edge[size].nt = first[u];
    first[u] = size;
}

void readdata(){
    read(n);read(w);
    for(int i = 2;i <= n; ++ i) read(a[i]);
    for(int i = 1;i < n; ++ i){
        int u,v,w;read(u);read(v);read(w);
        eadd(u,v,w);eadd(v,u,w);
    }
}

void bfs(){
    typedef pair<long long,int>pir;
    long long cur = 0,ans = 0;
    priority_queue<pir,vector<pir>,greater<pir> >q;
    q.push(make_pair(0,1));
    while(!q.empty()){
        int u = q.top().second;
        long long x = q.top().first;q.pop();
        vis[u] = 1;cur += a[u];ans = max(ans,x);
        if(cur >= w) break;
        for(int i = first[u];i;i = edge[i].nt){
            int v = edge[i].v;long long w = edge[i].w;
            if(vis[v]) continue;
            vis[v] = 1;
            q.push(make_pair(w,v));
        }
    }
    put(ans);
}

void work(){
    bfs();
}

int main(){
//    freopen("3.in","r",stdin); 
    readdata();
    work();
    return 0;
}

T2 货物分组

题目传送门：货物分组

题目描述

图片说明

分析

因为题目中并没有限制箱子的个数，而我们所求的只是 $n$ 个物品的最小的花费。又因为花费的计算方法与箱子数有关：

对于第 $i$ 个箱子，如果里面装的货物总重量为 $w$ ，那么费用为 $i*w$ 。

注意到 $i$ 是箱子数，说明越到后面的箱子里的物品，就会比前一个多算一遍。这样，我们就可以倒序处理，到物品 $i$ ，就直接加 $\sum_{j = i}^{j<=n}{a[j]}$ ，就可以把花费都算出来，还不用存下箱子的个数

所以我们可以直接将数组降为一维。用 $f[i]$ 表示(从后往前)到第 $i$ 个物品的最小花费

容易知道 $f[i]$ 是从后向前单调递增的，这可以为我们省去不少麻烦。

看转移方程： $f[i]\ =\ f[j]\ +\ sum[n]\ -\ sum[i\ -\ 1]\ +\ max(a[k],i<=k<=j)\ -\ min(a[k],i<=k<=j)$

这样转移明显还是 $n^2$ 的，但是我们可以发现，其实方程就只有最大值、最小值、 $f[j]$ 与 $j$ 有关系了。我们先前分析到 $f[j]$ 是有单调性的，所以在最大值与最小值确定的情况下， $j$ 越大，答案越优。

所以，我们就只需要考虑最大值与最小值变化的状态了。
我们可以用单调栈预处理出每一个位置后面第一个大于/小于它的数的位置，转移的时候直接跳就好

时间复杂度……有些玄学，不过跑的挺快的

代码

/**********************
User:fxyly
Language:c++
Problem:Nowcoder
Algorithm:
**********************/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int n,w,tp;
long long a[maxn], f[maxn], sum[maxn];
int suc_ma[maxn], suc_mi[maxn], s[maxn];

template<class T>inline void read(T &x){
    x = 0;char ch = getchar();bool flag = 0;
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
}

template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}

void readdata(){
    read(n);read(w);
    for(int i = 1; i <= n; ++ i) read(a[i]), sum[i] = sum[i - 1] + a[i];
}

void work(){
    //单调栈维护i后第一个大于/小于i的位置 
    //时刻记得s中是位置 
    tp = 0;
    for(int i = n; i >= 1; -- i){//get suc_mi
        while(tp && a[i] <= a[s[tp - 1]]) -- tp;
        if(! tp) suc_mi[i] = n + 1;
        else suc_mi[i] = s[tp - 1];
        s[tp ++ ] = i;
    }
    tp = 0;
    for(int i = n; i >= 1; -- i){//get suc_ma
        while(tp && a[i] >= a[s[tp - 1]]) -- tp;
        if(! tp) suc_ma[i] = n + 1;
        else suc_ma[i] = s[tp - 1];
        s[tp ++ ] = i;
    }

    //倒序，解决了第i个箱子的费用为sum[l,r]*i的问题 
    for(int i = n;i >= 1; -- i){
        //找到这个位置最多能装到的位置 
        int pos = upper_bound(sum + 1, sum + n + 1, sum[i - 1] + w) - (sum + 1);

        f[i] = f[i + 1] + sum[n] - sum[i - 1];

        int mipos = i, mapos = i, j = i;
        long long cur_sum = sum[n] - sum[i - 1];
        while(j <= pos){

            j = min(pos, min(suc_mi[mipos] - 1, suc_ma[mapos] - 1));
            //f数组从后往前递增（物品增多了嘛） ，所以转移的位置越后越好（最大最小不变的情况下） 
            f[i] = min(f[i], f[j + 1] + cur_sum + a[mapos] - a[mipos]);
            j ++;
            if(a[j] < a[mipos]) mipos = j;
            if(a[j] > a[mapos]) mapos = j;
        }
    }
    put(f[1]); 
}

int main(){
    readdata();
    work();
    return 0;
}

T3 地形计算

题目传送门：地形计算

题目描述

图片说明

分析

我个人认为出题人的讲解非常好
~~我就不说了~~
一句话，暴搜，加一个 $meet\ in\ the\ mid$ 就可以了

代码

/*********************
User:fxyly
Language:c++
Problem:Nowcoder
Algorithm:
*********************/
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int n, m, size,tp,now;
int first[maxn],s[maxn];
long long a[maxn],ans,tot[maxn];
long long vis[maxn],used[maxn];
struct Edge{
    int v, nt;
}edge[maxn << 1];
struct Degree{
    int d, id;
}ind[maxn];

template<class T>inline void read(T &x){
    x = 0;bool flag = 0;char ch = getchar();
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
} 
template<class T>void putch(const T x) {if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x) {if(x < 0) putchar('-'),putch(-x);else putch(x);}

void eadd(int u, int v){
    edge[++size].v = v;
    edge[size].nt = first[u];
    first[u] = size;
}

void readdata(){
    read(n); read(m);
    for(int i = 1; i <= n; ++ i) read(a[i]), ind[i].id = i;
    for(int i = 1; i <= m; ++ i) {
        int u, v;read(u); read(v);
        eadd(u, v); eadd(v, u); ind[u].d ++; ind[v].d ++;
    }
}

bool cmp(const Degree &x,const Degree &y){
    return x.d > y.d;
}

void dfs(int u,int f,int d,long long sum){
    if(d == 2) {
        if(vis[u]) ans = (ans + vis[u] + a[f] * tot[u] % mod) % mod;
        //一个点可能有很多条路径，所以是累加 
        vis[u] += sum;tot[u] ++; 
        return;
    }
    for(int i = first[u];i;i = edge[i].nt){
        int v = edge[i].v;if(v == f) continue;
        //因为只扩展两层，而且没有重边，只需要标记深度为两层的点，判断一下反向边就好，
        //如果不是两层，就需要另存数组来看这个点是否在栈中
        if(used[v]) continue;//已经删除的点 
        dfs(v,u,d + 1,(sum + a[v]) % mod);
    }
}

void del(int u,int f,int d){
    if(d == 2) {vis[u] = tot[u] = 0;return;}
    for(int i = first[u];i;i = edge[i].nt){
        int v = edge[i].v;if(v == f) continue;
        if(used[v]) continue;
        del(v,u,d + 1);
    }
}

void work(){
    sort(ind + 1,ind + 1 + n,cmp);
    for(int i = 1;i <= n; ++ i){
        now = ind[i].id;
        dfs(ind[i].id,0,0,a[ind[i].id]);
        del(ind[i].id,0,0);used[ind[i].id] = 1; 
    }
    put(ans);
}

int main(){
    readdata();
    work();
    return 0;
}

完结撒花！✿✿ヽ(°▽°)ノ✿

$\color{cornflowerblue}{为你，所向披靡！}$

$\color{black}{By}\ \ \ \ \color{royalblue}{Mandy.H.Y}$

$\color{black}{Date}\ \ \ \ \color{black}{2019.11.6}$

牛客CSP-S提高组赛前集训营3解题报告

写在前面

T1 货物收集

题目描述

分析

代码

T2 货物分组

题目描述

分析

代码

T3 地形计算

题目描述

分析

代码

完结撒花！✿✿ヽ(°▽°)ノ✿