346

A - Adjacent Product

签到

void solve() {
    int n;cin >> n;vector<int> a(n);
    for (int i = 0;i < n;i++)cin >> a[i];
    for (int i = 0;i < n-1;i++) {
        cout << a[i] * a[i + 1] << " ";
    }
}

B - Piano

有一个无限长的钢琴键盘。在这个键盘中，是否存在一个由 $W$ 个白键和 $B$ 个黑键组成的连续部分？

假设 $S$ 是由无限重复的字符串 wbwbwwbwbwbw 构成的字符串。

在 $S$ 中，是否存在一个由 $W$ 次出现的 w 和 $B$ 次出现的 b 组成的子串？

什么是 $S$ 的子串？ $S$ 的子串是一个字符串，它可以由 $S$ 的 $l$ /th、 $(l + 1)$ /th、 $\dots$ 、 $r$ /th 字符按照一定的顺序连接而成，对于某个两个正整数 $l$ 和 $r$ 。 $(l \leq r)$ .

暴力即可

void solve() {
    int w, b;cin >> w >> b;
    string s = "wbwbwwbwbwbw";
    for (int i = 1;i <= 10;i++) {
        s += s;
        if (s.size() > 200)break;
    }
    for (int i = 0;i < s.size();i++) {
        for (int j = 1;j < s.size() - i;j++) {
            string ss = s.substr(i, j);
            if (count(ss.begin(), ss.end(), 'w') == w && count(ss.begin(), ss.end(), 'b') == b) {
                cout << "Yes\n";return;
            }
        }
    }
    cout << "No\n";
}

C - Σ

长度为 $N$ 的正整数序列 $A = (A_{1}, A 2, \dots, A_{N})$ 和一个正整数 $K$ 。

求 $1$ 与 $K$ 之间，不在序列 $A$ 中出现的整数之和。

#define int long long
void solve() {
    int n, k;cin >> n >> k;vector<int>a(n);
    map<int, int> mp;
    for (int i = 0;i < n;i++)cin >> a[i], mp[a[i]]++;
    int p = 0;
    for (auto [x, y] : mp) {
        if (x <= k)
            p += x;
    }
    int kk = (1 + k) * k / 2;
    cout << kk - p << '\n';
}

D - Gomamayo Sequence

给你一个长度为 $N$ 的字符串 $S$ ，它由 0 和 1 组成。

长度为 $N$ 的字符串 $T$ 由 0 和 1 组成，当且仅当它满足以下条件时，它是一个**好的字符串：

恰好有一个整数 $i$ 使得 $1 \leq i \leq N - 1$ 与 $T$ 中的 $i$ -3 和 $(i + 1)$ -3 字符相同。

对于每个 $i = 1, 2, \dots, N$ ，您可以选择是否执行一次下面的操作：

如果 $S$ 的 $i$ 个字符是 "0"，则将其替换为 "1"，反之亦然。如果执行此操作，代价为 $C_{i}$ 。

求使 $S$ 成为一个好字符串所需的最小总成本。

Solution

前缀后缀和

可以知道，除了 $i, i + 1$ 位是相同的，其他位均为 $01$ 交错的字符串。分为 $1010 \dots 00 | 11 \dots 1010 \dots$ 和 $0101. . .00 | 11 \dots 0101 \dots$ 两种情况，分别处理出前缀和后缀，则这时的答案为 $p r e [i] [0] + s u f [i + 1] [0]$ 或 $p r e [i] [1] + s u f [i + 1] [1]$ (分别代表第 $i, i + 1$ 位同时为 0 或 1 且其他位为 $01$ 交替字符串时所需的代价)，取最小值即可。

#define int long long
void solve() {
    int n;cin >> n;string s;cin >> s;vector<int> a(n + 1);s = ' ' + s;
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<array<int, 2>> f(n + 2), g(n + 2);
    for (int i = 1;i <= n;i++) {
        f[i][0] = f[i - 1][1] + (s[i] == '0' ? 0 : a[i]);
        f[i][1] = f[i - 1][0] + (s[i] == '1' ? 0 : a[i]);
    }
    int ans = 1e18;
    for (int i = n;i >= 2;i--) {
        g[i][0] = g[i + 1][1] + (s[i] == '0' ? 0 : a[i]);
        g[i][1] = g[i + 1][0] + (s[i] == '1' ? 0 : a[i]);
        ans = min(ans, f[i - 1][0] + g[i][0]);
        ans = min(ans, f[i - 1][1] + g[i][1]);
    }
    cout << ans << '\n';
}

E - Paint

有一个行数为 $H$ 列数为 $W$ 的网格。初始时，所有单元格都涂有颜色 $0$ 。

您将按照 $i = 1, 2, \dots, M$ 的顺序执行以下操作。

如果是 $T_{i} = 1$ ，则使用颜色 $X_{i}$ 重新绘制 $A_{i}$ /-th 行中的所有单元格。
如果是 $T_{i} = 2$ ，则用颜色 $X_{i}$ 重新绘制 $A_{i}$ /th 列中的所有单元格。

完成所有操作后，针对网格中存在的每种颜色 $i$ ，找出被涂上颜色 $i$ 的单元格数量。

Solution

逆向思维

从后往前遍历，就不需要讨论的非常复杂，且后面的一定是最终的，不用担心被覆盖的问题。

#define int long long
void solve() {
    int n, m, q;cin >> n >> m >> q;
    vector<int> t(q + 1), a(q + 1), x(q + 1), visn(n + 1), vism(m + 1);
    for (int i = 1;i <= q;i++) {
        cin >> t[i] >> a[i] >> x[i];
    }
    int n1 = n, m1 = m;
    vector<int> cnt(2e5 + 1);
    for (int i = q;i >= 1;i--) {
        if (t[i] == 1) {
            if (!visn[a[i]]) {
                n1--;
                visn[a[i]] = 1;
                cnt[x[i]] += m1;
            }
        } else {
            if (!vism[a[i]]) {
                m1--;
                vism[a[i]] = 1;
                cnt[x[i]] += n1;
            }
        }
    }
    cnt[0] += n1 * m1;
    vector<pair<int, int>> ans;
    for (int i = 0;i <= 2e5;i++) {
        if (cnt[i]) {
            ans.push_back({i,cnt[i]});
        }
    }
    cout << ans.size() << '\n';
    for (auto [x, y] : ans)cout << x << " " << y << '\n';
}

F - SSttrriinngg in StringString

对于长度为 $n$ 的字符串 $X$ ，我们用 $f (X, k)$ 表示重复 $k$ 次字符串 $X$ 得到的字符串，用 $g (X, k)$ 表示重复 $k$ 次 $X$ 的第一个字符、第二个字符，直到第 $n$ 个字符得到的字符串。

例如，如果 $X =$ abc，那么 $f (X, 2) =$ abcabc， $g (X, 3) =$ aaabbbccc。同时，对于任意字符串 $X$ ， $f (X, 0)$ 和 $g (X, 0)$ 都是空字符串。

给定正整数 $N$ 以及字符串 $S$ 和 $T$ 。找出最大的非负整数 $k$ ，满足 $g (T, k)$ 是 $f (S, N)$ 的一个（不一定连续的）子序列。

$g (T, 0)$ 始终是 $f (S, N)$ 的子序列。

$(n \leq 10^{12}, 1 \leq∣ s ∣, ∣ t ∣\leq 10^{5})$

Solution

二分+贪心

官方题解

固定 k 并考虑如何确定 g (T，k)是否为 f (S，N)的子串。

让 s 为 S 的长度，t 为 T 的长度， $X [: i]$ 表示字符串 X 的前 i 个字符。T 中的每个字符也包含在 S 中（否则，答案显然为0）。

让我们依次找到以下值，以 i=1,2，...，t 的顺序：

${iter}_{i}$ ：最小的 j，使得 $g (T [: i], k)$ 是 $f (S, N) [: j]$ 的子串。

最终，通过比较从 N×s 得到的 ${iter}_{t}$ ，我们得到答案。根据 ${iter}_{i}$ 找到 ${iter}_{i + 1}$ 相当于找出 T 的第（i+1）个字符在 f (S，N)的第（ ${iter}_{i} + 1$ ）个字符（包括它自己）之后的第 k 次出现的位置，因此这个问题可以归结为处理以下查询 k 次：

$query (a, b, c)$ ：给定正整数 a 和 b 以及字符 c，在 f (S，N)的第 a 个字符（包括它自己）之后，找到字符 c 的第 b 次出现的位置。

假设 c 在 S 中出现了 ${cnt}_{c}$ 次。如果 a 大于 s，则通过 $query (a, b, c) = query (a - s, b, c) + s$ 将其简化为 a≤s 的情况。如果 b 大于 ${cnt}_{c}$ ，则通过 $query (a, b, c) = query (a + s, b - {cnt}_{c}, c)$ 将其简化为 b≤ ${cnt}_{c}$ 的情况。

因此，只需处理满足条件 a≤s，b≤ ${cnt}_{c}$ 的查询。如果满足这些条件，则 $query (a, b, c)$ 的答案不大于 2 s。通过为每个字符预先计算其在 f (S，2)中出现的位置，可以快速处理查询。

因此，包括最初提到的对 k 的二进制搜索，问题可以在总共 $O (s σ + t \log N s)$ 或 $O (s + σ + t \log s \log N s)$ 的时间内解决（其中 $σ$ 为字母表的大小）。

(待更 $\dots$ )

$a [i] [j]$ 代表的是字符串取前 $i$ 个字符中的各字母个数。

$x - 1$ 的原因是当刚好整除的时候，会进位一位，到时候 z 记录的就是下一个周期的相应字符下标了，但是实际上应该记录的是上一个周期该字母的最后一个位置

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 200005;

char s[N], t[N];
int a[N][26];
vector<int> b[26];
int main() {
    LL n;
    scanf("%lld%s%s", &n, s + 1, t + 1);
    int m = strlen(s + 1);
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < 26; j++) a[i][j] = a[i - 1][j];
        a[i][s[i] - 'a']++;
        b[s[i] - 'a'].push_back(i);
    }
    LL l = 1, r = 1e17 + 500;
    while (l < r) {
        LL mid = l + r >> 1;
        LL k = 0, z = 0;
        int ok = 0;
        for (int i = 1; t[i] && k < n; i++) {
            int c = a[m][t[i] - 'a'];//在s字符串中这个字母的个数<->int c = b[t[i] - 'a'].size();
            if (c == 0) {//若没有这个字符，则直接结束(这个mid作为答案不符合要求，答案应该更小)
                k = n;break;
            }
            LL x = a[z][t[i] - 'a'] + mid;
            k += (x - 1) / c;
            x = (x - 1) % c + 1;
            z = b[t[i] - 'a'][x - 1];//记录在满足条件的最后一个周期中的下标
        }
        if (k >= n)
        //若已经经过超过了n轮，还没能将t字符串走完，则证明无法满足要求，这种二分的目标是找出第一个满足k>=n的下标
            r = mid;
        else
            l = mid + 1;
    }
    printf("%lld\n", l - 1);
    return 0;
}