墨染空

2020-12-21 05:58 已编辑一昔如环昔昔都成玦量化分析

关注

牛客练习赛74题解

CCA的数列

https://ac.nowcoder.com/acm/contest/9700/A

我太神必了，B 炸了 $1$ 次，C 炸了 $5$ 次，DEF 一遍过。

不过第一次 AK 练习赛，还是比较激动的吧qwq。

A. CCA的数列

根据题意判断一下即可。

注意模和等比不能 $= 0$ 的特判。

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

int n, a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    int b = a[2] - a[1];
    bool ok = true;
    for (int i = 3; i <= n; i++) {
        if (a[i] - a[i - 1] != b) {
            ok = false;
        }
    }
    if (ok) {
        puts("YES");
        return 0;
    }
    if (a[1] != 0) {
        ok = true;
        for (int i = 3; i <= n; i++) {
            if (a[i] == 0 || a[i - 1] == 0) {
                ok = false;
                break;
            }
            if ((LL)a[1] * a[i] != (LL)a[2] * a[i - 1]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            puts("YES");
            return 0;
        }
    }
    if (a[1] != 0) {
        ok = true;
        int t = a[2] % a[1];
        for (int i = 3; i <= n; i++) {
            if (a[i - 1] == 0) {
                ok = false;
                break;
            }
            if ((LL)t != (LL)a[i] % a[i - 1]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            puts("YES");
            return 0;
        }
    }
    puts("NO");
}

B. CCA的字符串

考虑代表元计数法，把每个子串的贡献记录在最靠左的 NowCoder 上。

设 $[i, i + 7]$ 这一段是 NowCoder， $last$ 为上一个 NowCoder 左端点的位置，可取的左端点范围是 $[last + 1, i]$ ，右端点是 $[i + 7, n]$ ，对答案的贡献即 $(i - last) \times (n - (i + 7) + 1)$ 。

时间复杂度线性（带个 8 的常数 /kk）

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

typedef long long LL;

const int N = 1e5 + 5;

int n;

LL ans;

char a[N];

int main() {
    scanf("%s", a + 1);
    n = strlen(a + 1);
    int last = 0;
    for (int i = 1; i <= n; i++) {
        if (i + 7 <= n && a[i] == 'N' && a[i + 1] == 'o' && a[i + 2] == 'w' && a[i + 3] == 'C' && a[i + 4] == 'o' && a[i + 5] == 'd' && a[i + 6] == 'e' && a[i + 7] == 'r') {
            ans += (i - last) * (n - (i + 7) + 1ll);
            last = i;
        }
    }
    printf("%lld\n", ans);
}

C. CCA的矩阵

本来想写个斜着的差分，但是 WA 了五次，后来发现中间有一段空缺不知道咋处理www。

后来换了一个写法，如果把这个网格斜着看，这个锤子的区域是 $k$ 个长度为 $k$ 的序列 $+$ $k - 1$ 个长度为 $k - 1$ 的序列，我想先把这个区域按照左上-右下这个线来划分，考虑记两个数组 $a, b$ 分别代表向左上角延伸 $k$ 、 $k - 1$ 个格子的权值和。

然后再设 $c$ 为向右上延伸 $k$ 个 $a$ 的权值以及夹住的 $k - 1$ 个 $b$ 的权值和。

以上所有东西都可以 $O(n^2)$ 一遍递推出来。

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

typedef long long LL;

const int N = 2105;

typedef long long LL;

int n, K;
LL s[N][N], a[N][N], b[N][N], c[N][N];

LL ans;

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%lld", &s[i][j]);
        }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = s[i][j] + a[i - 1][j - 1];
            if (i > K && j > K) a[i][j] -= s[i - K][j - K];
            b[i][j] = s[i][j] + b[i - 1][j - 1];
            if (i > K - 1 && j > K - 1) b[i][j] -= s[i - K + 1][j - K + 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            c[i][j] = c[i - 1][j + 1] + a[i][j] + b[i - 1][j] - a[i - K][j + K] - b[i - K][j + K - 1];
            if (j + K - 1 <= n && j - K + 1 >= 1 && i - (2 * K - 1) + 1 >= 1) {
                ans = max(ans, c[i][j]);
            }
        }
    }
    printf("%lld\n", ans);
}

D. CCA的图

先找到 $L$ ，即按照标记从大到小排序加入边，使 $s, t$ 变为联通的时刻对应的标记。

用并查集维护连通性即可。

然后找 $R$ 方法同找 $L$ 。

时间复杂度 $O(m \log m + m \log n)$ 。

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

typedef long long LL;

const int N = 3e6 + 5, M = 3e6 + 5;

int n, m, s, t, L, R, f[N];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

void inline merge(int x, int y) {
    f[find(x)] = find(y);
}

struct E{
    int a, b, c;
    bool operator < (const E &b) const {
        return c < b.c;
    }
} e[M];

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    sort(e + 1, e + 1 + m);
    int p;
    for (int i = m; i; i --) {
        merge(e[i].a, e[i].b);
        if (find(s) == find(t)) {
            p = i, L = e[i].c;
            break;
        }
    }
    while (p > 1 && e[p - 1].c == L) p--;
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = p; i <= m; i++) {
        merge(e[i].a, e[i].b);
        if (find(s) == find(t)) {
            R = e[i].c;
            break;
        }
    }
    printf("%d %d\n", L, R);
}

E. CCA的期望

发现可以把黑色点个数期望拆成每个点的概率，每个点之间独立。

形式化的，设 $p_i$ 为 $i$ 编号的点经过 $k$ 次成为黑色点的概率。

$\text{Ans} = \displaystyle \sum_{i=1}^n p_i$

。

然后只要考虑算 $p$ 就好了。

我们可以先枚举 $i$ ，如果原来就是黑点那么直接 $+1$ 就好了，白点的情况，设 $a$ 为一次选择使 $i$ 成为黑点的概率，这个可以在 $O(n^3)$ 的 Floyd 预处理后，用 $O(n^2)$ 的复杂度枚举两个选择的点 $u, v$ ， $i$ 在一条 $u, v$ 的最短路上即等价于 $d_{u, v} = d_{u, i} + d_{i, v}$ 。

然后即求 $K$ 次至少有一次选 $a$ 的概率，其实可以考虑反向求没选的，然后减一下。因此就是 $1 - (1 - a)^K$ ，加入答案即可。

考场 sb 了写了个简单的 DP + 矩阵快速幂优化。

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

typedef long long LL;

const int N = 505, P = 1023694381;

int n, m, K, a[N], ans;

LL d[N][N];

int inline power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % P;
        a = (LL)a * a % P;
        b >>= 1;
    }
    return res;
}


int main() {
    memset(d, 0x3f, sizeof d);
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), d[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        d[u][v] = d[v][u] = min(d[u][v], (LL)w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            (ans += 1) %= P;
            continue;
        }
        int s = 0, cur = 0;
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                if (u == v) continue;
                s++;
                if (d[u][v] == d[u][i] + d[i][v]) cur++;
            }
        }
        int p = (LL)(s - cur) * power(s, P - 2) % P;
        ans = (ans + 1ll + P - power(p, K)) % P;
    }
    printf("%d\n", ans);
}

F. CCA的树

Cayley 定理： $n$ 个点的有标号无根树形态有 $n ^ {n - 2}$ 种。

然后那个分母就有了（然而我做到最后发现根本不用知道这个东西，因为可以消掉）。

考虑算所有形态染色方案数之和。

$\ge 1$ 个好链这种不好求，转化成总数 $-$ 没有好链的。

总数即随便染色 $n^{n - 2} \times m^n$ 。

考虑何种情况下没有好链，发现没有好链等价于在这颗树中，要么每种颜色的出现次数 $\le 1$ ，要么所有颜色相同的点都仅仅的靠拢在一起，即每个颜色聚拢成一个联通块。

因此对于每种形态的树而言，我们可以枚举断开的边数 $0 \le i \le n - 1$ ，选 $i$ 条边 $C_{n -1}^{i}$ 。考虑给 $i+1$ 个联通块染色 $C_{m, i + 1} \times (i+1)!$ 。注意这里的联通块，边本身没有编号的含义，但我们为了区分他，可以人为随便进行编号。因此贡献是：$ $C_{n -1}^{i} \times C_{m, i + 1} \times (i+1)!$ $

通过上段，我们发现每种形态对应方案数（总数和不合法数）是一样的，这个期望是唬我们的。

我们可以 $O(n)$ 预处理阶乘及其逆元， $O(n)$ 枚举断边。

因此总复杂度 $O(n)$ 。

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

typedef long long LL;

const int N = 1e7 + 5, P = 1023694381;

int n, m, L, fact[N], infact[N];

int inline power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % P;
        a = (LL)a * a % P;
        b >>= 1;
    }
    return res;
}

int inline C(int a, int b) {

    return (LL)fact[a] * infact[b] % P * infact[a - b] % P;
}


int main() {
    scanf("%d%d", &n, &m); L = max(n, m);
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= L; i++) fact[i] = (LL)fact[i - 1] * i % P;
    infact[L] = power(fact[L], P - 2);
    for (int i = L - 1; i; i--) infact[i] = (LL)infact[i + 1] * (i + 1) % P;
    int x = power(m, n) % P;
    for (int i = 0; i <= n - 1; i++) {
        if (i + 1 > m) continue;
        x = ((LL)x + P - (LL)C(n - 1, i) * C(m, i + 1) % P * fact[i + 1] % P) % P;
    }



    printf("%d\n", x);
}