2019牛客暑期多校训练营（第四场）

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

A. meeting

题意：在树上选取一个点使得 $K$ 个点到达这个点的最大值最小

思路：答案为 $K$ 个点的最远点对距离 $\lceil \frac{d}{2}\rceil$


#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f
#define N 100010

int n, m;
vector<int> G[N];
int vis[N], dp[N];
int ans;

void DFS(int u, int fa) {
    if (vis[u]) {
        dp[u] = 0;
    }
    for (auto v : G[u]) {
        if (v == fa) {
            continue;
        }
        DFS(v, u);
        ans = max(ans, dp[u] + dp[v] + 1);
        dp[u] = max(dp[u], dp[v] + 1);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1, x; i <= m; ++i) {
        scanf("%d", &x);
        vis[x] = 1;
    }
    memset(dp, -INF, sizeof dp);
    ans = 0;
    DFS(1, 0);
    printf("%d\n", (ans + 1) / 2);
    return 0;
}

C. sequence

题意：求 $max_{1\leq l \leq r \leq } \{min(a_{l\cdots r}) \cdot sum(b_{l\cdots r})\}$

思路：笛卡尔树维护最小值，线段树维护区间和。


#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define ll long long
#define INFLL 0x3f3f3f3f3f3f3f3f
#define N 3000010
int n, a[N];
ll b[N];

struct Cartesian_Tree {
    struct node {
        int id, val, fa;
        int son[2];
        node() {}
        node (int id, int val, int fa) : id(id), val(val), fa(fa) {
            son[0] = son[1] = 0;
        }
    }t[N];
    int root;
    pii b[N];
    void init() {
        t[0] = node(0, -1e9, 0);
    }
    void build(int n, int *a) {
        for (int i = 1; i <= n; ++i) {
            t[i] = node(i, a[i], 0);
        }
        for (int i = 1; i <= n; ++i) {
            int k = i - 1;
            while (t[k].val > t[i].val) {
                k = t[k].fa;
            }
             
            t[i].son[0] = t[k].son[1];
            t[k].son[1] = i;
            t[i].fa = k;
            t[t[i].son[0]].fa = i;
        }
        root = t[0].son[1];
    }
    int DFS(int u) {
        if (!u) return 0;
        int lsze = DFS(t[u].son[0]); 
        int rsze = DFS(t[u].son[1]);
        b[t[u].id] = pii(lsze, rsze);
        return lsze + rsze + 1;
    }
}CT;

struct SEG {
    struct node {
        ll Max, Min;
        node() {
            Max = -INFLL;
            Min = INFLL;
        }
        node operator + (const node &other) const {
            node res = node();
            res.Max = max(Max, other.Max);
            res.Min = min(Min, other.Min);
            return res;
        }
    }t[N << 2], resl, resr;
    void build(int id, int l, int r) {
        if (l == r) {
            t[id] = node();
            t[id].Max = t[id].Min = b[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    node query(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) {
            return t[id];
        }
        int mid = (l + r) >> 1;
        node res = node();
        if (ql <= mid) res = res + query(id << 1, l, mid, ql, qr);
        if (qr > mid) res = res + query(id << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }
}seg;

namespace IO
{
    const int S=(1<<20)+5;
    //Input Correlation
    char buf[S],*H,*T;
    inline char Get()
    {
        if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
        if(H==T) return -1;return *H++;
    }
    inline int read()
    {
        int x=0,fg=1;char c=Get();
        while(!isdigit(c)&&c!='-') c=Get();
        if(c=='-') fg=-1,c=Get();
        while(isdigit(c)) x=x*10+c-'0',c=Get();
        return x*fg;
    }
    inline void reads(char *s)
    {
        char c=Get();int tot=0;
        while(c<'a'||c>'z') c=Get();
        while(c>='a'&&c<='z') s[++tot]=c,c=Get();
        s[++tot]='\0';
    }
    //Output Correlation
    char obuf[S],*oS=obuf,*oT=oS+S-1,c,qu[55];int qr;
    inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
    inline void putc(char x){*oS++ =x;if(oS==oT) flush();}
    template <class I>inline void print(I x)
    {
        if(!x) putc('0');
        if(x<0) putc('-'),x=-x;
        while(x) qu[++qr]=x%10+'0',x/=10;
        while(qr) putc(qu[qr--]);
        putc('\n');
    }
    inline void prints(const char *s)
    {
        int len=strlen(s);
        for(int i=0;i<len;i++) putc(s[i]);
        putc('\n');
    }
    inline void printd(int d,double x)
    {
        long long t=(long long)floor(x);
        print(t);putc('.');x-=t;
        while(d--)
        {
            double y=x*10;x*=10;
            int c=(int)floor(y);
            putc(c+'0');x-=floor(y);
        }
    }
}using namespace IO;

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    b[0] = 0;
    for (int i = 1; i <= n; ++i) {
        b[i] = read();
        b[i] += b[i - 1];
    }
    CT.init();
    CT.build(n, a);
    CT.DFS(CT.root);
    ll res = -INFLL;
    seg.build(1, 0, n);
    for (int i = 1; i <= n; ++i) {
        int l = i - CT.b[i].fi, r = i + CT.b[i].se;
        seg.resl = seg.query(1, 0, n, l - 1, i - 1);
        seg.resr = seg.query(1, 0, n, i, r);
        res = max(res, 1ll * a[i] * (seg.resr.Max - seg.resl.Min));
        res = max(res, 1ll * a[i] * (seg.resr.Min - seg.resl.Max));
    }
    printf("%lld\n", res);
    return 0;
}

J. free

题意：可以免费 $k$ 条边的最短路

思路： $dis[i][j]$ 表示到达 $i$ ，免费了 $j$ 条边的代价，跑最短路


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define INFLL 0x3f3f3f3f3f3f3f3f
#define N 1010
#define M 100010

struct Edge {
    int to, nxt, w;

    Edge() {}
     
    Edge(int to, int nxt, int w) : to(to), nxt(nxt), w(w) {}
} edge[M << 1];

int n, m, S, T, K;
int head[N], tot;

void Init() {
    memset(head, -1, sizeof head);
    tot = 0;
}

void addedge(int u, int v, int w) {
    edge[++tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[++tot] = Edge(u, head[v], w);
    head[v] = tot++;
}

struct qnode {
    int u, k;
    ll w;

    qnode() {};
     
    qnode(int u, ll w, int k) : u(u), w(w), k(k) {}
     
    bool operator<(const qnode &other) const {
        return w > other.w;
    }
};

ll dis[N][N];

void Dijkstra(int s) {
    memset(dis, INFLL, sizeof dis);
    priority_queue<qnode> q;
    dis[s][0] = 0;
    q.push(qnode(s, 0, 0));
    while (!q.empty()) {
        int u = q.top().u;
        int k = q.top().k;
        q.pop();
        if (u == T) {
            return;
        }
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            ll w = edge[i].w;
            if (dis[u][k] + w < dis[v][k]) {
                dis[v][k] = dis[u][k] + w;
                q.push(qnode(v, dis[v][k], k));
            }
            if (k < K && dis[u][k] < dis[v][k + 1]) {
                dis[v][k + 1] = dis[u][k];
                q.push(qnode(v, dis[v][k + 1], k + 1));
            }
        }
    }
}

int main() {
    scanf("%d %d %d %d %d", &n, &m, &S, &T, &K);
    Init();
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        addedge(u, v, w);
    }
    Dijkstra(S);
    ll ans = INFLL;
    for (int i = 0; i <= K; ++i) {
        ans = min(ans, dis[T][i]);
    }
    printf("%lld\n", ans);
    return 0;
}

K. number

题意：给定一个数字串，问多少个子串可以被 $300$ ，整除

思路： $dp[i][j]$ 表示 $i$ 结尾，余数为 $j$ ， $dp$ 转移即可。


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

char str[N];
ll dp[N][301];

int main() {
    scanf("%s", str + 1);
    ll ans = 0;
    for (int i = 1, len = strlen(str + 1); i <= len; ++i) {
        int now = str[i] - '0';
        dp[i][now]++;
        for (int j = 0; j < 300; ++j) {
            int nxt = (j * 10 + now) % 300;
            dp[i][nxt] += dp[i - 1][j];
        }
        ans += dp[i][0];
    }
    printf("%lld\n", ans);
    return 0;
}

2019牛客多校

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

2019牛客暑期多校训练营（第五场）上一篇

2019 Multi-University Training Contest 3 下一篇