牛客练习赛

A、qsgg and Primes

判断 $nn$ 是否是质数，$nn$ 每次除以 $1010$ 。判断质数的 $ii$ 枚举到$\sqrt{n}\backslash 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

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

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

#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=BA=B$ 的操作数最少，那么需要找到 $AA$ 中最多不会移动的元素，即需要求$AA$和$BB$的最长公共子序列。

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

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

#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

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

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

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

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

对于越早到达的时间显然更优，满足求最短路的性质。那么可以用$DijkstraDijkstra$算法或 $spfaspfa$ 算法实现。

#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\_1,y\_1)$ 到达其他点的最远距离，和相应的点。

设其他点为$(x_2,y_2)(x\_2,y\_2)$，$dis=\mathrm{\mid }{x}_1-x_2\mathrm{\mid }+\mathrm{\mid }{y}_1-y_2\mathrm{\mid }dis\; =\; |x\_1-x\_2|+|y\_1-y\_2|$，将绝对值符号拆开成 $44$ 种形式，

$d1=x_1-x_2+y_1-y_2=x_1+y_1-(x_2+y_2)d1\; =\; x\_1-x\_2+y\_1-y\_2\; =\; x\_1+y\_1-(x\_2+y\_2)$

$d2=-(x_1-x_2)+y_1-y_2=-x_1+y_1+(x_2-y_2)d2\; =\; -(x\_1-x\_2)+y\_1-y\_2\; =\; -x\_1+y\_1+(x\_2-y\_2)$

$d3=x_1-x_2-(y_1-y_2)=x_1-y_1-(x_2-y_2)d3\; =\; x\_1-x\_2-(y\_1-y\_2)\; =\; x\_1-y\_1-(x\_2-y\_2)$

$d4=-(x_1-x_2)-(y_1-y_2)=-x_1-y_1+(x_2+y_2)d4\; =\; -(x\_1-x\_2)-(y\_1-y\_2)\; =\; -x\_1-y\_1+(x\_2+y\_2)$

显然 $dis=max(d1,d2,d3,d4)dis=max\{(d1,d2,d3,d4)\}$，观察 $d1,d2,d3,d4d1,d2,d3,d4$ 发现 $(x_1,y_1)(x\_1,y\_1)$ 到达最大距离的点，一定是

当前其他点 $x2+y2x2+y2$ 最大，$x2+y2x2+y2$ 最小，$x2-y2x2-y2$ 最大，$x2-y2x2-y2$ 最小 的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\le 50c\_i\backslash le50$。

考虑 $dpdp$。$g_2(u,k)g\_2(u,k)$表示 $uu$ 子树节点到 $uu$ 的线路中，最低油费为 $kk$ 的线路所花费钱的和。

$g_1(u,k)g\_1(u,k)$则表示线路数量，那么答案要求所有节点作为根的${\sum }_{k=1}^{50}{g}_2(root,k)\backslash sum\_\{k=1\}^\{50\}\; g\_2(root,k)$。

考虑换根 $dpdp$ 即可，复杂度$O(n\dot{}\max ci)O(n\backslash dot\; \backslash \; \backslash 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;
}