2020-08-22发表2020-12-27更新题解9 分钟读完 (大约1299个字)

「解题报告」牛客小白月赛 27

又是签到走人的一天……

A 巨木之森

签到题，对每个点维护一个到叶子的最长距离，随便怎么搞搞就行了。本人脑子笨，写了个线段树，复杂度 $O(n\log n)$，实际上有严格 $O(n)$ 解法。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define int long long

const int CN = 1e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class fs {public: int to,nxt,d; void init(int t,int n,int dd) {to = t, nxt = n, d = dd;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y,int z) {E[++ecnt].init(y, hd[x], z); hd[x] = ecnt;}

class SGT {
  public: int d[CN << 2], tag[CN << 2];
    #define lc k << 1
    #define rc k << 1 | 1
    void pd(int l, int r, int k){
        d[lc] += tag[k], d[rc] += tag[k], tag[lc] += tag[k], tag[rc] += tag[k], tag[k] = 0;
    }
    void md(int l, int r, int k, int s, int t, int x){
        if(s <= l && r <= t) return (void)(tag[k] += x, d[k] += x);
        int m = (l + r) >> 1; if(tag[k]) pd(l, r, k);
        if(s <= m) md(l, m, lc, s, t, x); if(m < t) md(m + 1, r, rc, s, t, x);
        d[k] = max(d[lc], d[rc]);
    }
    void upd(int l, int r, int k){
        if(l == r) return; int m = (l + r) >> 1; if(tag[k]) pd(l, r, k);
        upd(l, m, lc), upd(m + 1, r, rc); d[k] = max(d[lc], d[rc]);
    }
    int qu() {return d[1];}
} D;

int n, m, sum = 0, d[CN], id[CN], sz[CN], idx = 0, mxd[CN];
void bd(int u, int p){
    id[u] = ++idx, sz[u] = 1;
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to;
        if(v ^ p) d[v] = d[u] + E[k].d, bd(v, u), sz[u] += sz[v];
    }
}
void dfs(int u, int p){
    mxd[u] = D.qu();
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to;
        if(v ^ p){
            D.md(1, n, 1, 1, n, E[k].d), D.md(1, n, 1, id[v], id[v] + sz[v] - 1, -2ll * E[k].d);
            dfs(v, u);
            D.md(1, n, 1, 1, n, -E[k].d), D.md(1, n, 1, id[v], id[v] + sz[v] - 1, 2ll * E[k].d);
        }
    }
}

signed main()
{
    n = read(), m = read();
    for(int i = 1; i < n; i++){
        int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, w), sum += w;
    }
    sum = 2ll * sum;

    bd(1, 0); for(int i = 1; i <= n; i++) D.md(1, n, 1, id[i], id[i], d[i]);
    dfs(1, 0);

    for(int i = 1; i <= n; i++) mxd[i] = sum - mxd[i];
    sort(mxd + 1, mxd + n + 1); int ans = 0, sum = 0, p = 1;
    while(p <= n && sum + mxd[p] <= m) sum += mxd[p++], ans++;
    printf("%lld", ans);
}

B 乐团派对

考察快速排序以及输入输出。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 1e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

int n, a[CN];
bool cmp(int a, int b) {return a > b;}

int main()
{
    n = read(); for(int i = 1; i <= n; i++) {a[i] = read(); if(a[i] > n) return puts("-1"), 0;}
    sort(a + 1, a + n + 1, cmp); 
    int p = 1, ans = 0;
    while(p <= n) {if(p + a[p] <= n + 1) ans++, p += a[p]; else p++;}
    printf("%d", ans);
}

D 巅峰对决

线段树板子题。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}

class SGT {
  public: int d[CN << 2], mx[CN << 2], mn[CN << 2];
    #define lc k << 1
    #define rc k << 1 | 1
    void bd(int l, int r, int k, int *a){
        if(l == r) return (void)(mx[k] = mn[k] = d[k] = a[l]);
        int m = (l + r) >> 1; bd(l, m, lc, a), bd(m + 1, r, rc, a);
        d[k] = gcd(d[lc], d[rc]), mx[k] = max(mx[lc], mx[rc]), mn[k] = min(mn[lc], mn[rc]);
    }
    void md(int l, int r, int k, int p, int x){
        if(l == r) return (void)(mx[k] = mn[k] = d[k] = x);
        int m = (l + r) >> 1; if(p <= m) md(l, m, lc, p, x); else md(m + 1, r, rc, p, x);
        d[k] = gcd(d[lc], d[rc]), mx[k] = max(mx[lc], mx[rc]), mn[k] = min(mn[lc], mn[rc]);
    }
    int qu(int l, int r, int k, int s, int t){
        if(s <= l && r <= t) return d[k];
        int m = (l + r) >> 1, ans = 0;
        if(s <= m) ans = gcd(qu(l, m, lc, s, t), ans);
        if(m < t) ans = gcd(qu(m + 1, r, rc, s, t), ans);
        return ans;
    }
    int qum(int l, int r, int k, int s, int t){
        if(s <= l && r <= t) return mx[k];
        int m = (l + r) >> 1, ans = 0;
        if(s <= m) ans = max(qum(l, m, lc, s, t), ans);
        if(m < t) ans = max(qum(m + 1, r, rc, s, t), ans);
        return ans;
    }
    int qun(int l, int r, int k, int s, int t){
        if(s <= l && r <= t) return mn[k];
        int m = (l + r) >> 1, ans = INF;
        if(s <= m) ans = min(qun(l, m, lc, s, t), ans);
        if(m < t) ans = min(qun(m + 1, r, rc, s, t), ans);
        return ans;
    }
} D;

int n, q, a[CN];

bool ck(int s, int t){
    if(s == t) return true;
    int MX = D.qum(1, n, 1, s, t), MN = D.qun(1, n, 1, s, t);
    if((MX - MN) ^ (t - s)) return false;
    int G = D.qu(1, n, 1, s, t);
    return G ^ 1 ? 0 : 1;
}

int main()
{
    n = read(), q = read(); for(int i = 1; i <= n; i++) a[i] = read();
    D.bd(1, n, 1, a);
    while(q--){
        int op = read(), x = read(), y = read();
        if(op == 1) D.md(1, n, 1, x, y);
        else ck(x, y) ? puts("YES") : puts("NO");
    }
}

F 核弹剑仙

傻题。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

const int CN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int n, m, f[CN]; bool vis[CN];

void dfs(int u){
    vis[u] = true;
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to; if(!vis[v]) dfs(v);
    }
}
int cnt(int u){
    memset(vis, 0, sizeof(vis));
    dfs(u); int ans = 0;
    for(int i = 1; i <= n; i++) if(vis[i]) ans++;
    return ans - 1;
}

int main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; i++){
        int u = read(), v = read(); add(v, u);
    }

    for(int i = 1; i <= n; i++) printf("%d", cnt(i)), puts("");
}