A. 你的数太多了

题目描述

给定一个大小为 $n$ 的有序可重数列，要求把其中出现了超过 $1$ 次的数字都去掉，求操作之后的数列。

输入格式

第一行一个正整数 $n$，表示数列的大小。
第二行 $n$ 个正整数 $a_i$，表示数列的元素，保证数列有序。

输出格式

仅一行若干个正整数，表示操作之后的序列。

样例输入

1 2	5 2 3 3 3 4

样例输出

2 4

数据范围与提示

$1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$。

思路与题解

map 或者 unorder_map 是去重好帮手

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    int temp;
    vector<int> ans;
    vector<int> v(n);
    map<int, int> map;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        map[v[i]]++;
    }
    for (int i = 0; i < n; i++) if (map[v[i]] == 1) ans.push_back(v[i]);

    for (auto i : ans) cout << i << " ";

    return 0;
}

B. 合并链表

题目描述

一个链表共有 $n$ 个“块”，编号依次为 $1, 2, \cdots, n$，每块中放置了一个长度为 $k$ 的数组，第 $i$ 块中的数组的前 $a_i$ 位储存了有效信息。

这样，第 $i$ 块的数组就有 $k-a_i$ 的单位空间没有使用，造成了时间和空间的浪费，所以需要合并一部分块来提高运行效率。

两个块 $i, j\ (i < j)$ 能够合并，当且仅当它们相邻即 $j-i=1$，且 $a_i+a_j \leq k$。

合并操作为：将 $j$ 的有效信息紧接到 $i$ 的有效信息后面，在 $i$ 的数组中形成长度为 $a_i+a_j$ 的有效信息，并删除 $j$。

求这个链表可以合并到最少是多少块。

输入格式

第一行两个正整数 $n, k$。
第二行 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$。

输出格式

一个整数，表示答案。

样例输入

1
2

3 2
1 1 1

样例输出

数据范围与提示

$1 \leq n \leq 10^6,\ 1 \leq k \leq 10^9$。

所有 $a_i \leq k\ (1 \leq i \leq n)$。

样例解释：可以将前两个 $1$ 合并形成一个块，第三个 $1$ 形成第三个块。

思路与题解

把能加的都加进去，这样一定是最优的

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> res;
    for (int i = 0; i < n; i++) {
        if (!res.empty() && res.back() + a[i] <= k) res.back() += a[i];
        else res.push_back(a[i]);
    }
    cout << res.size() << endl;
    return 0;
}

C.SA. 重复字符串 I

Description

给定一个长度为 $n$，全部由小写英文字母组成字符串 $s$，找出最长的子串，使得该子串在字符串 $s$ 中至少出现两次且不重叠。

具体来说，不妨令子串长度为 $l$，则：

$ l_1, l_2 n - l + 1, l_1 + l l_2 $;
$ s_{l_1+i} = s_{l_2+i} $ ($ i {0, 1, …, l - 1} $)。

如果子串不存在，则输出 $0$。

Format

Input

第一行一个整数 $n$ 表示字符串长度。

第二行为长度为 $n$ 的字符串 $s$。

Output

一个整数，表示在字符串 $s$ 中出现两次且不重叠的最长子串的长度。

Samples

输入样例

1 2	13 strangeorange

输出样例

Limitation

$ 2 n ^3 $。

思路与题解

$dp[i][j]$ 代表以 $s[i-1]$ 结尾和以 $s[j-1]$ 结尾的最长公共后缀的长度

逐个对比，时间复杂度 $O(n^{2})$

注意一下条件，这两个字符串不能重合

最优的应该是后缀自动机时间复杂度和空间复杂度都是 $O(n)$

#include <bits/stdc++.h>

using namespace std;


int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    // dp[i][j] 代表 以 s[i-1] 结尾和以 s[j-1] 结尾的最长公共后缀的长度

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (s[i-1] == s[j-1]) {
                if (dp[i-1][j-1] < i - j) { // 保证不重叠
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = i - j;
                }
            } else dp[i][j] = 0;
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;

    return 0;
}

D. 最大子矩阵

题目描述

给定一个仅包含整数的二维方阵 $A_{N \times N}$，求其所有子矩阵中矩阵和最大的一个。

一个子矩阵被定义为二维矩阵中大小为 $1 \times 1$ 或者更大的连续矩阵，矩阵和为其中所有元素的和。

例如，一个二维矩阵 $A_{4 \times 4}$ 如下：

0 -2 -7  0 
 9  2 -6  2 
-4  1 -4  1 
-1  8  0 -2

其中左下角的子矩阵为：

1
2
3

9 2 
-4 1 
-1 8

其矩阵和为 15。

输入格式

第一行包含一个整数 $N$，表示二维方阵每一维的大小。

从第二行开始每行 $N$ 个整数，表示方阵的每一行。共 $N$ 行。

输出格式

输出一行表示最大的子矩阵和。

样例

输入样例

输出样例

数据范围与提示

$ N $;

$ a_{i,j} $, $ a_{i,j} $ 为 $ A_{N N} $ 中的元素。

思路与题解

前缀和+容斥原理，时间复杂度很高，达到了神秘的 $O(n^{4})$

后面了解了 $Kadane$ 算法，最优时间复杂度应该是 $O(n^{3})$

有时间补充一下最优解

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> v(n,vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) cin >> v[i][j];
    }

    vector<vector<int>> sum (n+1,vector<int>(n+1,0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + v[i-1][j-1];
        }
    }
    int ans = INT_MIN;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = i; k <= n; ++k) {
                for (int l = j; l <= n; ++l) {
                    ans = max(ans, sum[k][l] - sum[i-1][l] - sum[k][j-1] + sum[i-1][j-1]);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

E. Permutation Transformer

题目描述

给出 $1 \sim n$ 的排列，最开始是 $1, 2, \cdots, n$ 的顺序序列。

接下来有 $m$ 个操作，对于每个操作 $[l, r]$，需将排列下标 $l \sim r$ 的元素翻转后放到整个序列的末尾。

输入整数 $n, m$，接下来 $m$ 行包括每个操作对应的区间。

输出最终得到的序列。

输入格式

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

接下来 $m$ 行，每行两个整数 $l, r$，表示把当前序列的下标 $[l, r]$ 区间的元素翻转后放到整个序列的末尾。

输出格式

输出一行，$n$ 个整数，表示最后的序列。

样例输入 #1

1
2
3

10 2
2 5
4 8

样例输出 #1

1	1 6 7 3 2 4 5 10 9 8

数据范围

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

思路与题解

最难一题，改了几版没出来

块状链表+懒标记时间复杂度 $n + m\sqrt{n}$

数据很严，尝试过程：

纯数组实现（不通过）

不维护 $\sqrt{n}$ 长度块的块状链表实现（不通过）

不维护 $\sqrt{n}$ 长度块的块状链表+懒标记实现（不通过）

维护 $\sqrt{n}$ 长度块的块状链表+懒标记实现（通过）

怀疑是不维护长度导致块状链表后期逐渐退化成链表导致时间复杂度上升导致的 $TLE$

上机考这个能不能直接套模板啊（

#include <bits/stdc++.h>

using namespace std;

struct Block {
    vector<int> v;
    bool lazy = false;

    Block(vector<int> v, bool lazy) : v(v), lazy(lazy) {}
};

using BL = list<Block>;

void reverseLazy(BL::iterator it) {
    if (it->lazy) {
        reverse(it->v.begin(), it->v.end());
        it->lazy = false;
    }
}

// 从 it 指定的 pos 前分裂新 block，返回指向新 block 的 it
BL::iterator split(BL &bl, BL::iterator it, int pos) {
    if (pos == 0) return it;
    if (pos == it->v.size()) {
        ++it;
        return it;
    }
    reverseLazy(it);
    vector<int> newV(it->v.begin() + pos, it->v.end());
    Block newBlock(newV ,false);
    it->v.erase(it->v.begin() + pos, it->v.end());
    return bl.insert(++it, newBlock);
}

// 得到[l,r]区间的块
BL getLR(int l, int r, BL &bl) {
    if (l > r) return {};
    auto it = bl.begin();

    // 找 l
    int pos = 1;
    while (it != bl.end() && pos + it->v.size() < l) {
        pos += it->v.size();
        ++it;
    }
    auto start = split(bl, it, l-pos);
    it = start;

    // 找 r
    pos = 0;
    while (it != bl.end() && pos + it->v.size() < r - l + 1) {
        pos += it->v.size();
        ++it;
    }
    auto end = split(bl, it, r - l + 1 - pos);

    // 把这个区间放到ans中返回
    BL ans;
    ans.splice(ans.begin(), bl, start, end);
    return ans;
}

// 保持块状链表每一块的稳定，分裂过大的，合并过小的
void maintain(BL &bl, int B) {
    for (auto it = bl.begin(); it != bl.end(); ) {
        while ((int)it->v.size() > 2 * B) {
            reverseLazy(it);
            vector<int> newV(it->v.begin() + B, it->v.end());
            it->v.erase(it->v.begin() + B, it->v.end());
            bl.insert(next(it), Block(newV, false));
        }

        if (it != bl.begin()) {
            auto prev = it; --prev;
            if ((int)prev->v.size() + (int)it->v.size() <= B) {
                reverseLazy(prev);
                reverseLazy(it);
                prev->v.insert(prev->v.end(), it->v.begin(), it->v.end());
                it = bl.erase(it);
                continue;
            }
        }
        ++it;
    }
}

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

    int n,m;
    cin >> n >> m;
    int B = max(1, (int)std::sqrt(n));
    BL bl;
    vector<int> all(n);
    for (int i = 0; i < n; i++) all[i] = i+1;
    for (int i = 0; i < n; i += B) {
        vector<int> v(all.begin() + i, all.begin() + min(n, i + B));
        bl.push_back(Block(v, false));
    }
    int l, r;
    for (int i = 0; i < m; ++i) {
        cin >> l >> r;
        // 得到区间
        BL LR = getLR(l, r, bl);

        // 反转区间
        LR.reverse();
        for (auto& block : LR) {
            block.lazy = !block.lazy;
        }
        bl.splice(bl.end(), LR);
        maintain(bl, B);
    }

    for (auto block = bl.begin(); block != bl.end(); ++block) {
        reverseLazy(block);
        for (auto &x : block->v) cout << x << " ";
    }

    return 0;
}

后面使用了 GNU 的 rope 数据结构

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_cxx;

int main() {
    int n, m;
    cin >> n >> m;
    rope<int> s,rs;
    for (int i = 1; i <= n; ++i ) {
        s.push_back(i);
        rs.push_front(i);
    }
    int l, r;
    for (int i = 0; i < m; ++i) {
        cin >> l >> r;
        --l;
        rope<int> A = s.substr(0, l);
        rope<int> B = s.substr(l, r-l);
        rope<int> C = s.substr(r, n-r);
        rope<int> rA = rs.substr(n - l, l);
        rope<int> rB = rs.substr(n - r, r - l);
        rope<int> rC = rs.substr(0, n - r);
        s = A + C + rB;
        rs = B + rC + rA;
    }
    for (int i : s) cout << i << " ";
    return 0;
}

字符串 rope（`crope`）

首先，我们定义了一个 crope a;

a.push_back(x)：在 a 的末尾添加字符 c；
a.insert(p,x): 在 a 的下标 p 后面添加 x；
或 a.insert(p,s,n)：将字符串 s 的前 n 位插入 a 的下标 p 处；
a.erase(p,x): 从 a 的下标 p 开始删除 x 个元素；
a.replace(p,s): 从 a 的下标 p 开始换成字符串 s，若 a 的位数不够则补足；
a.copy(p,n,s)：从 a 的下标 p 开始的 n 个字符换成字符串 s，若位数不够则补足；
a.substr(p,x)：从 a 的下标 p 开始截取 x 个元素；
a[x] 或 a.at(x) 访问下标为 x 的元素；
a.append(s,p,n)：把字符串 s 中从下标 p 开始的 n 个字符连接到 a 的结尾，如没有参数 n 则把字符串 s 中下标 p 后的所有字符连接到 a 的结尾，如参数 p 也没有则把整个字符串 s 连接到 a的结尾；

以上，s 均为字符串（string 或 char[]）类型，c 为字符（char）类型，n，p，x 均为整型。

这些操作复杂度基本都为 $O(\sqrt{n})$ ， push_back 等单个字符的插入是 $O(1)$

SB. 位运算自动机

题目背景

小皮在做研究的时候整理了一系列的位运算计算任务，他把计算任务记录了下来，希望你写个程序帮助他算出最后的答案。

计算任务是一个表达式字符串，它仅由 $a, b, \ldots, z$ 和小写字母组成。其中，& 表示按位与运算，| 表示按位或运算，^ 表示按位异或运算，$a \sim z$ 表示 $26$ 个变量。

你现在已经知道每个小写字母表示的变量的值，以及计算任务的表达式，请你输出这个 $32$ 位无符号整数表达式的计算结果。

注意到，位运算具有运算优先级。& 的优先级最高，^ 的优先级次之， |的优先级最低。

输入格式

第一行输入 $26$ 个用空格分开的整数，分别表示常量 $a, b, c, \ldots, z$ 的值。

第二行输入一个字符串 $s$，表示算式。

数据保证表达式合法，即输入的字符串一定是用运算符分隔开表示变量的字符串的形式。可以参考样例，这有助于了解输入格式。

输出格式

输出一行一个整数，表示计算结果。

样例输入 #1

1 2	1 2 4 8 16 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a\|b^c&d^e\|f

样例输出 #1

样例输入 #2

1 2	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 a^b^c^d^e^f^g^h^i^j^k^l^m^n^o^p^q^r^s^t^u^v^w^x^y^z

样例输出 #2

数据范围与提示

对于 30% 的测试数据满足，算式中含有不超过 1 种运算符。
对于 60% 的测试数据满足，算式中含有不超过 2 种运算符。
对于 100% 的测试数据满足 $0 \leq a, b, c, \ldots, z \leq 2^{32}-1$，算式长度不超过 $2 \times 10^5$ 个字符。

思路与题解

没有 $AC$ 这道真是有点搞笑了，考场上的实现很劣

#include <bits/stdc++.h>

using namespace std;

int main(){
    unordered_map<int,unsigned> v;
    for(int i = 0; i < 26; ++i) cin >> v[i];
    int cnt = 26;
    string s;
    cin >> s;

    stack<int> stNum;
    stack<int> stOp;
    int n = s.size();

    // 处理 & 操作
    bool key = false;
    for(int i = 0; i < n; ++i){
        if(key){
            int a = stNum.top();
            stNum.pop();
            int b = s[i] - 'a';
            int c = cnt++;
            v[c] = v[a] & v[b];
            stNum.push(c);
            key = false;
            continue;
        }
        if (s[i] == '|') stOp.push(-2);
        else if (s[i] == '^') stOp.push(-1);
        else if(s[i] == '&') key = true;
        else stNum.push(s[i] - 'a');
    }

    // 重构字符串
    vector<int> s0;
    while(!stNum.empty() && !stOp.empty()){
        s0.push_back(stNum.top());
        stNum.pop();
        s0.push_back(stOp.top());
        stOp.pop();
    }
    if(!stNum.empty()){
        s0.push_back(stNum.top());
        stNum.pop();
    }
    reverse(s0.begin(), s0.end());

    // 处理 ^ 操作
    n = s0.size();
    key = false;
    for(int i = 0; i < n; ++i){
        if(key){
            int a = stNum.top();
            stNum.pop();
            int b = s0[i];
            int c = cnt++;
            v[c] = v[b] ^ v[a];
            key = false;
            stNum.push(c);
            continue;
        }
        if (s0[i] == -2) stOp.push(s0[i]);
        else if(s0[i] == -1) key = true;
        else stNum.push(s0[i]);
    }

    // 计算最终结果
    unsigned ans = v[stNum.top()];
    stNum.pop();
    while(!stNum.empty()) {
        ans |= v[stNum.top()];
        stNum.pop();
    }
    cout << ans;

    return 0;
}

SC. 汉诺塔

题目背景

by Gym

汉诺塔是一个非常经典的问题。给你三个柱盘，编号为 $A, B, C$。现在 $A$ 柱盘上面有若干个圆饼，下面的圆饼半径大于上面的，$B, C$ 柱为空。

正常，我们的任务是利用 $B$ 柱，把柱盘的所有圆饼移到 $C$ 柱上，并且过程中要保证大圆饼不能放在小圆饼上面。这个问题的子问题，引出了递归版本，即“从 $n$ 个圆饼该怎么移？”这个问题是也难不倒你，因为这个问题已经被证明了有唯一解，需要 $2^n-1$ 个步骤。

现在，问题变得更加细致一点。输入三个盘柱上面圆饼的状态，请你判断这个状态是否处于最优步骤的某个状态中，如果是，请输出这个状态还需要多少步才能把所有圆饼移到 $C$ 柱上。

输入格式

共三行：

第一行：整数 $a$，代表 $A$ 柱此时有 $a$ 个圆饼，接下来输入 $a$ 个整数，表示圆饼的半径。

第二行：整数 $b$，代表 $B$ 柱此时有 $b$ 个圆饼，接下来输入 $b$ 个整数，表示圆饼的半径。

第三行：整数 $c$，代表 $C$ 柱此时有 $c$ 个圆饼，接下来输入 $c$ 个整数，表示圆饼的半径。

保证当前柱盘的所有圆饼的半径是一系列从 $1$ 开始的连续的整数，且不重复，且大半径的圆饼一定在小半径圆饼的下方。

输出格式

如果当前的状态不在最优步骤中，输出 No，否则输出还需要多少个步骤来完成任务。

样例输入 #1

1
2
3

1 3
2 2 1
0

样例输出 #1

样例输入 #2

1
2
3

1 3
0
2 2 1

样例输出 #2

No

提示

对 100% 的数据满足：$a+b+c \leq 50$。

思路与题解

$dfs$ 但来不及写了

#include <bits/stdc++.h>

using namespace std;

map<int,char> posOf;

long long stepsDone(int k, char from, char to, char aux) {
    if (k == 0) return 0;
    auto it = posOf.find(k);
    if (it == posOf.end()) return -1;
    char p = it->second;
    if (p == from) return stepsDone(k - 1, from, aux, to);
    else if (p == to) {
        long long sub = stepsDone(k - 1, aux, to, from);
        if (sub == -1) return -1;
        return (1LL << (k - 1)) + sub;
    } else return -1;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,c,x;
    int maxDisk = 0;
    if (!(cin >> a)) return 0;
    for (int i=0;i<a;i++){ cin >> x; posOf[x]='A'; maxDisk = max(maxDisk,x); }
    cin >> b;
    for (int i=0;i<b;i++){ cin >> x; posOf[x]='B'; maxDisk = max(maxDisk,x); }
    cin >> c;
    for (int i=0;i<c;i++){ cin >> x; posOf[x]='C'; maxDisk = max(maxDisk,x); }

    int n = maxDisk;
    for (int d=1; d<=n; ++d) if (!posOf.count(d)) { cout << "No\n"; return 0; }

    long long done = stepsDone(n, 'A', 'C', 'B');
    if (done == -1) {
        cout << "No";
        return 0;
    }
    long long total = (1LL << n) - 1;
    long long remain = total - done;
    cout << remain;
    return 0;
}

(´-ω-｀)

数据结构作业题解02

A. 你的数太多了

题目描述

输入格式

输出格式

样例输入

样例输出

数据范围与提示

思路与题解

B. 合并链表

题目描述

输入格式

输出格式

样例输入

样例输出

数据范围与提示

思路与题解

C.SA. 重复字符串 I

Description

Format

Input

Output

Samples

Limitation

思路与题解

D. 最大子矩阵

题目描述

输入格式

输出格式

样例

数据范围与提示

思路与题解

E. Permutation Transformer

题目描述

输入格式

输出格式

样例输入 #1

样例输出 #1

数据范围

思路与题解

字符串 rope（crope）

SB. 位运算自动机

题目背景

输入格式

输出格式

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

数据范围与提示

思路与题解

SC. 汉诺塔

题目背景

输入格式

输出格式

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

提示

思路与题解

字符串 rope（`crope`）