A. 后缀表达式

Description

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右进行（不用考虑运算符的优先级）。

如：$3*(5-2)+7$ 对应的后缀表达式为：$3$、$5$、$2$、$-*7$、$+@$。$@$ 为表达式的结束符号。$.$ 为操作数的结束符号，防止操作数连在一起分不清。

Format

Input

输入：后缀表达式，以 $@$ 结尾

Output

输出：表达式的值，运算结果

Samples

输入样例 1

1	3.5.2.-*7.+@

输出样例 1

Limitation

字符串长度，$1000$ 内。

运算符只有加减乘除四种 $(+,-,*,/)$，保证所有的中间结果都是 int 范围

思路与题解

模板题

#include <iostream>
#include <stack>

using namespace std;

int main() {
    string s;
    cin >> s;
    stack<int> st;
    int num = 0;
    for (char c : s) {
        if (c == '.') {
            if (num != 0) {
                st.push(num);
                num = 0;
            }
        }
        else if (isdigit(c)) {
            num = num * 10 + (c - '0');
        }
        else if (c == '@') {
            cout << st.top();
            break;
        }
        else {
            int a = st.top(); st.pop();
            int b = st.top(); st.pop();
            if (c == '+') st.push(b + a);
            else if (c == '-') st.push(b - a);
            else if (c == '*') st.push(b * a);
            else if (c == '/') st.push(b / a);
        }
    }
    return 0;
}

B. 栈与询问

题目背景

现在有一个空的栈，接下来会进行 $m$ 次操作，每次操作后你需要输出栈中最大的元素。

每次操作是下面的一种： 1. push $x$ 向栈中插入一个元素 $x$ 2. pop 弹出栈顶元素

输入格式

第一行，一个整数 $m$。

接下来 $m$ 行，每行表示一个操作，格式是下面的一种： - push $x$ - pop

输出格式

输出 $m$ 行，每次输出栈中最大的元素。特别的，如果栈此时为空，输出一行 empty。

样例 #1

样例输入 #1

5
push 2
push 3
pop
pop
push 5

样例输出 #1

2
3
2
empty
5

数据范围与提示

$m \leq 10^5, 0 \leq x \leq 10^9$。

思路与题解

维护两个栈，一个栈是单调栈，一直维护另一个栈的最大值，另一个栈模拟即可

#include <iostream>
#include <stack>

using namespace std;

int main() {
    int m;
    cin >> m;
    string s;
    int k;
    stack<int> st1;
    stack<int> st2;
    while (m--) {
        cin >> s;
        if (s == "push") {
            cin >> k;
            st1.push(k);
            if (st2.empty() || k > st2.top()) {
              st2.push(k);
            } else {
                st2.push(st2.top());
            }
            cout << st2.top() << endl;
        } else if (s == "pop") {
            st1.pop();
            st2.pop();
            if (st2.empty()) {
                cout << "empty" << endl;
            } else {
                cout << st2.top() << endl;
            }
        }
    }
    return 0;
}

C. 四角不同色

题目描述

你需要构造一个 $n$ 行 $m$ 列的 0-1 矩阵。

其中第 $i$ 行第 $j$ 列的元素记作 $a_{i,j}$，满足 $a_{i,j} \in \{1,0\} (1 \leq i \leq n, 1 \leq j \leq m)$。

此外你构造的这个矩阵还需要满足一个条件：对于每个长宽均大于 1 的子矩阵，它的四个角上的元素不能完全相同。

形式化的说，对于任意的 $1 \leq i_1 < i_2 \leq n, 1 \leq j_1 < j_2 \leq m$，不允许 $a_{i_1,j_1} = a_{i_1,j_2} = a_{i_2,j_1} = a_{i_2,j_2}$ 的情况出现。

如果说不存在合法的构造方案，请输出 “No solution” (不包含引号)。

如果存在合法的构造方案，请输出字典序最小的构造方案。

对于矩阵的字典序，在这道题中我们这样规定：

对比两个 $n \times m$ 的 0-1 矩阵的字典序，我们先将两者分别看作 $n$ 行的长度为 $m$ 的 0-1 字符串，然后将这些字符串按照符号从小到大的顺序从左往右拼接得到单个字符串。将两者得到的字符串的字典序作为矩阵的字典序比较即可。

形式化的说，比较矩阵的字典序时，实际上是在比较序列：

\[a_{1,1}, a_{1,2}, \cdots a_{1,m}, a_{2,1}, a_{2,2}, \cdots a_{2,m}, \cdots a_{n,1}, a_{n,2}, \cdots a_{n,m}\]

的字典序。

输入格式

第一行，一个正整数 $T$ 表示问题数。

对每组问题，输入一行两个整数，$n, m$，表示矩阵的行数和列数。

输出格式

对于每组问题：

如果无解，则输出一行 “No solution” (不包含引号)。
如果有解，请直接输出矩阵，用 $n$ 行的长度为 $m$ 的 0-1 字符串表示你的答案，不要有额外的空格。注意要求是输出字典序最小的解。

样例

输入数据 1

输出数据 1

00
01
0001
0110
1010
00
01
01
01
01
01
01
01
No solution

提示

【数据范围】

对于 20% 的数据，满足 $n, m, T \leq 4$

对于 50% 的数据，满足 $n, m, T \leq 10$

对于 70% 的数据，满足 $n, m, T \leq 50$

对于 100% 的数据，满足 $T \leq 8000, 2 \leq n, m \leq 10^5, \sum n \cdot m \leq 2 \times 10^5$

【时空限制】

时间限制：1000 ms

空间限制：256 MB

思路与题解

设 $a = min(n,m),b=max(n,m)$首先我们容易知道 $a=2$ 时有通解，直接根据通解输出即可

剩下考虑从 $a$ 中任取两行，再取这两行相同的两列，需要防止出现全 $0$ 或全 $1$，根据抽屉原理可以得知此时 $ a , b $，所以 $a \ge 5, b \ge 7$ 时一定无解，这下我们把数据范围大大缩小，可以采用 $dfs$ 解决

用 $g$ 表示在填的表，用 $ans$ 储存答案，没有填入的位置用 $?$ 表示

我们构造一个表存入任意两行出现的相同 $0$ 和 $1$ 的表 $cnt0$ 和 $cnt1$，再构造一个映射 $pid[r][i]$ 把两行 $r,i(r < i)$ 映射成唯一的 $id$，这样就可以在 $O(1)$ 内完成对 $cnt0$ 和 $cnt1$ 的查询

分别尝试 $0$ 和 $1$

如果出现 $cnt0[id]$ 或 $cnt[1]$ 大于等于 $1$ 的时候就说明有四个角元素相同了，这个时候 $dfs$ 搜索退出

后面就是 $dfs$ 常见模板

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<string> g, ans;
vector<int> cnt0, cnt1;
vector<vector<int>> pid;

bool dfs(int idx) {
    if (idx == n * m) { ans = g; return true; }
    int i = idx / m, j = idx % m;

    for (int bit = 0; bit <= 1; ++bit) {
        char ch = char('0' + bit);
        bool ok = true;

        for (int r = 0; r < i; ++r) {
            if (g[r][j] == ch) {
                int id = pid[r][i];
                if (bit == 0) { if (cnt0[id] >= 1) { ok = false; break; } }
                else          { if (cnt1[id] >= 1) { ok = false; break; } }
            }
        }
        if (!ok) continue;

        for (int r = 0; r < i; ++r) {
            if (g[r][j] == ch) {
                int id = pid[r][i];
                if (bit == 0) ++cnt0[id];
                else          ++cnt1[id];
            }
        }

        g[i][j] = ch;
        if (dfs(idx + 1)) return true;
        g[i][j] = '?';

        for (int r = 0; r < i; ++r) {
            if (g[r][j] == ch) {
                int id = pid[r][i];
                if (bit == 0) --cnt0[id];
                else          --cnt1[id];
            }
        }
    }
    return false;
}

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

    int T;
    if (!(cin >> T)) return 0;

    while (T--) {
        cin >> n >> m;
        int a = n < m ? n : m;
        int b = n < m ? m : n;

        if (a >= 5) { cout << "No solution\n"; continue; }

        if (a == 2) {
            if (n == 2) {
                string r1(m, '0');
                string r2(m, '1');
                if (m >= 1) r2[0] = '0';
                cout << r1 << '\n' << r2 << '\n';
            } else { // m == 2
                cout << "00\n";
                for (int i = 2; i <= n; ++i) cout << "01\n";
            }
            continue;
        }

        if (b > 6) { cout << "No solution\n"; continue; }

        pid.assign(n, vector<int>(n, -1));
        int numN = n * (n - 1) / 2;
        for (int id = 0, x = 0; x < n; ++x)
            for (int y = x + 1; y < n; ++y)
                pid[x][y] = id++;

        cnt0.assign(numN, 0);
        cnt1.assign(numN, 0);
        g.assign(n, string(m, '?'));
        ans.clear();

        if (!dfs(0)) {
            cout << "No solution\n";
            continue;
        }
        for (int i = 0; i < n; ++i) cout << ans[i] << '\n';
    }
    return 0;
}

D.SA. 括号替换

Description

给定的字符串 $s$ 由四种类型的左括号和右括号组成：$($, $)$, $[$, $]$, $\{$, $\}$, $<$, $>$。括号有两种类型：左括号和右括号。你可以用相同类型（同为左或同为右）的另一个括号代替任何一个括号。例如，您可以替换 “(” 为 “[” 括号，但不能用 “)” 或 “>” 代替。

下面的”正则括号序列”定义是众所周知的，因此您可以熟悉它。

让我们定义一个”正则括号序列”(RBS)。空字符串是 RBS。设 $s_1$ 和 $s_2$ 是一个 RBS，那么字符串 $(s_1)s_2$，$[s_1]s_2$，$\{s_1\}s_2$，$<s_1>s_2$ 也是 RBS。

例如，字符串 “$[[]()]\{\}$” 是 RBS，但 “$[]($” 和 “$[)]$” 不是。

在这个问题中，你需要确定使字符串 $s$ 变成 RBS 的最少替换次数，或者判断这是不可能的。

Format

Input

唯一的一行包含一个非空字符串 $s$，只包含四种类型的左括号和右括号。

Output

如果不能从 $s$ 得到正则括号序列，则输出 Impossible

否则输出把 $s$ 变成正则括号序列的最小替换次数

Samples

输入样例 1

[<}){}

输出样例 1

输入样例 2

{()}[]

输出样例 2

输入样例 3

]]

输出样例 3

1	Impossible

Limitation

$s$ 的长度不超过 $10^6$。

思路与题解

前半部分就是括号匹配的思路，对于变化为正则的，首先括号个数不可能是奇数，其次匹配完之后右括号不可能先于左括号出现，也就是右括号个数始终要小于左括号个数，否则不可能变成。最后只需要贪心将一左一右括号匹配（不管类型）即可

#include <iostream>
#include <stack>

using namespace std;

bool isMatching(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}') ||
           (left == '<' && right == '>');
}

int main() {
    string s;
    cin >> s;
    if (s.size() % 2 == 1) {
        cout << "Impossible" << endl;
        return 0;
    }
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{' || c == '<') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}' || c == '>') {
            if (st.empty()) {
                cout << "Impossible" << endl;
                return 0;
            } else {
                char top = st.top();
                if (isMatching(top, c)) {
                    st.pop();
                } else {
                    st.push(c);
                }
            }
        }
    }

    stack<char> temp;

    int lcnt = 0, rcnt = 0;
    while (!st.empty()) {
        char c = st.top();
        if (c == '(') lcnt++;
        else if (c == ')') rcnt++;
        else if (c == '[') lcnt++;
        else if (c == ']') rcnt++;
        else if (c == '{') lcnt++;
        else if (c == '}') rcnt++;
        else if (c == '<') lcnt++;
        else if (c == '>') rcnt++;
        st.pop();
        temp.push(c);
    }

    if (lcnt != rcnt) {
        cout << "Impossible" << endl;
        return 0;
    }

    int ans = 0;

    while (!temp.empty()) {
        char c = temp.top();
        temp.pop();
        if (c == '(' || c == '[' || c == '{' || c == '<') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}' || c == '>') {
            if (st.empty()) {
                cout << "Impossible" << endl;
                return 0;
            }
            char top = st.top();
            if (isMatching(top, c)) {
                st.pop();
            } else {
                ans++;
                st.pop();
            }
        }
    }

    cout << ans;
    return 0;
}

E. 争夺土地

题目背景

from Gym

题目描述

YGG 和 NSH 在 SDZX 争夺土地。

SDZX 的土地是一个大矩形，进而被划分成了 $n \times m$ 块小格子土地。即一共 $n$ 行，$m$ 列的矩阵。

NSH 曾给 YGG 划一部分的土地，但是 YGG 比较灰烬，想要一块正方形的区域作为自己的土地（即，想要一个长宽相同的子矩阵），而且他希望这个正方形区域的土地都是肥沃的。然而 SDZX 里并不是所有土地都是肥沃的。

但是 YGG 可以使用任意次序去，每次可将任意一行土地的状态取反：即选择一行，把这行中肥沃的土地变得贫瘠、贫瘠土地变得肥沃。

YGG 想知道，在上述条件下，他能获得最大的全肥沃的方形区域面积是多大。

输入格式

第一行，输入正整数 $n, m$。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，字符串由 $B$ 和 $G$ 组成。

上述输入构成了 $n \times m$ 的矩阵，表示每一块小正方形土地（面积为 1）是否肥沃。$G$ 表示肥沃，$B$ 表示贫瘠。

输出格式

一行，一个整数代表 YGG 能获得土地的最大面积。

样例 #1

样例输入 #1

1
2
3

2 2 
BB
BB

样例输出 #1

解释

他可以把这两行贫瘠的土地都用魔法转换，变成肥沃土地。然后存在 $2 \times 2$ 的正方形肥沃土地。

样例 #2

样例输入 #2

5 6 
GBBBBB
BBBBBB
BGGGGG
GGGGGG
GBBBBB

样例输出 #2

提示

对 30% 的数据满足：$n, m \leq 10$

对 60% 的数据满足：$n, m \leq 100$

对 100% 的数据满足：$n, m \leq 1000$

思路与题解

用一个前缀和查询是否可以翻转，用一个can函数维护每一次查询，再用二分法求最大值

#include <iostream>
#include <vector>

using namespace std;

int n, m;

bool can(int& k, vector<vector<int>>& preSum) {
    if (k == 0) return true;
    if (k > n || k > m) return false;
    for (int start = 0; start + k <= m; ++start){
        int cnt = 0;
        for (int i = 0; i < n; i++){
            int kSum = preSum[i][start+k] - preSum[i][start];
            if(kSum == 0 || kSum == k){
                ++cnt;
                if(cnt >= k) return true;
            } else cnt = 0;
        }
    }
    return false;
}

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

    cin >> n >> m;
    vector<string> s(n);
    for(int i=0;i<n;i++) cin >> s[i];

    vector<vector<int>> preSum(n, vector<int>(m+1, 0));
    for (int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            preSum[i][j+1] = preSum[i][j] + (s[i][j] == 'G' ? 1 : 0);
        }
    }

    int l = 1, r = min(n,m), ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(can(mid, preSum)){
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }

    cout << 1LL * ans * ans << "\n";

    return 0;
}

SB. 螺旋矩阵

传统题 时间限制：1000ms 内存限制：256MB

题目背景

输出一个 $n$ 行 $m$ 列的顺时针螺旋矩阵。

顺时针螺旋矩阵的定义是这样的：

该矩阵由 $[1, nm]$ 中的这 $n \cdot m$ 个整数组成，且每个整数恰好出现一次。
矩阵的构造方式要求如下：
- 我们一个从小到大的顺序去放置整数。
- 左上角放置整数 1，然后开始向右放置整数，直到触及边界或者已经有数字的位置；然后向下放置；然后向左；然后向上……循环这个过程直到所有数字都放置完毕。

例如，$3 \times 3$ 的顺时针螺旋矩阵是：

\[\begin{bmatrix} 1 & 2 & 3 \\ 8 & 9 & 4 \\ 7 & 6 & 5 \end{bmatrix}\]

例如，$3 \times 4$ 的顺时针螺旋矩阵是：

\[\begin{bmatrix} 1 & 2 & 3 & 4 \\ 10 & 11 & 12 & 5 \\ 9 & 8 & 7 & 6 \end{bmatrix}\]

例如，$4 \times 4$ 的顺时针螺旋矩阵是：

\[\begin{bmatrix} 1 & 2 & 3 & 4 \\ 12 & 13 & 14 & 5 \\ 11 & 16 & 15 & 6 \\ 10 & 9 & 8 & 7 \end{bmatrix}\]

输入格式

输入一行两个整数 $n, m$，意义如题目描述所示。

输出格式

输出 $n$ 行，每行 $m$ 个整数，整数之间用空格隔开，表示一个顺时针螺旋矩阵。

样例 #1

样例输入 #1

5 5

样例输出 #1

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

数据范围与提示

对于 70% 的测试数据满足 $n = m \leq 10$

对于 100% 的测试数据满足 $1 \leq n \leq 100, 1 \leq m \leq 100$

思路与题解

其实就是顺次填充，考场上写的比较丑，没使用 $next$ 数组统一重复代码

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int n,m;

pair<int,int> next(pair<int, int>cur, int c) {
    if (c % 4 == 0) return {cur.first, cur.second + 1};
    if (c % 4 == 1) return {cur.first + 1, cur.second};
    if (c % 4 == 2) return {cur.first, cur.second - 1};
    return {cur.first - 1, cur.second};
}

int main() {
    cin >> n >> m;
    vector< vector<int> > ans(n, vector<int>(m, 0));
    vector< vector<bool> > visited(n, vector<bool>(m, false));
    pair<int,int> cur = {0,0};
    int cnt = 0;
    for (int i = 1; i <= n*m; ++i) {
        if (next(cur, cnt).first >= 0 && next(cur, cnt).first < n &&
            next(cur, cnt).second >= 0 && next(cur, cnt).second < m &&
            !visited[next(cur, cnt).first][next(cur, cnt).second]) {
            ans[cur.first][cur.second] = i;
            visited[cur.first][cur.second] = true;
            cur = next(cur, cnt);
        } else {
            cnt++;
            ans[cur.first][cur.second] = i;
            visited[cur.first][cur.second] = true;
            cur = next(cur, cnt);
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

SC. 子串差距和

传统题
时间限制：500ms
内存限制：256MB

题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, ..., a_n$，定义函数 $f(l, r) = \max(a_l, a_{l+1}, ..., a_r) - \min(a_l, a_{l+1}, ..., a_r)$。求

\[\sum_{l=1}^n \sum_{r=l}^n f(l, r)\]

输入输出格式

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

一个整数，表示 $\sum_{l=1}^n \sum_{r=l}^n f(l, r)$ 的答案。

样例

输入数据 1

1 2	10 7 6 6 5 6 5 1 9 2 10

输出数据 1

约束条件

\[1 \leq n \leq 3 \times 10^6, \quad 1 \leq a_i \leq 10^9\]

Note

本题可能需要更高精度的整数类型 __int128 存储答案。__int128 在 C++ 中无对应输出方式，需自行编写，以下提供一种示例：

using int128 = __int128_t;
std::ostream& operator<<(std::ostream &os, int128 x) {
    std::string s;
    do {
        s.push_back(x % 10 + '0');
        x /= 10;
    } while (x);
    std::reverse(s.begin(), s.end());
    return os << s;
};

void solve() {
    int128 ans = 0;
    std::cout << ans << "\n";
}

思路与题解

用单调栈分别找到左边更小的元素，右边更小的元素，左边更大的元素，右边更大的元素，记录他们的角标，这样就可以得到这个元素对这个和做出的贡献，也就是加了几次，最终使用 $(maxCnt - minCnt) * arr[i]$ 计算即可

注意左端点右端点不要计重了，所以一段采用 $<$ 另一端就采用 $\le$

时间空间复杂度都是 $O(n)$ 是最优的，考场上想着维护其他数据结构不是最优的

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

using namespace std;

using i128 = __int128_t;
using ll = long long;

std::ostream& operator<<(std::ostream &os, i128 x) {
    std::string s;
    do {
        s.push_back(x % 10 + '0');
        x /= 10;
    } while (x);
    std::reverse(s.begin(), s.end());
    return os << s;
}

/*
每个元素 arr[i] 在所有区间中
作为最大值的区间数记为 maxCnt, 作为最小值的区间数记为 minCnt
它对答案的贡献就是 (maxCnt - minCnt) * arr[i]
*/
void solve()
{
    i128 ans = 0;
    int n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];

    vector<ll> lMax(n), rMax(n), lMin(n), rMin(n);
    vector<int> s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && arr[s.back()] < arr[i]) s.pop_back();
        lMax[i] = s.empty() ? -1 : s.back();
        s.push_back(i);
    }
    s.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!s.empty() && arr[s.back()] <= arr[i]) s.pop_back();
        rMax[i] = s.empty() ? n : s.back();
        s.push_back(i);
    }
    s.clear();
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && arr[s.back()] > arr[i]) s.pop_back();
        lMin[i] = s.empty() ? -1 : s.back();
        s.push_back(i);
    }
    s.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!s.empty() && arr[s.back()] >= arr[i]) s.pop_back();
        rMin[i] = s.empty() ? n : s.back();
        s.push_back(i);
    }

    for (int i = 0; i < n; ++i) {
        i128 maxCnt = (i128)(i - lMax[i]) * (rMax[i] - i);
        i128 minCnt = (i128)(i - lMin[i]) * (rMin[i] - i);
        ans += (maxCnt - minCnt) * arr[i];
    }

    std::cout << ans << "\n";
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

(´-ω-｀)

数据结构作业题解03

A. 后缀表达式

Description

Format

Input

Output

Samples

Limitation

思路与题解

B. 栈与询问

题目背景

输入格式

输出格式

样例 #1

数据范围与提示

思路与题解

C. 四角不同色

题目描述

输入格式

输出格式

样例

提示

思路与题解

D.SA. 括号替换

Description

Format

Input

Output

Samples

Limitation

思路与题解

E. 争夺土地

题目背景

题目描述

输入格式

输出格式

样例 #1

解释

样例 #2

提示

思路与题解

SB. 螺旋矩阵

题目背景

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

数据范围与提示

思路与题解

SC. 子串差距和

题目描述

输入输出格式

输入格式

输出格式

样例

输入数据 1

输出数据 1

约束条件

思路与题解