A: CCA的数列

分析

签到题, 依照题意模拟即可. 只不过我写的等比数列有精度错误, 换成 $a*b = c*d$ 的形式就过了.

时间复杂度: $O(n)$

代码实现

#include <cstdio>

const int N = 1e5;

int n;
long long A[N + 5];

int main() {
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) scanf ("%lld", &A[i]);

    long long a = A[2] - A[1];
    long long c = A[2] % A[1];
    bool F1, F2, F3;
    F1 = F2 = F3 = true;
    for (int i = 3; i <= n; ++i) {
        if (A[i] - A[i - 1] != a) F1 = false;
        if (A[i] * A[1] != A[i - 1] * A[2]) F2 = false;
        if (A[i] % A[i - 1] != c) F3 = false;

    } if (F1 || F2 || F3) printf ("YES\n");
    else printf ("NO\n");
    return 0;
}

B: CCA的字符串

分析

闲话: 第一眼以为是 $SAM$ 板子, 看了看数据范围可以用 $KMP$ . 紧接着发现模式串长度仅为 $8$ ......果然我还是太 $naive$ 了.

可以自然地想到这样一种做法:

找到每一个字符串中的 "NowCoder"
尝试将左右端点向两边扩展.

但是这样做有点麻烦, 因为会算重.

原因在于位置不同的两个 "NowCoder" 有可能扩展出相同的左右端点.

容斥? 不需要. 对于每一个合法的串, 只在其包含的最后一个 "NowCoder" 处计算它的贡献.

也就是说, 计算包含第 $i$ 个 "NowCoder" 的串时, 右端点最远只能到第 $i + 1$ 个 "NowCoder" 的 "e" 处. (即不能包含它)

时间复杂度: $O(8n)$

代码实现

#include <cstdio>
#include <cstring>

const int N = 1e5;

int Len;
char Str[N + 5];
char T[N + 5];

int S[N + 5], nL;

int main() {
    scanf ("%s", Str + 1);
    Len = strlen (Str + 1);
    T[1] = 'N', T[2] = 'o', T[3] = 'w', T[4] = 'C', T[5] = 'o', T[6] = 'd', T[7] = 'e', T[8] = 'r';


    for (int i = 1; i <= Len - 7; ++i) {
        bool Flag = true;
        for (int j = 1; j <= 8; ++j)
            if (Str[i + j - 1] != T[j]) Flag = false;
        if (Flag) S[++nL] = i;

    } long long Ans = 0;
    for (int i = 1; i <= Len; ++i) {
        int R = (i == nL)? Len : (S[i + 1] + 6);
        Ans += 1LL * S[i] * (R - (S[i] + 8 - 1) + 1);
    } printf ("%lld\n", Ans);
    return 0;
}

C: CCA的矩阵

分析

如果锤子是方方正正的话, 这题就是一个裸的二维前缀和. 现在是斜着锤, 但还是可以往这个方面想.

画个图想想如何二维前缀和, 发现实际上只要维护一些倒三角形就行了. 其实本质上还是个二维前缀和, 只不过形状变了下而已.

时间复杂度: $O(n^2k)$

代码实现

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int N = 2e3;

int n, K;
int Map[N + 5][N + 5];

LL S[N + 5][N + 5];

int main() {
    scanf ("%d%d", &n, &K);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) scanf ("%d", &Map[i][j]);

    for (int i = 1; i <= n; ++i) {
        S[i][0] = S[i - 1][1];
        S[i][n + 1] = S[i - 1][n];
        for (int j = 1; j <= n; ++j) {
            S[i][j] = Map[i][j] + Map[i - 1][j] + S[i - 1][j - 1] + S[i - 1][j + 1];
            if (i - 2 >= 0) S[i][j] -= S[i - 2][j];
        }
    } LL Ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            int X1 = i - (2 * K - 1) + 1, Y1 = j;
            int X2 = i - K + 1, Y2 = j - K + 1;
            int X3 = i - K + 1, Y3 = j + K - 1;
            if (X1 < 1 || X2 < 1 || Y2 < 1 || X3 < 1 || Y3 > n) continue;
            LL tap = S[i][j] - S[X2][Y2] - S[X3][Y3] + S[X1][Y1] + Map[X1][Y1];
            for (int p = 2; p <= K; ++p) tap += Map[X1 + p - 1][Y1 - (p - 1)] + Map[X1 + p - 1][Y1 + (p - 1)];
            Ans = std::max (Ans, tap);
        }
    printf ("%lld\n", Ans);
    return 0;
}

D: CCA的图

分析

本场考试最好想的题. 没有之一.

读完题目, 实际上有两个子问题:

找出 $L_{max}$
找出 $R_{min}$

解决问题 $1$ 的时候实际上有条件 $R = w_{max}$ . 把 $w_i$ 从大到小排序, 跑一遍 $Kruskal$ , 到 $S$ 与 $T$ 首次连通时退出. 最后一条边的 $w$ 即为 $L_{max}$ .

考虑问题 $2$ , 首先把 $w_i > L_{max}$ 的边弄出来, 把 $w_i$ 从小到大排序. 跑一遍 $Kruskal$ , 到 $S$ 与 $T$ 首次连通时退出. 最后一条边的 $w$ 即为 $R_{min}$ .

完了? 完了.

代码实现

#include <cstdio>
#include <algorithm>

const int N = 1e6;
const int M = 3e6;

int n, m, S, T;

int mL;
struct Edge { int u, v, w; } E[M + 5], Ed[M + 5];
int Fa[N + 5];

int AnsL, AnsR;

bool Cmp1 (Edge, Edge);
bool Cmp2 (Edge, Edge);
int Kruskal1();
int Kruskal2();
int Find (int);

int main() {
    scanf ("%d%d%d%d", &n, &m, &S, &T);
    for (int i = 1; i <= m; ++i) scanf ("%d%d%d", &E[i].u, &E[i].v, &E[i].w);

    std::sort (E + 1, E + 1 + m, Cmp1);
    AnsL = Kruskal1();
    std::sort (Ed + 1, Ed + 1 + mL, Cmp2);
    AnsR = Kruskal2();
    printf ("%d %d\n", AnsL, AnsR);
    return 0;

} bool Cmp1 (Edge X, Edge Y) {
    return X.w > Y.w;

} bool Cmp2 (Edge X, Edge Y) {
    return X.w < Y.w;

} int Find (int p) {
    if (p == Fa[p]) return p;
    else return Fa[p] = Find (Fa[p]);

} int Kruskal1() {
    for (int i = 1; i <= n; ++i) Fa[i] = i;

    for (int i = 1; i <= m; ++i) {
        Fa[Find (E[i].u)] = Find (E[i].v);
        Ed[++mL] = E[i];
        if (Find (S) == Find (T)) return E[i].w;
    } return 0;
} int Kruskal2() {
    for (int i = 1; i <= n; ++i) Fa[i] = i;

    for (int i = 1; i <= mL; ++i) {
        Fa[Find (Ed[i].u)] = Find (Ed[i].v);
        if (Find (S) == Find (T)) return Ed[i].w;
    } return 0;
}

牛客练习赛74 A-D 简要题解

A: CCA的数列

分析

代码实现

B: CCA的字符串

分析

代码实现

C: CCA的矩阵

分析

代码实现

D: CCA的图

分析

代码实现