2024牛客寒假算法基础集训营3

A 智乃与瞩目狸猫、幸运水母、月宫龙虾

第一个字母在忽略大小写相同输出 yes 否则 no

if (tolower(s[0]) == tolower(t[0])) {
    cout << "yes\n";
} else {
    cout << "no\n";
}

B 智乃的数字手串

有一个手串 (第 $N$ 个数字与第一个数字相邻)

两人轮流进行操作：

当且仅当某两个相邻数字的和为偶数时，可以拿走这两个相邻数字中的任意一个，取数后将剩下的数字按照它们之前的相对顺序重新紧凑排列
选择两个数字交换他们的值 (可以不交换)

如果最后手串只剩下一个了，则可以直接取走并赢得胜利。

若玩家不能进行取数操作，则该玩家失败输掉游戏。

现在 qcjj 先手取数，若两个人都采取最优策略，谁将获胜？

考虑游戏最终的结果，无论是谁不能取数，最终剩下的数字一定按照 $[奇, 偶, 奇, 偶, . . ., 奇, 偶]$ 排列，即长度为偶数。所以无论数字的内容是什么，两人的决策是什么，都不影响起始回合到终局回合的奇偶性。

if (n % 2) {
	cout << "qcjj\n";
} else {
	cout << "zn\n";
}

D/E/F chino's bubble sort and maximum subarray sum (easy)(hard)(very hard)

现在智乃有一个长度大小为 $N$ 的数组，数组中元素的值有正有负。她想要先进行恰好 $K$ 次相邻元素的交换操作，再求整个数组的最大子段和。她想要让最后求出的最大子段和尽可能的大，请你帮助智乃算出她最终可能的最大子段和有多大。

easy: $2 \leq n \leq 10^{3}, 0 \leq k \leq 1$
hard: $2 \leq n \leq 10^{3}, 0 \leq k \leq 100$
very hard: $2 \leq n \leq 10^{3}, 0 \leq k \leq 1000$

当 $k = 0$ 时，则求的是数组的最大字段和，

for (int l = 1;l <= n;l++) {
	for (int r = l;r <= n;r++) {
		ans = max(ans, pre[r] - pre[l - 1]);
	}
}

当 $k = 1$ 时，则在可以交换一次的前提下，数组的最大字段和。(PS：交换后记得还原)

for (int i = 2; i <= n; ++i) {
	swap(a[i], a[i - 1]);
	for (int k = 1; k <= n; ++k) {
		pre[k] = pre[k - 1] + a[k];
	}
	for (int l = 1; l <= n; ++l) {
		for (int r = l; r <= n; ++r) {
			ans = max(ans, pre[r] - pre[l - 1]);
		}
	}
	swap(a[i], a[i - 1]);
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1), pre(n + 1, 0);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    for (int i = 1;i <= n;i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    ll ans = -INTMAX_MAX;
    if (k == 0) {
        for (int l = 1;l <= n;l++) {
            for (int r = l;r <= n;r++) {
                ans = max(ans, pre[r] - pre[l - 1]);
            }
        }
    } else {
        for (int i = 2; i <= n; ++i) {
            swap(a[i], a[i - 1]);
            for (int k = 1; k <= n; ++k) {
                pre[k] = pre[k - 1] + a[k];
            }
            for (int l = 1; l <= n; ++l) {
                for (int r = l; r <= n; ++r) {
                    ans = max(ans, pre[r] - pre[l - 1]);
                }
            }
            swap(a[i], a[i - 1]);
        }
    }
    cout << ans << '\n';
}

L/M 智乃的 36 倍数 (easy)(normal)

定义运算 $f$ ，表示将两个正整数按照字面值从左到右拼接

智乃现在有一个大小为 $N$ 的正整数数组 $a$ ，第 $i$ 个元素为 $a_{i}$ ，现在他想选出两个正整数进行前后拼接，使得它们拼接后是一个 $36$ 的倍数，问智乃有多少种可行的方案。

她想要知道有多少对有序数对 $(i, j) (i \neq j)$ 满足 $f (a_{i}, a_{j})$ 是一个 $36$ 的倍数。

easy: $1 \leq N \leq 1000, 1 \leq a_{i} \leq 10$
normal: $1 \leq N \leq 10^{5}, 1 \leq a_{i} \leq 10^{18}$

$easy:$

法一：暴力枚举

stoi: 即 string to int

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i];
    }
    int cnt = 0;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (i != j) {
                string s = to_string(a[i]) + to_string(a[j]);
                int num = stoi(s);
                if (num % 36 == 0) {
                    cnt++;
                }
            }
        }
    }
    cout << cnt << '\n';
}

法二：只需要统计 36 72 108 即可。

void solve() {
    int n, x;
    cin >> n;
    vector<int> a(11);
    for (int i = 1;i <= n;++i) {
        cin >> x;
        a[x]++;
    }
    cout << a[3] * a[6] + a[7] * a[2] + a[10] * a[8] << '\n';
}

$normal:$

法一：可以考虑 36 实际上就是 4 的倍数和 9 的倍数

4 的倍数只要后两位可以被 4 整除即可。
9 的倍数只要所有数位和可以被 9 整除即可。

(待更 $\dots$ )

法二：根据模的性质，两个数字求和模 36 实际上就是每一部分分别模 36 求和后再模 36

即 $(a + b) % 36 = (a % 36 + b % 36) % 36$ ，

所以可以直接开桶统计每个数字模 36 后是几，然后 36 还有个特殊性质， $10^{k} % 36 = 28 (k \geq 2)$ 所以只需要知道它是不是 10 位数即可。

$f (j, i) = j \times 10^{k} + i$ ( $k$ 为 $i$ 的位数)

如果 $k \geq 2 (i \geq 10), j \times 10^{k} % 36 = j \times 28$
如果 $k = 1 (i < 10), j \times 10^{k} % 36 = j \times 10$

$f (j, i)$ 即 (j * (i < 10LL ? 10LL : 28LL) + i) $j$ 是 a[i] 中的元素 $mod 36$ 的结果， $i$ 是 a[i]， $s u m [i]$ 是代表 $a [i] % 36$ 结果相同的数量(证明这些数相差 36 的倍数，对结果不影响，在 $f (j, i) % 36$ 时会消掉，这些数就可以一起加上降低复杂度)

对于 a[i] 中的每个元素，遍历 $f (j, a [i])$ ,若被 36 整除加上

void solve() {
    int n;
    ll ans = 0;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    auto calc = [&]() {
        ll ans = 0;
        vector<ll> sum(36, 0);
        for (auto i : a) {
            for (int j = 0; j < 36; ++j) {
                if ((j * (i < 10LL ? 10LL : 28LL) + i) % 36 == 0) {
                    ans += sum[j];
                }
            }
            sum[i % 36]++;
        }
        return ans;
    };

    ans += calc();
    reverse(a.begin(), a.end());
    ans += calc();
    cout << ans << '\n';
}

代码没有怎么看懂，我主要是想预处理 $s u m [i]$ 数组，然后在两层循环中两层循环所对应的下标不能相同 (即不能和自己拼接)，这样就不用翻转数组再来一次了

void solve() {
    int n;
    ll ans = 0;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<ll> sum(36, 0);
    for (auto i : a) {
        sum[i % 36]++;
    }
    for (auto i : a) {
        --sum[i % 36];
        for (int j = 0; j < 36; ++j) {
            if ((j * (i < 10LL ? 10LL : 28LL) + i) % 36 == 0) {
                ans += sum[j];
            }
        }
        ++sum[i % 36];
    }

    cout << ans << '\n';
}

G/H 智乃的比较函数 (easy)(normal)

$c m p (x, y)$ :

$x < y, c m p (x, y) = 1$
$x \geq y, c m p (x, y) = 0$

有 $a_{1}, a_{2}, a_{3}$ 整型变量，给出 $N$ 组 $c m p (a_{x}, a_{y})$ 的值，问是否产生了矛盾。

easy: $1 \leq N \leq 2$
normal: $1 \leq N \leq 50$

$easy:$

void solve() {
    int n; cin >> n;
    bool ok = true;
    int xx, yy, zz, x, y, z;
    for (int i = 1;i <= n;i++) {
        cin >> x >> y >> z;
        if (i == 1) {
            xx = x, yy = y, zz = z;
        }
        if (x == y && z) {
            ok = false;
        }
    }
    if (n == 2) {
        if (xx == x && yy == y && zz != z) {
            ok = false;
        }
        if (xx == y && yy == x && zz == z) {
            if (z == 1) {
                ok = false;
            }
        }
    }
    if (ok) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

$normal:$

枚举 $a_{1}, a_{2}, a_{3} (1, 2, 3)$ 如果有满足 $z = 1 & & a [x] \geq a [y] ∣∣ z = 0 & & a [x] < a [y]$ ,则产生了矛盾。

只要找到符合条件的情况，则存在

感觉代码很简单，只是自己没有想到。

int i, j, k, n, m, t, a[1005];
vector<tuple<int, int, int> > v;
bool fuck() {
    for (auto [x, y, w] : v) {
        if (w == 1) {
            if (a[x] < a[y])continue;
            else return 0;
        } else {
            if (a[x] >= a[y])continue;
            else return 0;
        }
    }
    return 1;
}
void solve() {
    int n;
    cin >> n;
    while (n--) {
        cin >> i >> j >> k;
        v.push_back({ i,j,k });
    }
    int res = 0;
    for (i = 1;i <= 3;i++)
        for (j = 1;j <= 3;j++)
            for (k = 1;k <= 3;k++) {
                a[1] = i; a[2] = j; a[3] = k;
                int ans = 0;
                res |= fuck();
            }
    if (res)cout << "Yes\n";
    else cout << "No\n";
    v.clear();
}

(待更 $\dots$ )可以先暂时不补了，后面的都比较有难度，还是先去系统学习算法再来。

2024牛客寒假算法基础集训营3

A 智乃与瞩目狸猫、幸运水母、月宫龙虾

B 智乃的数字手串

D/E/F chino's bubble sort and maximum subarray sum (easy)(hard)(very hard)

L/M 智乃的 36 倍数 (easy)(normal)

$easy:$

$normal:$

G/H 智乃的比较函数 (easy)(normal)

$easy:$

$normal:$

J 智乃的相亲活动

C 智乃的前缀、后缀、回文

K 智乃的“黑红树”

I chino's infinite infinite strings without xyz