A. SA.算一算 Ⅰ

Description

Y 老是惦记着同学们的“美丽值”，现在，他又玩出了新花样。

他想从 $n$ 个同学里选出若干个同学，使得他们的美丽值之和恰好为 $s$。

请问聪明的你，有多少种不同的选法？

Format

Input

第一行两个整数 $n, s$ 表示同学数量和美丽值之和。

第二行 $n$ 个整数 $a_i$ 用空格隔开表示每个同学的美丽值。

Output

一行一个整数表示答案。

Samples

输入样例 1

1 2	3 19260817 1 1 1

输出样例 1

输入样例 2

1 2	7 10 1 3 4 2 8 1 9

输出样例 2

Limitation

$1 \leq n \leq 24, 1 \leq a_i, s \leq 10^9$

思路与题解

$dfs$ 模板题

#include <iostream>
#include <vector>
using namespace std;

int ans = 0;
int n, s;
vector<int> v;

void dfs(int idx, int sum) {
    if (idx == n) {
        if (sum == s && sum != 0) ans++;
        return;
    }
    dfs(idx + 1, sum);
    dfs(idx + 1, sum + v[idx]);
}

int main() {
    cin >> n >> s;
    v.resize(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

B. 序列延中与后缀查询

Description

有一个初始为空的序列 $A$，在题目描述中，我们用 $a_i$ 表示 $A$ 中的第 $i$ 个数字。

你需要支持以下两种操作：

延中：在序列 $A$ 的尾部添加一个数 $x$（形式化来说，假设当前 $A$ 中有 $m$ 个数，添加之后则有 $m + 1$ 个数，且 $a_{m+1} = x$）。
查询：询问当前序列 $A$ 最后的 $k$ 个数字，最大的数是多少（形式化来说，假设当前 $A$ 中有 $m$ 个数，即询问 $\max\{a_i \mid m - k + 1 \leq i \leq m\}$ 的值）。

为了帮助你在线处理询问，输入数据进行了解密。你需要维护一个值 $lastans$（初始值为 0），表示上一次询问操作的答案，并且需要使用 $lastans$ 来解密出真正的操作内容。具体细节可以查看输入格式。

Input Format

第一行，一个整数 $n$，表示操作的次数。

接下来 $n$ 行，每行输入两个加密后的整数 $a, b$。

你需要用 $lastans$ 解密得到 $op, v$，规则为： $op = lastans \oplus a$ $v = lastans \oplus b$ （其中 $\oplus$ 表示按位异或运算，即 C++ 的 ^ 运算符）

如果 $op = 1$，那么执行延中操作，在序列 $A$ 尾部添加一个 $v$。
如果 $op = 2$，那么执行查询操作，询问序列 $A$ 最后的 $v$ 个数中，最大的数是多少，并且你需要在求解出这个答案之后，用此答案更新 $lastans$，以确保之后的操作能够正确解密。

输入保证第一个操作一定是延中操作，且 $op = 2$ 时，$v$ 不会超过此时序列 $A$ 的长度。

Output Format

为了减少输出文件的大小，你并不需要按照顺序输出所有询问的答案，你只需要输出一个值，表示所有询问的答案的和即可（请注意数据范围大小）。

Samples

样例输入 #1

样例输出 #1

数据范围与提示

【样例解释】

首先进行了 3 次延中操作，使得序列 $A = [2, 3, 1]$，然后第四次操作询问了后 3 个数字的最大值，答案应当为 3，于是第五次操作最后是询问后 1 个数字的最大值，答案为 1，然后第六次操作最后是询问后 2 个数字的最大值，答案应当为 3，所以最后输出 $3 + 1 + 3 = 7$。

【数据范围】

对于 100% 的测试数据满足 $n \leq 10^8, 1 \leq op < 2, 1 \leq v \leq 10^9$。

输入保证第一个操作一定是延中操作，且 $op = 2$ 时，$v$ 不会超过此时序列 $A$ 的长度。

请注意该数据的效率。

思路与题解

类似于单调队列求大小为 $k$ 的滑动窗口的求法，维护一个单调递减的队列记录角标，但是不 $pop()$ 元素，采用二分法（这里调用 $lower bound$ 函数确定后 $k$ 个元素中最大元素位置）

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    vector<int> v;
    vector<int> dq;

    cin >> n;

    int a, b;
    long long lastans = 0;
    long long ans = 0;
    int curSize = 0;
    while (n--) {
        cin >> a >> b;
        int op = a ^ lastans;
        int val = b ^ lastans;

        if (op == 1) {
            v.push_back(val);
            while (!dq.empty() && v[dq.back()] < val) {
                dq.pop_back();
            }
            dq.push_back(curSize);
            curSize++;
        } else if (op == 2) {
            int start = curSize - val;
            int idx = *lower_bound(dq.begin(), dq.end(), start);
            lastans = v[idx];
            ans += lastans;
        }
    }
    cout << ans;
    return 0;
}

C. 快速幂

Description

给定 $n, m$，求 $n^m \mod (10^9 + 7)$。

如有不理解可查阅资料。

Format

Input

一行两个整数 $n, m$。

Output

一行输出 $n^m \mod (10^9 + 7)$。

Samples

输入样例

3 2

输出样例

Limitation

$1 \leq n, m \leq 10^9$

思路与题解

板子题

#include <iostream>

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

ll quick_pow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ll n,m;
    cin >> n >> m;
    cout << quick_pow(n, m, MOD) << endl;
    return 0;
}

D. 本质不同子串计数

Description

给出一个字符串 $S$，请你统计其中本质不同的子串个数。

例如：如果 $S = \text{aba}$，那么它有 6 个子串：
a, b, a, ab, ba, aba。
但是，本质不同的子串只有 a, b, ab, ba, aba 这 5 种。

Format

Input

第一行，一个字符串 $S$。

Output

输出一行，一个整数表示 $S$ 的本质不同的子串个数。

Samples

样例输入 #1

aba

样例输出 #1

样例输入 #2

george

样例输出 #2

数据范围与提示

$|S| \leq 2000$，输入字符串均由小写字母组成。

思路与题解

采用 $Z$ 函数（扩展 $KMP$）

利用动态规划的思路，每次增加一个字符时，不考虑重复，都增加了字符串长度的子串个数，我们只需要找到重复的子串有多少个即可

把这个字符串倒过来，只需要考虑该字符串子串和该字符串最长公共前缀即可

这就是 $Z$ 函数定义，$Z$ 函数实现参照 Z 函数（扩展 KMP） - OI Wiki

有趣的是，这道题如果直接用 $KMP$ 中的 $\pi$ 数组（下称为 $\pi$）的求法直接代替 $Z$ 函数的函数调用得到的结果是正确的，其实这是因为 $max\\{\pi[i]\\}=max\\{z[i]\\}$，下面给出证明

考虑一个字符串 $s[0,...,n-1]$

我们不妨设 $k=max\\{z[i]\\}$，设 $j$ 是出现最大 $z[i]$ 的位置，根据 $z$ 函数定义，$s[0,...,k-1]=s[j,...j+k-1]$

这时考虑 $\pi[j+k-1]$，根据 $\pi$ 的定义 $\pi[j+k-1]\ge k$，得到 $max\\{\pi[i]\\}\ge \pi[j+k-1]\ge max\\{z[i]\\}$

不妨设 $k=max\\{\pi[i]\\}$，设 $j$ 是出现最大 $\pi[i]$ 的位置，$s[0,...,k-1]=s[j-k+1,j]$

这时考虑 $z[j-k+1]$，根据 $z$ 的定义 $z[j-k+1]\ge k$，得到 $max\\{z[i]\\}\ge z[j-k+1]\ge max\\{\pi[i]\\}$

综上，有 $max\\{\pi[i]\\}=max\\{z[i]\\}$

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> Z(string s) {
    int n = (int)s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r && z[i-l] < r - i + 1) {
            z[i] = z[i-l];
        } else {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int main() {
    string s;
    cin >> s;
    int n = (int)s.size();
    vector<int> dp(n, 0);
    dp[0] = 1;
    string temp;
    temp.push_back(s[0]);
    for (int i = 1; i < n; ++i) {
        temp.push_back(s[i]);
        reverse(temp.begin(), temp.end());
        vector<int> z = Z(temp);
        reverse(temp.begin(), temp.end());
        int Max = 0;
        for (int j = 0; j < z.size(); ++j) Max = max(Max, z[j]);
        dp[i] = dp[i-1] + temp.size() - Max;
    }

    cout << dp[n-1];
    return 0;
}

E. 战士与辅助

Description

HMP_Haoge 编写了一款开放世界游戏，游戏中有一个关于战斗的小游戏，首先玩家拥有 $n$ 个战士，它们的战斗力分别为 $a_1, a_2, \cdots, a_n$；接着，玩家拥有 $n$ 个辅助，它们的辅助力分别为 $b_1, b_2, \cdots, b_n$。

现在，玩家需要将这 $2n$ 个角色分为 $n$ 组，每组为一个战士和一个辅助，每组的战斗力为相对战士战斗力和辅助的辅助力之和。然而，开发者在开发时不小心写了一个bug，它将每个组的战斗力对 $n$ 进行了取模。形式化来说，对于第 $z$ 组，我们记该组的战斗力为 $c_z$，假设该组由第 $i$ 个战士和第 $j$ 个辅助组成，那么 $c_z = (a_i + b_j) \mod n$。

你发现了这个bug，但是你却无法改变它，这时你作为玩家，你需要完成分组，并且使用所有组的战斗力之和最大，即最大化 $\sum_{i=1}^n c_i$。

你只需要输出这个最大的战斗力之和即可。

Format

Input

首先输入一个正整数 $T$，表示数据组数。

对于每组数据：

第一行，一个整数 $n$ 表示战士和辅助的数目；
第二行，$n$ 个整数，第 $i$ 个数表示 $a_i$；
第三行，$n$ 个整数，第 $i$ 个数表示 $b_i$；

保证 $T$ 组测试数据的 $\sum n$ 不超过 $2 \times 10^5$。

Output

对于每组数据，输出一行，一个整数，表示最大的 $\sum_{i=1}^n c_i$。

Samples

样例输入 #1

2
4
31 45 92 65
35 89 79 32
10
1 1 4 5 1 4 1 1 4 5
1 9 1 9 8 1 0 1 9 1

样例输出 #1

1
2

8
37

Limitation

【样例解释】

用二元组 $(i,j)$ 表示把 $a_i$ 和 $b_j$ 分为一组。

那么对于第一组数据，可以采用的分组方案为： $(1,3), (2,4), (3,1), (4,2)$

此时得到最大的战斗力和为： $((31 + 79) \mod 4) + ((45 + 32) \mod 4) + ((92 + 35) \mod 4) + ((65 + 89) \mod 4) = 2 + 1 + 3 + 2 = 8$

【数据范围】 $1 \leq T \leq 2 \times 10^5$ $1 \leq n \leq 2 \times 10^5, \sum n \leq 2 \times 10^5, 0 \leq a_i, b_i \leq 2 \times 10^5$

思路与题解

由于模的存在，我们直接按照同余类分类

要使得和最大，我们需要尽量的两个和不超过 $n$

先两两配对考虑和为 $n-1$ 的

对于剩下的，考虑固定 $a$，对 $a$ 的每一个元素，要使得找到 $b$ 中的元素让他们的和接近 $n-1$，那么就从它们配对的那个逆元往下遍历，这样先配对完最接近 $n-1$ 的，如果这一部分的和超了，那就往从最上方开始遍历，这样使得两者和超了之后做出的贡献最大，根据这个原则匹配完即可

值得一提的是实现这个过程采用了两个指针分别记录 $b$ 进行到哪里了

时间复杂度 $O(n)$ ，应该是最优的

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int n;
    vector<int> a,b;
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        a.resize(n, 0);
        b.resize(n, 0);
        int temp;
        for (int i = 0; i < n; ++i) {
            cin >> temp;
            a[temp % n]++;
        }

        for (int i = 0; i < n; ++i) {
            cin >> temp;
            b[n - 1 - (temp % n)]++;
        }

        long long ans = 0;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            int MIN = min(a[i], b[i]);
            cnt += MIN;
            a[i] -= MIN;
            b[i] -= MIN;
        }
        ans += 1LL * cnt * (n-1);

        int j_ge = 0, j_l = 0;

        for (int i = 0; i < n; ++i) {
            while (a[i] > 0) {
                if (j_ge < i + 1) j_ge = i + 1;
                while (j_ge < n && b[j_ge] == 0) ++j_ge;

                if (j_ge < n) {
                    long long MIN = min(a[i], b[j_ge]);
                    a[i] -= MIN;
                    b[j_ge] -= MIN;
                    int k = n - 1 - j_ge;
                    ans += MIN * ((i + k) % n);
                    continue;
                }

                while (j_l < n && b[j_l] == 0) ++j_l;
                if (j_l == n) break;

                long long MIN = min(a[i], b[j_l]);
                a[i] -= MIN;
                b[j_l] -= MIN;
                int k = n - 1 - j_l;
                ans += MIN * ((i + k) % n);
            }
        }

        cout << ans << endl;

        a.clear();
        b.clear();
    }

    return 0;
}

SB. 周期循环

描述

ZZR 喜欢周期循环，看不到周期循环的字符串就很不爽。

现在 ZZR 得到一个字符串，可以在字符串末尾添加若干任意字符。

请你帮 ZZR 想想，最少添加多少个字符，才能使得字符串变得周期循环（即存在一个循环节至少循环两次）。

格式

输入

第一行一个整数 $T$ 代表测试数据的组数。

接下来 $T$ 行每行一个字符串，由小写字母组成，字符串的长度为 $L$。

输出

每组测试数据输出一行表示最少添加的字符数量。

样例

输入样例：

3
ppp
pip
machinelearning

输出样例：

1
2
3

0
1
15

样例解释： ppp 为周期循环，循环节为 p，循环 3 次。

限制

$1 \le T \le 100$， $3 \le L \le 10^5$。

思路与题解

考场上没写出来有点遗憾了，思路是用 $z$ 函数确定字符串已有的周期，如果已经是周期字符串，对最小的 $i$ 有 $z[i] + i == n $ 且 $n i == 0 $ 也就是后缀 s[i..] 完全等于前缀 s[0..n-i)，并且长度能被 $i$ 整除，说明整串正好是长度为 $i$ 的块重复拼成的，此时答案是 $0$

如果不能整除，就找和原字符串开始重复的字符位置也就是满足 $z[i] + i == n $ 的位置，说明周期就是 $i$ ，接下来用 $i$ 减去还剩下多少没重复就得到答案

如果完全找不到，那答案就是原字符串长度

#include <bits/stdc++.h>

using namespace std;

vector<int> Z(string s) {;
    int n = s.size();
    vector<int> z(n);
    z[0] = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r && z[i-l] < r-i+1) {
            z[i] = z[i-l];
        }else {
            z[i] = max(0, r-i+1);
            while (i + z[i] < n && s[z[i]] == s[i+z[i]]) z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int main() {
    int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
        int n = (int)s.size();
        vector<int> z = Z(s);

        int period = n;
        for (int i = 1; i < n; ++i) {
            if (z[i] + i == n && n % i == 0) {
                period = i;
                break;
            }
        }
        if (period == n) {
            for (int i = 1; i < n; ++i) {
                if (z[i] + i == n) {
                    period = i;
                    break;
                }
            }
        }

        int add;
        if (period == n) {
            add = n;
        } else {
            add = period - (n % period);
            if (add == period) add = 0;
        }

        cout << add << endl;
    }

    return 0;
}

SC. 括号字符串转置

题目背景

问题描述

给定一个字符串 $S = S_1S_2S_3 \ldots S_{|S|}$，由大写和小写的英文字母、(、)、[和]组成。字符串 $S$ 中的括号是匹配的。

重复执行以下操作，直到无法再执行为止：

首先，选择一对整数 $(l, r)$，满足以下所有条件： - $l < r$ - 字符串 $S_{l+1}, S_{l+2}, \ldots, S_{r-1}$ 中的每个字符都是大写或小写的英文字母 - $S_l = ($ 且 $S_r = )$，或者 $S_l = [$ 且 $S_r = ]$

令 $T_1 = S_{l+1}S_{l+2} \ldots S_{r-1}$，$T_2 = \text{reverse}(S_{r-1}S_{r-2} \ldots S_{l+1})$。

这里，$\text{reverse}(x)$ 表示通过切换 $x$ 中每个字符的大小写（大写变小写，小写变大写）而得到的字符串。

然后，删除 $S$ 中第 $l$ 到 $r$ 的字符，如果 $S_l = ($ 且 $S_r = )$ 则在删除位置插入字符串 $T_1$，否则在删除位置插入字符串 $T_2$。

可以证明，使用上述操作可以去除字符串中的所有 (、)、[和]，并且最终字符串与操作的顺序无关。请确定最终的字符串。

括号匹配定义

字符串 $S$ 中的括号匹配是什么意思？首先，一个正确的括号序列定义如下：

正确的括号序列是满足以下条件之一的字符串： - 它是一个空字符串 - 它是一个仅包含大写或小写的英文字母的字符串 - 存在一个正确的括号序列 $A$，该字符串由 (、$A$、) 或 [、$A$、] 依次连接而成 - 存在非空的正确括号序列 $A$ 和 $B$，该字符串由 $A$ 和 $B$ 依次连接而成

当且仅当从字符串 $S$ 中提取出的 ( 和 )（保持顺序不变）形成一个正确的括号序列时，字符串 $S$ 中的括号才是匹配的。

输入格式

第一行输入一个字符串 $S$，保证 $S$ 由大写和小写的英文字母、(、)、[和]组成且 $S$ 中的括号是匹配的。

输出格式

输出一行，表示按照上述规则去除 $S$ 中的所有 (、)、[和]后最终的字符串。

样例 #1

样例输入 #1

[(A)y]x()

样例输出 #1

yax

样例 #2

样例输入 #2

1	S([VPX[w[t]PcV]PBG])

样例输出 #2

1	SgbpWTpCvxpv

数据范围与提示

\[1 \leq |S| \leq 5 \times 10^6\]

思路与题解

考试时卡第一题上了，后面在写递归，但是递归过不了，原因是 最终字符串与操作的顺序无关

那其实可以优化到 $O(n)$ 的时间复杂度

预处理 [ 和 ] 的位置

从左到右依次遍历，如果遇到 [ 和 ] 就跳转并反向遍历，这里就实现了翻转字符串的位置

而对于 ( 和 ) ，其实是不用考虑它的顺序的，从左到右遍历的时候其实他只会改变是否进行大小写转换，考虑经过它的奇偶就可以判断了

代码可能写的有点复杂，主要是用原来递归改的

#include <bits/stdc++.h>

using namespace std;

char Change(char c) {
    if (c >= 'a' && c <= 'z') return char(c - 'a' + 'A');
    if (c >= 'A' && c <= 'Z') return char(c - 'A' + 'a');
    return c;
}

string solve(const string& s) {
    int n = (int)s.size();
    vector<int> match(n, -1);
    vector<int> st;

    // 预处理匹配的 []
    for (int i = 0; i < n; ++i) {
        if (s[i] == '[') st.push_back(i);
        else if (s[i] == ']') {
            int j = st.back(); st.pop_back();
            match[i] = j;
            match[j] = i;
        }
    }

    string res;
    res.reserve(n);

    int i = 0;
    int dir = 1;
    int par = 0; // ()奇偶


    while (i >= 0 && i < n) {
        char c = s[i];
        if (c == '[' || c == ']') {
            // 跳转并反向
            i = match[i];
            dir = -dir;
        } else if (c == '(' || c == ')') {
            par ^= 1;
        } else {
            if (par) c = Change(c);
            res.push_back(c);
        }
        i += dir;
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    string result = solve(s);
    cout << result << endl;
    return 0;
}

(´-ω-｀)

数据结构作业题解04

A. SA.算一算 Ⅰ

Description

Format

Input

Output

Samples

输入样例 1

输出样例 1

输入样例 2

输出样例 2

Limitation

思路与题解

B. 序列延中与后缀查询

Description

Input Format

Output Format

Samples

样例输入 #1

样例输出 #1

数据范围与提示

思路与题解

C. 快速幂

Description

Format

Input

Output

Samples

输入样例

输出样例

Limitation

思路与题解

D. 本质不同子串计数

Description

Format

Input

Output

Samples

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

数据范围与提示

思路与题解

E. 战士与辅助

Description

Format

Input

Output

Samples

样例输入 #1

样例输出 #1

Limitation

思路与题解

SB. 周期循环

描述

格式

输入

输出

样例

限制

思路与题解

SC. 括号字符串转置

题目背景

问题描述

括号匹配定义

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

数据范围与提示

思路与题解