@dxbdly 2022-07-16T03:18:59.000000Z 字数 6325 阅读 183

7.13暑期模拟赛

2022暑

7.13暑期模拟赛

期望得分：

T1	T2	T3	Sum
100	50	80	230

实际得分：

T1	T2	T3	Sum
95	50	0	145

T1 tsm

首先考虑没有修改的情况。

最后的游戏，是一个典型的 $\operatorname{Nim}$ 游戏，那么就只要考虑如何求出 $m$ 和 $b$

图上路径最大边权最小问题，参考货车运输，考虑最小生成树 + $\operatorname{LCA}$

稍微给个证明：考虑反证，如果答案不落在最小生成树上，那么可以将这条边替换进最小生成树中。

再将修改考虑进去。

实际上就是在树上多填了一条边，考虑找出环，若新增的边更小，删去最大的边，并重新初始化倍增数组。

每部分的思路比较经典，是道缝合题，比较考验代码能力

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 5000, maxm = 1e5 + 5;
int n, m;
struct Map {
    struct node {
        int u, v, nex;
        int w, flag;
    }edge[maxm << 3];
    map < pair<int, int>, int > mapp;
    int head[maxm << 3], len;
    inline void make_map(int u, int v, int w, int flag) {
        len++;
        edge[len].nex = head[u];
        edge[len].u = u;
        edge[len].v = v;
        edge[len].w = w;
        edge[len].flag = flag;
        head[u] = len;
    }
}Tree, Mapp;
namespace MST {
    int Father[maxm];
    inline bool cmp(Map::node x, Map::node y) {
        return x.w < y.w;
    }
    inline int Find(int x) {
        if(Father[x] != x) return Father[x] = Find(Father[x]);
        return Father[x];
    }
    inline void Unnion(int x, int y) {
        int f1 = Find(x), f2 = Find(y);
        if(f1 != f2) Father[f2] = f1;
    }
    inline void Kruskal() {
        int tot = 0;
        for(register int i = 1; i <= m; ++i) {
            int u = Mapp.edge[i].u, v = Mapp.edge[i].v, w = Mapp.edge[i].w;
            if(Find(u) != Find(v)) {
                Unnion(u, v), tot++, Tree.make_map(u, v, w, 1), Tree.mapp[make_pair(u, v)] = Tree.len, Tree.make_map(v, u, w, 1), Tree.mapp[make_pair(v, u)] = Tree.len;
                if(tot == n - 1) break;
            }
        }
    }
    inline void Work() {
        for(register int i = 1; i <= n; ++i) Father[i] = i;
        sort(Mapp.edge + 1, Mapp.edge + m + 1, cmp);
        Kruskal();
    }
}
namespace LCA {
    int f[maxm][25], maxx[maxm][25], dep[maxm];
    int Lca, Maxx;
    inline void Deal_First(int x, int fa) {
        dep[x] = dep[fa] + 1;
        for(register int i = 1; i <= 20; ++i) {
            f[x][i] = f[f[x][i - 1]][i - 1];
            maxx[x][i] = max(maxx[x][i - 1], maxx[f[x][i - 1]][i - 1]);
        }
        for(register int i = Tree.head[x]; i; i = Tree.edge[i].nex) {
            int y = Tree.edge[i].v, z = Tree.edge[i].w, flag = Tree.edge[i].flag;
            if(y == fa || !flag) continue;
            f[y][0] = x, maxx[y][0] = z;
            Deal_First(y, x);
        }
    }
    inline void Get_Lca(int x, int y) {
        if(dep[x] < dep[y]) swap(x, y);
        Lca = Maxx = 0;
        for(register int i = 20; i >= 0; --i)
            if(dep[f[x][i]] >= dep[y]) Maxx = max(Maxx, maxx[x][i]), x = f[x][i];
        if(x == y) { Lca = x; return ;}
        for(register int i = 20; i >= 0; --i)
            if(f[x][i] != f[y][i]) Maxx = max(Maxx, max(maxx[x][i], maxx[y][i])), x = f[x][i], y = f[y][i];
        Lca = f[x][0], Maxx = max(Maxx, max(maxx[x][0], maxx[y][0]));
    }
    inline int Erase(int x, int y, int z) {
        Get_Lca(x, y);
        if(Maxx < z) return 0;
        int now = 0; Maxx = 0;
        while(x != Lca) {
            if(maxx[x][0] > Maxx) Maxx = maxx[x][0], now = x;
            x = f[x][0];
        }
        while(y != Lca) {
            if(maxx[y][0] > Maxx) Maxx = maxx[y][0], now = y;
            y = f[y][0];
        }
        return now;
    }
    inline void Work() {
        Deal_First(1, 0);
    }
}
namespace Solve {
    using LCA::Maxx; using LCA::Get_Lca; using LCA::Deal_First; using LCA::Erase; using LCA::f;
    inline bool Check(int x, int y) { return (x ^ y) != 0; }
    inline void Work() {
        int Q = read();
        while(Q--) {
            char s[15];
            scanf("%s", s);
            if(s[0] == 'a') {
                int u = read(), v = read(), q = read(), x = Erase(u, v, q);
                if(!x) continue;
                int y = f[x][0];
                Tree.edge[Tree.mapp[make_pair(x, y)]].flag = 0, Tree.edge[Tree.mapp[make_pair(y, x)]].flag = 0;
                Tree.make_map(u, v, q, 1), Tree.mapp[make_pair(u, v)] = Tree.len, Tree.make_map(v, u, q, 1), Tree.mapp[make_pair(v, u)] = Tree.len;
                Deal_First(1, 0);
            }
            else {
                int m1 = read(), m2 = read(), b1 = read(), b2 = read();
                Get_Lca(m1, m2); int M = Maxx;
                Get_Lca(b1, b2); int B = Maxx;
                if(Check(M, B)) printf("madoka\n");
                else printf("Baozika\n");
            }
        }
    }
}
signed main() {
//  freopen("tsm.in", "r", stdin);
//  freopen("tsm.out", "w", stdout);
    n = read(), m = read();
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        Mapp.make_map(u, v, w, 1);
    }
    MST::Work(), LCA::Work(), Solve::Work();
    return 0;
}

T2 ihp

经典结论

$\sum_{d\mid n}\varphi(d) = n$

所以此题的 $f(i)$ 就是 $\varphi(i)$

$\varphi$ 是个积性函数，所以可以直接线性筛 $\varphi$

至于剩下两个提答点，直接跑分解。

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 3e7 + 5;
int n;
int a[maxn], Phi[maxn], Vst[maxn], Prime[maxn], maxx, Ans, tot;
inline void Get_Phi() {
    Phi[1] = 1;
    for(register int i = 2; i <= maxx; ++i) {
        if(!Vst[i]) Prime[++tot] = i, Phi[i] = i - 1;
        for(register int j = 1; j <= tot && i * Prime[j] <= maxx; ++j) {
            Vst[i * Prime[j]] = 1;
            if(i % Prime[j] == 0) { Phi[i * Prime[j]] = Phi[i] * Prime[j]; break; }
            else Phi[i * Prime[j]] = Phi[i] * (Prime[j] - 1);
        }
    }
} 
signed main() {
//  freopen("ihp.in", "r", stdin);
//  freopen("ihp.out", "w", stdout);
    n = read();
    if(n == 5) { printf("21517525747423580"); return 0; }
    if(n == 3) { printf("525162079891401242"); return 0; }
    for(register int i = 1; i <= n; ++i) a[i] = read(), maxx = max(maxx, a[i]);
    Get_Phi();
    for(register int i = 1; i <= n; ++i) Ans += Phi[a[i]];
    printf("%lld\n", Ans);
    return 0;
}

T3 qmras

Solve1：SAM

最近学了下 $\operatorname{SAM}$ ，能解决大部分子串类字符串问题

此题就是个 $\operatorname{SAM}$ 板子，建出 $\operatorname{SAM}$ 后求出每个点 $\operatorname{endpos}$ 的集合大小，乘上每个点长度小于 $k$ 的本质不同子串数量

后者的计算方式： $\min(k, \operatorname{len}(x)) - \operatorname{len}(\operatorname{link}(x))$

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e6 + 5, mod = 998244353;
int n, k;
char s[maxn];
struct Map {
    int v, nex;
}edge[maxn << 1];
struct node {
    int link, len;
    int Ch[26];
}SAM[maxn];
int head[maxn], len;
int Siz[maxn], tot, Last, Answer;
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
inline void Init() { SAM[1].len = 0, Last = 1, SAM[1].link = 0, tot++; }
inline void Insert(int c) {
    int q = ++tot, p = Last; SAM[q].len = SAM[p].len + 1, Last = q, Siz[q] = 1;
    while(p && !SAM[p].Ch[c]) SAM[p].Ch[c] = q, p = SAM[p].link;
    if(!p) SAM[q].link = 1;
    else {
        int x = SAM[p].Ch[c];
        if(SAM[p].len + 1 == SAM[x].len) SAM[q].link = x;
        else {
            int y = ++tot; SAM[y].len = SAM[p].len + 1;
            SAM[y].link = SAM[x].link, SAM[q].link = SAM[x].link = y;
            memcpy(SAM[y].Ch, SAM[x].Ch, sizeof(SAM[x].Ch));
            while(p && SAM[p].Ch[c] == x) SAM[p].Ch[c] = y, p = SAM[p].link;
        }
    }
}
inline void Search(int x) {
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        Search(y);
        Siz[x] += Siz[y];
    }
    if(Siz[x] > 1) Answer = (Answer + (Siz[x] * (Siz[x] - 1) / 2) % mod * max(0ll, min(k, SAM[x].len) - SAM[SAM[x].link].len) % mod % mod) % mod;
}
signed main() {
//  freopen("qmras.in", "r", stdin);
//  freopen("qmras.out", "w", stdout);
    n = read(), k = read();
    scanf("%s", s), Init();
    for(register int i = 0; i < n; ++i) Insert(s[i] - 'a');
    for(register int i = 2; i <= tot; ++i) make_map(SAM[i].link, i);
    Search(1);
    printf("%lld\n", Answer);
    return 0;
}

Solve2：Hash

由于保证数据随机，考虑长度很长的相同串不可能出现，所以可以自己设置 $k$ 的取值，然后直接前缀 $\operatorname{hash}$ 做 $\operatorname{check}$ 即可。

最后调调 $k$ 就好了，大概20的样子就能过。

Solve3：Sa + RMQ

大概思路是利用 $\operatorname{SA}$ 的 $\operatorname{Height}$ 数组，再用 $\operatorname{RMQ}$ 维护一下区间最大（其实我也不是很清楚bushi）。

还是推荐学习 $\operatorname{SAM}$ ！！！