小白月赛91文字版题解

在此感谢牛客官方工作人员,验题人简单，讲题人和参与内测的所有朋友。

本场题中E、F的通过人数比较出乎意料(内测中反馈都说比较典，本来预测通过人数会比较多，悲)，其他题目符合预期。

视频讲解：Bilibili-牛客竞赛

A.Bingbong的化学世界

知识点：基础语法

由于输入数据已经固定，所以我们只需要找出不是'.'的位置就可以判断出是属于哪种“苯环”。

时间复杂度：

题解代码：

#include<bits/stdc++.h>
using namespace std;
char a[10][10];
int main() {
    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 7; j++) {
            cin >> a[i][j];
        }
    }
    if (a[3][6] != '.') cout << "o";
    else if (a[6][4] != '.') cout << "p";
    else cout << "m";
    return 0;
}

B.Bingbong的数数世界

知识点：博弈思维

可以发现，在操作最优情况下如果存在对方的数都应该选择消除。

而后手必胜的条件即最终态时刚好剩余两个偶数+两个奇数，这样才能在先手、后手依次操作完以后先手无法操作。由于所有卡牌已经是的排列，故只需要判断对取模的余数即可。

时间复杂度：

题解代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n % 4 == 0) {
            cout << "Bong" << '\n';
        } else {
            cout << "Bing" << '\n';
        }
    }
    return 0;
}

C.Bingbong的蛋仔世界

知识点：思维

由于每个位置允许多只蛋仔存在，所以每个蛋仔本质上是独立的，只需要考虑每个蛋仔能不能到达终点即可。

对于每一只蛋仔，我们只需要计算它到达终点的所需总时间能否小于所在行和列中砖块消失最长时间即可。

时间复杂度：

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    int fx = n / 2 + 1, fy = m / 2 + 1;
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        int time = abs(x - fx) + abs(y - fy);
        if (time < max(fx, fy)) ans++;
    }
    cout << ans;
    return 0;
}

D.Bingbong的奇偶世界

知识点：dp思维

我们可以分别考虑当一个数的结尾分别是的情况。

用记录所有满足条件的答案数量，用来记录前面可以形成的所有数的个数。

时：

我们发现此数可以接在前面的任意数的后面，且以为后导的数是满足条件的，并且这个不能作为前导,故可得：

时：

我们发现此数可以接在前面的任意数的后面，但不是满足条件的答案，故可得：

时：

我们发现此数可以接在前面的任意数的后面，是满足条件的答案,故可得：

最后再对各个部分取模即可。

时间复杂度：

代码：

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
const i64 mod = 1e9 + 7;
int main() {
    int n;
    cin >> n;
    vector<char>s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    i64 ans = 0, cnt = 0;;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0') {
            ans = (ans + cnt + 1) % mod;
            cnt = (cnt * 2) % mod;
        } else if ((s[i] - '0') & 1) {
            cnt = (cnt * 2 + 1) % mod;
        } else {
            ans = (ans + cnt + 1) % mod;
            cnt = (cnt * 2 + 1) % mod;
        }
    }
    cout << ans;
    return 0;
}

E.Bingbong的字符串世界

知识点：序列自动机

入手点是考虑对于任意为起点满足条件的字符串有多少个。

1.首先维护出对于任意的位置后面出现的字符为的位置，即。

2.然后对于第个位置，找出右边索引中满足存在子序列中的最小位置，然后再找出的最小位置。如果此时存在且那么此时的满足条件的字符串必然不可能存在。否则继续判断。

3.此时，我们需要讨论存在和不存在的情况。

当不存在时，需要加上满足长度大于等于且右索引不大于的字符串。

当存在时，需要加上满足长度大于等于且右索引不会大于等于的字符串。

由于此题细节较多，在代码中写出部分注释。

时间复杂度：

代码：

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
int Next_ACCEPT[6] = {1, 3, 3, 5, 16, 20,};
int Next_WA[2] = {23, 1};
int main() {
    i64 ans = 0;
    int n, k;
    cin >> n >> k;
    vector<char>s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    //序列自动机--维护第i个位置右边出现字符j的第一个位置
    vector<vector<int>>f(n + 2, vector<int>(27, -1));
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= 26; j++) {
            f[i][j] = f[i + 1][j];
        }
        f[i][s[i] - 64] = i;
    }
    //计算以当前i为左端点开始满足条件的子串的数目
    for (int i = 1; i <= n; i++) {
        int t1 = i;
        for (int j = 0; j < 6; j++) {
            if (j == 2 && s[t1] == 'C') t1 = f[t1 + 1][Next_ACCEPT[j]]; //防止一个C被判断两次
            else  t1 = f[t1][Next_ACCEPT[j]];
            if (t1 == -1) break;
        }
        if (t1 == -1) continue;
        int t2 = i;
        for (int j = 0; j < 2; j++) {
            t2 = f[t2][Next_WA[j]];
            if (t2 == -1) break;
        }
        if (t2 != -1 && t2 <= t1) continue;
        if (t2 == -1) {
            if (i + k - 1 > n) continue;
            else {
                ans = ans + n - max(i + k - 1, t1) + 1;
            }
        } else {
            if (i + k - 1 >= t2) continue;
            else {
                ans = ans + t2 - max(t1, i + k - 1);
            }

        }
    }
    cout << ans ;
    return 0;
}

F.Bingbong的幻想世界

知识点：位运算

首先暴力做法的做法必然超时，所以考虑更优解。

对于每一个数,我们可以考虑它对二进制位上的贡献。

考虑二进制枚举到第位,数组枚举到第个。

当二进制的第位是的时候，我们可以得出在区间中在二进制的第位上是的数所贡献的区间个数为个,且影响的区间个数为之后的个，所以贡献即为，又因为一个区间需要两两异或运算，所以对于一对和需要计算两遍,故总贡献为。

同理计算即可。

时间复杂度：

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
#define i64 long long
int main() {
    int n;
    cin >> n;
    vector<i64>a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    i64 ans = 0;
    for (int t = 0; t <= 20; t++) {
        i64 v0 = 0;
        i64 v1 = 0;
        for (int i = 1; i <= n; i++) {
            if ((a[i] >> t) & 1) {
                ans = (ans + v0 * (n - i + 1) % mod * (1 << t) % mod * 2 % mod) % mod;
                v1 = (v1 + i) % mod;
            } else {
                ans = (ans + v1 * (n - i + 1) % mod * (1 << t) % mod * 2 % mod) % mod;
                v0 = (v0 + i) % mod;
            }
        }
    }
    cout << ans ;
    return 0;
}

G.Bingbong的回文路径

知识点：

做法一：最近公共祖先，字符串哈希

做法二：后缀数组+树链分治

做法一：

.最近公共祖先，字符串哈希

:首先介绍一种比较不严谨的写法(因为字符串哈希本身带有哈希冲突)，但是比较好理解这题，考虑是小白月赛以学习为目的，所以没有卡这种做法(好像也不好卡)。

思路：首先我们需要预处理​的函数，以及到达第个结点时从上到下的幂次逐渐变高的数组和从上到下的幂次逐渐变低的数组的两种字符串哈希值。然后通过两点找到。令为 to ,为 to

当做为左串时，字符串为： to ,此时 使用数组的哈希值，使用数组的哈希值，然后减掉到根节点这部分多余的哈希值，再用逆元处理掉多余的的幂次，两个哈希值处理到对应的幂次后相加得到.

当做为左串时，可同上进行计算得到。

当此串为回文串时应该满足=。

(内测的佬说也可以不用逆元，倍增同时处理也可，可自行选择参考)

时间复杂度：

参考代码：(非唯一)

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
const int mod = 1e9 + 7;
const int P = 13331;
void solve() {
    int n;
    cin >> n;
    vector<char>a(n + 1); 
    vector<int>e[n + 1]; 
    vector<vector<int>>f(n + 1, vector<int>(32, 0)); 
    vector<i64>p(n + 1); 
    vector<i64>s(n + 1); 
    vector<i64>g(n + 1); 
    vector<int>d(n + 1, 1e9); 
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int fa;
        cin >> fa;
        e[fa].push_back(i);
        e[i].push_back(fa);
    }

    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P % mod;
    }

    auto bfs = [&](int root) {
        queue<int>q;
        q.push(root);
        d[root] = 0;
        s[root] = a[root];
        g[root] = a[root];
        while (!q.empty()) {
            auto t = q.front();
            q.pop();
            for (int i = 0; i < e[t].size(); i++) {
                int j = e[t][i];
                if (d[j] <= d[t] + 1) continue;
                d[j] = d[t] + 1;
                q.push(j);
                f[j][0] = t;
                for (int k = 1; k <= 31; k++) {
                    f[j][k] = f[f[j][k - 1]][k - 1];
                }
                s[j] = (s[t] + p[d[j]] * (a[j] - 0) % mod) % mod;
                g[j] = (g[t] * P % mod + a[j] - 0) % mod;

            }
        }
    };
    bfs(1);
    d[0] = -1;
    auto LCA = [&](int u, int v) ->int {
        if (d[u] < d[v])swap(u, v);
        for (int i = 31; i >= 0; i--) {
            if (d[f[u][i]] >= d[v]) {
                u = f[u][i];
            }
        }
        if (u == v) return u;
        for (int i = 31; i >= 0; i--) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i];
                v = f[v][i];
            }
        }
        u = f[u][0];
        v = f[u][0];
        return u;
    };
    auto ksm = [&](i64 a, i64 b) ->i64{
        i64 ans = 1;
        while (b) {
            if (b & 1) ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return ans;
    };
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        int fa = LCA(u, v);
        i64 p1 = (s[u] - s[fa] + mod) % mod;
        p1 = p1 * ksm(p[d[fa]], mod - 2) % mod;
        p1 = (p1 + a[fa]) % mod;
        p1 = (p1 * p[d[v] % mod - d[fa]] + mod) % mod;
        i64 p2 = (g[v] - g[fa] * p[d[v] - d[fa]] % mod + mod) % mod;
        i64 ans1 = (p1 + p2) % mod;
        p1 = 0, p2 = 0;
        p1 = (s[v] - s[fa] + mod) % mod;
        p1 = p1 * ksm(p[d[fa]], mod - 2) % mod;
        p1 = (p1 + a[fa]) % mod;
        p1 = (p1 * p[d[u] % mod - d[fa]] + mod) % mod;
        p2 = (g[u] - g[fa] * p[d[u] - d[fa]] % mod + mod) % mod;
        i64 ans2 = (p1 + p2) % mod;
        if (ans1 == ans2) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}
int main() {
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

做法二：

接下来介绍一种比较严谨的写法。

首先对此有根树轻重链分治，对每条链把它从上到下按顺序访问的节点的值和从下到上访问的值缝起来串到一个串里面，然后对缝起来后的串求后缀数组，此时便可以快速求两个后缀的，之后便可以快速对比两个链的某个区间，通过判断可得该路径是否满足回文串。

时间复杂度：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct graph {
    int head[N], nxt[N], to[N], cnt;
    inline graph(): cnt(1) {}
    inline void add(int u, int v) {
        nxt[++cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt;
    }
} gr;
char s[N];
int n, q, sz[N], son[N], top[N], father[N], dep[N], zidx[N], fidx[N], tmp[N];
bool vis[N];
char t[N << 1];
int len;
inline bool cmp(int x, int y) {
    return dep[x] > dep[y];
}
void dfs1(int u) {
    sz[u] = 1;
    dep[u] = dep[father[u]] + 1;
    for (int i = gr.head[u]; i; i = gr.nxt[i]) {
        int v = gr.to[i];
        dfs1(v);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
    }
}
void dfs2(int u) {
    if (son[u]) {
        top[son[u]] = top[u];
        dfs2(son[u]);
        for (int i = gr.head[u]; i; i = gr.nxt[i]) {
            int v = gr.to[i];
            if (v == son[u])continue;
            top[v] = v;
            dfs2(v);
        }
    }
}
int sa[N << 1], rak[N << 2], oldrak[N << 2], idx[N << 1], h[N << 1],
    cnt[N << 1];
void getsa() {
    int m = max(255, n);
    for (int i = 1; i <= len; i++) {
        cnt[t[i]]++;
        rak[i] = t[i];
    }
    for (int i = 1; i <= m; i++) {
        cnt[i] += cnt[i - 1];
    }
    for (int i = len; i >= 1; i--) {
        sa[cnt[rak[i]]--] = i;
    }
    for (int L = 1, p; L <= len; L <<= 1, m = p) {
        p = 0;
        for (int i = len; i + L > len; i--) {
            idx[++p] = i;
        }
        for (int i = 1; i <= len; i++) {
            if (sa[i] > L) {
                idx[++p] = sa[i] - L;
            }
        }
        memset(cnt, 0, (m + 1)*sizeof(int));
        for (int i = 1; i <= len; i++) {
            cnt[rak[i]]++;
        }
        for (int i = 1; i <= m; i++) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = len; i >= 1; i--) {
            sa[cnt[rak[idx[i]]]--] = idx[i];
        }
        memcpy(oldrak, rak, sizeof rak);
        p = 0;
        for (int i = 1; i <= len; i++) {
            if (oldrak[sa[i]] == oldrak[sa[i - 1]] &&
                    oldrak[sa[i] + L] == oldrak[sa[i - 1] + L]) {
                rak[sa[i]] = p;
            } else {
                rak[sa[i]] = ++p;
            }
        }
        if (p == len) {
            for (int i = 1; i <= len; i++) {
                sa[rak[i]] = i;
            }
            break;
        }
    }
    for (int i = 1, j = 0; i <= len; i++) {
        if (rak[i] == 1)continue;
        if (j)j--;
        while (t[i + j] == t[sa[rak[i] - 1] + j])j++;
        h[rak[i]] = j;
    }
}
struct node {
    int l, r;
    inline node(int l, int r): l(l), r(r) {}
};
vector<node> query(int x, int y) {
    vector<node> t0, t1;
    int xtag = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            xtag ^= 1;
            swap(x, y);
        }
        if (xtag == 0) {
            t0.push_back(node(fidx[x], fidx[top[x]]));
        } else {
            t1.push_back(node(zidx[top[x]], zidx[x]));
        }
        x = father[top[x]];
    }
    if (dep[x] < dep[y]) {
        xtag ^= 1;
        swap(x, y);
    }
    if (xtag == 0) {
        t0.push_back(node(fidx[x], fidx[y]));
    } else {
        t1.push_back(node(zidx[y], zidx[x]));
    }
    vector<node> ret = t0;
    for (int i = t1.size() - 1; i >= 0; i--) {
        ret.push_back(t1[i]);
    }
    return ret;
}
int min_h[19][N << 1], logv[N];
int query_min(int l, int r) {
    int v = logv[r - l + 1];
    return min(min_h[v][l], min_h[v][r - (1 << v) + 1]);
}
int calc(int i, int j) {
    if (i == j)return len - i + 1;
    i = rak[i];
    j = rak[j];
    if (i > j)swap(i, j);
    return query_min(i + 1, j);
}
bool check(const vector<node>& t1, const vector<node>& t2) {
    int i = 0;
    int j = 0;
    int x1 = 0, x2 = 0;
    while (i < t1.size() && j < t2.size()) {
        int len = min(t1[i].r - t1[i].l + 1 - x1, t2[j].r - t2[j].l + 1 - x2);
        if (calc(t1[i].l + x1, t2[j].l + x2) < len)return false;
        if (t1[i].l + x1 + len - 1 == t1[i].r && t2[j].l + x2 + len - 1 == t2[j].r) {
            i++;
            j++;
            x1 = 0;
            x2 = 0;
            continue;
        }
        if (t1[i].l + x1 + len - 1 == t1[i].r) {
            x2 += len;
            x1 = 0;
            i++;
        } else {
            x1 += len;
            x2 = 0;
            j++;
        }
    }
    return true;
}
int main() {
    cin >> n;
    cin >> (s + 1);
    for (int i = 1; i <= n; i++) {
        cin >> father[i];
        if (father[i]) {
            gr.add(father[i], i);
        }
    }
    top[1] = 1;
    dfs1(1);
    dfs2(1);
    for (int i = 1; i <= n; i++) {
        tmp[i] = i;
    }
    sort(tmp + 1, tmp + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        int x = tmp[i];
        if (vis[x])continue;
        vector<int> d;
        while (x != top[x]) {
            d.push_back(x);
            vis[x] = true;
            x = father[x];
        }
        vis[x] = true;
        d.push_back(x);
        for (int j = d.size() - 1; j >= 0; j--) {
            t[++len] = s[d[j]];
            zidx[d[j]] = len;
        }
        for (int j = 0; j < d.size(); j++) {
            t[++len] = s[d[j]];
            fidx[d[j]] = len;
        }
    }
    getsa();
    logv[0] = -1;
    for (int i = 1; i <= len; i++) {
        min_h[0][i] = h[i];
        logv[i] = logv[i >> 1] + 1;
    }
    for (int j = 1; j <= 18; j++) {
        for (int i = 1; i + (1 << j) - 1 <= len; i++) {
            min_h[j][i] = min(min_h[j - 1][i], min_h[j - 1][i + (1 << (j - 1))]);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        vector<node> t1 = query(x, y);
        vector<node> t2 = query(y, x);
        if (check(t1, t2)) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    }
    return 0;
}