牛客练习赛112 题解

牛客练习赛

A、qsgg and Primes

判断 $n$ 是否是质数， $n$ 每次除以 $10$ 。判断质数的 $i$ 枚举到 $\sqrt{n}$ 即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
    int n;
    cin >> n;

    while (n) {
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                cout << "NO" << '\n';
                return ;
            }
        }

        if (n == 1) {
            cout << "NO" << '\n';
            return ;
        }

        n /= 10;
    }

    cout << "YES" << '\n';
}
int main() {
    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

B、qsgg and Subarray

从小到大枚举右端点的下标，记录 $l s t [i]$ 表示第 $i$ 位为 $0$ 的最右边的下标，即该位从这开始向左都为 $0$ 。

那么左端点的最大取值为所有位 $l s t$ 的最小值。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int lst[31], a[N];
void solve() {
    int n;
    cin >> n;

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

    LL ans = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 31; ++j) {
            if (!(a[i] >> j & 1))
                lst[j] = i;
        }

        int mn = 1e9;

        for (int j = 0; j < 31; ++j) {
            mn = min(mn, lst[j]);
        }

        ans += mn;
    }

    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;

    //  cin>>T;
    while (T--) {
        solve();
    }

    return 0;
}

C、qsgg and Permutation

要使得 $A = B$ 的操作数最少，那么需要找到 $A$ 中最多不会移动的元素，即需要求 $A$ 和 $B$ 的最长公共子序列。

求排列 $A, B$ 的最长公共子序列，可以将 $B$ 排列映射为有序， $A$ 排列做同样的映射。

那么问题转化为经典的最长上升子序列问题，这里用树状数组优化 $d p$ 实现。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int a[N], b[N], p[N], s[N], n;
int lowbit(int x) {
    return x & (-x);
}
int get(int p) {
    int r = 0;

    for (int i = p; i; i -= lowbit(i))
        r = max(r, s[i]);

    return r;
}
void modi(int p, int x) {
    for (int i = p; i <= n; i += lowbit(i)) {
        s[i] = max(s[i], x);
    }
}
void solve() {
    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)
        p[b[i]] = i;

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

    for (int i = 1; i <= n; ++i) {
        int r = get(a[i] - 1);
        ++r;
        modi(a[i], r);
    }

    int ans = n - get(n);
    cout << ans << '\n';
}
int main() {
    //  freopen("a.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;

    //  cin>>T;
    while (T--) {
        solve();
    }

    return 0;
}

D、qsgg and Subway

对于每一条线路相邻的点直接相当于连了一条边。设置起始地铁站到该当前地铁站时间为 $s$ ，周期为 $t$ 。

那么该线路到该地铁站的时间即为 $s+k\times t \ (k\ge0)$ 。若到达当前地铁站的时间为 $d i s [u]$ 。

那么下一班车到达的最快时间为最小的 $k$ 使得 $w=s+kt \ge dis[u]$ ，若 $s\ge dis[u]$ 那么到达的时间为 $w = s$ ,

否则 $k=\lceil\frac{dis[u]-s}{t}\rceil$ ,到达时间为 $w = \lceil\frac{dis[u]-s}{t}\rceil*t+s$ ，到达下一个站的时间为 $w + 1$ 。

对于越早到达的时间显然更优，满足求最短路的性质。那么可以用 $D i j k s t r a$ 算法或 $s p f a$ 算法实现。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, M = 2e6 + 10;
int h[N], e[M], w1[M], w2[M], ne[M], idx;
void add(int a, int b, int c, int d) {
    e[idx] = b, w1[idx] = c, w2[idx] = d, ne[idx] = h[a], h[a] = idx++;
}
typedef pair<LL, int> P;
LL dis[N];
void solve() {
    memset(h, -1, sizeof h);
    int n, m, S;
    cin >> n >> m >> S;

    for (int i = 1; i <= m; ++i) {
        int k, t;
        cin >> k >> t;
        int fr = 0, s = 0;

        for (int j = 1; j <= k; ++j) {
            int x;
            cin >> x;

            if (fr) {
                add(fr, x, s, t);
                ++s;
            }

            fr = x;
        }
    }

    priority_queue<P, vector<P>, greater<P>> Q;
    Q.push({0, S});
    memset(dis, -1, sizeof dis);
    dis[S] = 0;

    while (Q.size()) {
        auto tmp = Q.top();
        Q.pop();
        LL d = tmp.first;
        int u = tmp.second;

        //      cout<<u<<" "<<d<<'\n';
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            LL st = w1[i], t = w2[i];
            LL w;

            if (dis[u] <= st) {
                w = st + 1;
            } else {
                w = (dis[u] - st + t - 1) / t * t + st + 1;
            }

            if (dis[j] == -1 || dis[j] > w) {
                dis[j] = w;
                Q.push({dis[j], j});
            }
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << dis[i] << '\n';
}
int main() {
    //  freopen("a.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;

    //  cin>>T;
    while (T--) {
        solve();
    }

    return 0;
}

E、qsgg and Move

问题容易转换成如何求一个点的 $(x_{1}, y_{1})$ 到达其他点的最远距离，和相应的点。

设其他点为 $(x_{2}, y_{2})$ ， $d i s = ∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$ ，将绝对值符号拆开成 $4$ 种形式，

$d 1 = x_{1} - x_{2} + y_{1} - y_{2} = x_{1} + y_{1} - (x_{2} + y_{2})$

$d 2 = - (x_{1} - x_{2}) + y_{1} - y_{2} = - x_{1} + y_{1} + (x_{2} - y_{2})$

$d 3 = x_{1} - x_{2} - (y_{1} - y_{2}) = x_{1} - y_{1} - (x_{2} - y_{2})$

$d 4 = - (x_{1} - x_{2}) - (y_{1} - y_{2}) = - x_{1} - y_{1} + (x_{2} + y_{2})$

显然 $d i s = m a x (d 1, d 2, d 3, d 4)$ ，观察 $d 1, d 2, d 3, d 4$ 发现 $(x_{1}, y_{1})$ 到达最大距离的点，一定是

当前其他点 $x 2 + y 2$ 最大， $x 2 + y 2$ 最小， $x 2 - y 2$ 最大， $x 2 - y 2$ 最小的4类点。

对4类点排序后，扫描一遍即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
struct Node {
    LL x, y, id;
} t[5][N];
bool cmp1(Node a, Node b) {
    if (a.x + a.y != b.x + b.y)
        return a.x + a.y < b.x + b.y;

    return a.id < b.id;
}
bool cmp2(Node a, Node b) {
    if (a.x + a.y != b.x + b.y)
        return a.x + a.y > b.x + b.y;

    return a.id < b.id;
}
bool cmp3(Node a, Node b) {
    if (a.x - a.y != b.x - b.y)
        return a.x - a.y < b.x - b.y;

    return a.id < b.id;
}
bool cmp4(Node a, Node b) {
    if (a.x - a.y != b.x - b.y)
        return a.x - a.y > b.x - b.y;

    return a.id < b.id;
}
bool vis[N];
void solve() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;

        for (int j = 1; j <= 4; ++j)
            t[j][i] = {x, y, i};
    }

    sort(t[1] + 1, t[1] + 1 + n, cmp1);
    sort(t[2] + 1, t[2] + 1 + n, cmp2);
    sort(t[3] + 1, t[3] + 1 + n, cmp3);
    sort(t[4] + 1, t[4] + 1 + n, cmp4);
    int p[5];

    for (int i = 1; i <= 4; ++i)
        p[i] = 1;

    LL x = 0, y = 0;
    LL ans = 0;

    for (int k = 1; k <= n; ++k) {
        LL dis = -1, re;

        for (int i = 1; i <= 4; ++i) {
            while (p[i] <= n && vis[t[i][p[i]].id]) {
                ++p[i];
            }

            if (i <= 2) {
                LL tmp = x + y - (t[i][p[i]].x + t[i][p[i]].y);
                tmp = abs(tmp);

                if (tmp > dis) {
                    dis = tmp;
                    re = i;
                } else if (tmp == dis && t[re][p[re]].id > t[i][p[i]].id) {
                    re = i;
                }
            } else {
                LL tmp = x - y - (t[i][p[i]].x - t[i][p[i]].y);
                tmp = abs(tmp);

                if (tmp > dis) {
                    dis = tmp;
                    re = i;
                } else if (tmp == dis && t[re][p[re]].id > t[i][p[i]].id) {
                    re = i;
                }
            }
        }

        ans += dis;
        x = t[re][p[re]].x;
        y = t[re][p[re]].y;
        vis[t[re][p[re]].id] = 1;
    }

    cout << ans << '\n';
}
int main() {
    //  freopen("a.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;

    //  cin>>t;
    while (t--) {
        solve();
    }

    return 0;
}

F、qsgg and Money

对于一条线路的油费一定是下降的。观察到 $c_i\le50$ 。

考虑 $d p$ 。 $g_{2} (u, k)$ 表示 $u$ 子树节点到 $u$ 的线路中，最低油费为 $k$ 的线路所花费钱的和。

$g_{1} (u, k)$ 则表示线路数量，那么答案要求所有节点作为根的 $\sum_{k=1}^{50} g_2(root,k)$ 。

考虑换根 $d p$ 即可，复杂度 $O(n\dot \ \max ci)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, M = 1e6 + 10;
LL f1[N][51], f2[N][51], g1[N][51], g2[N][51];
int c[N];
int h[N], w[M], e[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs1(int u, int fa) {
    g1[u][c[u]]++;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];

        if (j == fa)
            continue;

        dfs1(j, u);

        for (int k = 1; k <= 50; ++k) {
            if (k < c[u]) {
                g1[u][k] += g1[j][k];
                g2[u][k] += g2[j][k] + g1[j][k] * k * w[i];
            } else {
                g1[u][c[u]] += g1[j][k];
                g2[u][c[u]] += g2[j][k] + g1[j][k] * k * w[i];
            }
        }
    }
}
void dfs2(int u, int fa) {
    for (int k = 1; k <= 50; ++k) {
        f1[u][k] += g1[u][k];
        f2[u][k] += g2[u][k];
    }

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];

        if (j == fa)
            continue;

        for (int k = 1; k < c[u]; ++k) {
            f1[j][min(c[j], k)] += f1[u][k] - g1[j][k];
            f2[j][min(c[j], k)] += f2[u][k] - (g2[j][k] + g1[j][k] * k * w[i])
                                   + (f1[u][k] - g1[j][k]) * w[i] * k;
        }

        LL s1 = f1[u][c[u]], s2 = f2[u][c[u]];

        for (int k = c[u]; k <= 50; ++k) {
            s2 -= g2[j][k] + k * w[i] * g1[j][k];
            s1 -= g1[j][k];
        }

        f1[j][min(c[j], c[u])] += s1;
        f2[j][min(c[j], c[u])] += s2 + s1 * w[i] * c[u];
        dfs2(j, u);
    }
}
void solve() {
    int n;
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; ++i)
        cin >> c[i];

    for (int i = 1; i <= n - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    dfs1(1, 0);
    dfs2(1, 0);
    LL ans = 0;

    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= 50; ++k) {
            ans += f2[i][k];
        }
    }

    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;

    //  cin>>t;
    while (t--) {
        solve();
    }

    return 0;
}