如果你是荣誉课的学生，请你注意以下事项：
A. 排序 本题只允许使用C语言提交
题目背景 我们定义一个随机数生成器 xorshift()：
1 2 3 4 5 6 unsigned int xorshift (unsigned int x) { x ^= x << 13 ; x ^= x >> 17 ; x ^= x << 5 ; return x; }
现在，告诉你两个整数 \(n, z_0\) ，需要你用这个随机数生成器生成 \(z_1, z_2, \dots, z_n\) 。
即，\(z_i = \text{xorshift}(z_{i-1}), 1 \leq i \leq n\) 。
然后，你需要将 \(z_1, z_2, \dots, z_n\) 从小到大排序，使得 \(z_1 < z_2 < \dots < z_n\) 。
对于排序后的序列，并不要求你输出整个数列。为了防止输出量太大，你只需要输出 \(\sum_{i=1}^{n} i \cdot z_i\) 对 \(2^{32}\) 取模的结果即可。
输入格式 第一行，两个整数 \(n, z_0\) 。
输出格式 输出一个整数，表示答案（注意数据范围）。
样例 #1 样例输入 #1
样例输出 #1
样例 #2 样例输入 #2
样例输出 #2
数据范围与提示 对于 100% 的测试数据满足 \(n \leq 3 \times 10^7\) 。
一般来说，Xorshift 算法可以产生较为均匀的分布。
提示：
相同复杂度的算法，使用 STL 实现的时空间常数通常高于自己的手动实现。
如果你认为复杂度正确，但是超时，可以考虑把基于 STL 容器的实现改为手动实现。
注意数据范围，此题的数值属于 unsigned int 范畴。
样例解释
样例1的三个数排序后为：
270369 67634689 2647435461
\(\sum = 270369 + 2 \times 67634689 + 3 \times 2647435461 \mod 2^{32} = 3782878834\)
思路与题解 可以生成较为均匀的数据，所以考虑使用基数排序（LSD）
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include <stdio.h> #include <stdlib.h> #include <string.h> unsigned int xorshift (unsigned int x) x ^= x << 13 ; x ^= x >> 17 ; x ^= x << 5 ; return x; } void LSD (unsigned int * a, int n) if (n <= 1 ) return ; unsigned int * aux = (unsigned int *)malloc ((size_t )n * sizeof (unsigned int )); const int R = 1 << 16 ; unsigned int *count = (unsigned int *)malloc ((size_t )R * sizeof (unsigned int )); unsigned int *from = a; unsigned int *to = aux; for (int pass = 0 ; pass < 2 ; ++pass) { memset (count, 0 , (size_t )R * sizeof (unsigned int )); int shift = pass * 16 ; for (int i = 0 ; i < n; ++i) { unsigned int d = (from[i] >> shift) & 0xFFFFu ; count[d]++; } for (int i = 1 ; i < R; ++i) count[i] += count[i - 1 ]; for (int i = n - 1 ; i >= 0 ; --i) { unsigned int v = from[i]; unsigned int d = (v >> shift) & 0xFFFFu ; to[--count[d]] = v; } unsigned int *tmp = from; from = to; to = tmp; } if (from != a) memcpy (a, from, (size_t )n * sizeof (unsigned int )); free (aux); free (count); } int main (void ) int n; scanf ("%d" , &n); unsigned int *x = (unsigned int *)malloc ((size_t )(n + 1 ) * sizeof (unsigned int )); scanf ("%u" , &x[0 ]); for (int i = 1 ; i <= n; ++i) x[i] = xorshift (x[i - 1 ]); LSD (x+1 , n); unsigned int ans = 0 ; for (int i = 1 ; i <= n; ++i) { unsigned long long term = (unsigned long long )i * x[i]; ans += (unsigned int )term; } printf ("%u" , ans); free (x); return 0 ; }
B. 作业狂魔 题目背景 from Gym
题目描述 \(PW\) 是一个作业狂魔。
寒假里一共有 \(n\) 份作业，每份作业都有一个难度值，\(PW\) 喜欢享受洗刷作业的快感，于是必定按照作业的布置顺序完成作业。他会把作业分配到寒假每一天来完成，每一天他都必须至少完成一份作业。每天他获得的快乐值是当天所完成的这些作业中的最大难度值。
由于寒假爆发了疫情，所以假期可能会比较长，一共有 \(k\) 天。
\(PW\) 整个寒假获得的快乐值就是每天的快乐值之和。
\(PW\) 按照作业布置的从先到后的顺序告诉你每份作业的难度值。他希望你为他合理分配作业到每一天，并且输出他寒假能获得的最大快乐值。
输入格式 第一行，正整数 \(n\) ，正整数 \(k\) 。
接下来 \(n\) 个正整数，\(a_i\) ，表示按照布置顺序，给出作业的难度值。
输出格式 输出 \(PW\) 寒假的最大快乐值。
样例 #1 样例输入 #1
样例输出 #1
样例 #2 样例输入 #2
样例输出 #2
提示 对30%的数据满足：\(n \leq 100\)
对100%的数据满足：\(1 \leq k \leq n \leq 2000\) ，\(1 \leq a_i \leq 1000\)
思路与题解 这是一个动态规划问题，定义状态 \(dp[j][i]\) 表示前 \(i\) 份作业分配到 \(j\) 天所能获得的最大快乐值，则状态转移方程为：
\[dp[j][i] = \max_{k < i} (dp[j-1][k] + \max_{k < t \leq i} a_t)\]
尝试用动态规划写，好巧不巧卡了 1000ms 的限制，有几个样例 1003ms，于是采用单调栈优化，时间复杂度由 \(O(n^2k)\) 优化到 \(O(nk)\)
同时二维 dp 数组也超了，所以使用滚动数组，空间复杂度由 \(O(nk)\) 优化到 \(O(n)\)
具体思路为：
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <iostream> #include <vector> #include <climits> using namespace std;using ll = long long ;int main () ios_base::sync_with_stdio (false ); cin.tie (nullptr ); int n, k; cin >> n >> k; vector<ll> a (n + 1 ) ; for (int i = 1 ; i <= n; ++i) cin >> a[i]; const ll NEG = LLONG_MIN / 2 ; vector<long long > dp (n + 1 , NEG) , newdp (n + 1 , NEG) ; dp[0 ] = 0 ; for (int j = 1 ; j <= k; ++j) { fill (newdp.begin (), newdp.end (), NEG); vector<int > st; vector<long long > best_val; vector<long long > prefmax; for (int i = 1 ; i <= n; ++i) { long long cur_best = dp[i - 1 ]; while (!st.empty () && a[st.back ()] <= a[i]) { cur_best = max (cur_best, best_val.back ()); st.pop_back (); best_val.pop_back (); prefmax.pop_back (); } st.push_back (i); best_val.push_back (cur_best); long long res = cur_best + a[i]; if (prefmax.empty ()) prefmax.push_back (res); else prefmax.push_back (max (prefmax.back (), res)); newdp[i] = prefmax.back (); } dp.swap (newdp); } cout << dp[n]; return 0 ; }
C. 猜猜它是谁 题目描述 有一个 \(n\) 行 \(m\) 列的整数矩阵，它们每个元素都是 0。
接下来开始有两种操作：
选择矩阵的一行，给这一行所有的数字加上一个正整数。 选择矩阵的一列，给这一列所有的数字加上一个正整数。 乔治以某种顺序，进行了若干次操作，每次操作都是上面的一种。但是你不知道他做了哪些操作，他会告诉你做完所有操作之后，这个矩阵上每个数字是什么。
不过，调皮的乔治，偷偷选择了某个数字，把他改成了 \(-1\) 。
他问你，这个被改的数字，本来应该是什么？
输入格式 第一行，两个正整数 \(n, m\) 分别表示矩阵的行和列数。
接下来 \(n\) 行，每行 \(m\) 个整数，其中第 \(i\) 行第 \(j\) 列的整数表示 \(a_{ij}\) 。
保证矩阵里面有且仅有一个整数是 \(-1\) 。
输出格式 输出这个被改为 \(-1\) 的数字原本是什么。
样例 输入数据 1
输出数据 1
输入数据 2
1 2 3 4 5 6 5 7 1 0 0 1 0 0 1 4 3 3 4 3 3 4 4 3 3 -1 4 3 4 2 1 1 1 2 1 2 1 0 0 1 0 0 1
输出数据 2
输入数据 3
1 2 3 4 5 6 7 8 9 8 6 16 74 89 104 158 77 36 34 49 64 318 37 94 58 106 130 173 98 102 100 115 -1 184 103 73 71 86 101 155 74 93 91 106 121 176 94 84 82 97 112 166 85 50 48 61 78 135 51
输出数据 3
提示 举例解释：可以看出，乔治给第 3 行和第 3 列的每个元素都加了 1，因此右下角的数字原本应该是 2。
对 40% 的数据，满足 \(2 \leq n, m, a_{ij} \leq 10\)
对 80% 的数据，满足 \(n, m \leq 100, a_{ij} \leq 1000\)
对 100% 的数据，满足 \(2 \leq n, m \leq 1000, -1 \leq a_{ij} \leq 2 \times 10^9\) ，保证矩阵中有且仅有一个数是 \(-1\) 。
时空限制 1000ms 256MB
思路与题解 其实是一个超级暴力的解方程，假设被改的数字在第 \(x\) 行第 \(y\) 列，那么我们可以通过矩阵的其他位置的数字，计算出第 \(x\) 行和第 \(y\) 列分别被加了多少，不妨就取周围四格
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <iostream> #include <vector> using namespace std;int main () ios::sync_with_stdio (false ); cin.tie (nullptr ); int n, m; cin >> n >> m; vector<vector<int >> a (n, vector <int >(m)); int x = -1 , y = -1 ; for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < m; ++j) { cin >> a[i][j]; if (a[i][j] == -1 ) { x = i; y = j; } } } long long val = 0 ; bool ok = false ; if (!ok && x > 0 && y > 0 ) { val = 1LL * a[x][y - 1 ] + a[x - 1 ][y] - a[x - 1 ][y - 1 ]; ok = true ; } if (!ok && x > 0 && y + 1 < m) { val = 1LL * a[x - 1 ][y] + a[x][y + 1 ] - a[x - 1 ][y + 1 ]; ok = true ; } if (!ok && x + 1 < n && y > 0 ) { val = 1LL * a[x + 1 ][y] + a[x][y - 1 ] - a[x + 1 ][y - 1 ]; ok = true ; } if (!ok && x + 1 < n && y + 1 < m) { val = 1LL * a[x + 1 ][y] + a[x][y + 1 ] - a[x + 1 ][y + 1 ]; ok = true ; } if (!ok) return 0 ; cout << val; return 0 ; }
D. 探照灯 题目描述 让每个探照灯都被照亮，这是计划的一部分。
在一条直线上，有 \(n\) 个探照灯，每个探照灯有一个照射方向。具体的，第 \(i\) 个探照灯用 \(d_i\) 表示它的照射方向，方向只有 \(L\) 和 \(R\) 两种，分别表示照射左边和照射右边。
当 \(d_i = L\) 的时候，第 \(i\) 个探照灯可以照亮它左边的所有探照灯，也就是照亮编号为 \(1, 2, \ldots, i-1\) 的探照灯。
当 \(d_i = R\) 的时候，第 \(i\) 个探照灯可以照亮它右边的所有探照灯，也就是照亮编号为 \(i + 1, i + 2, \ldots, n\) 的探照灯。
现在我们已经知道了每个灯的朝向。但是我们注意到，有可能有的灯没有被任何一盏灯照亮，比如方向为 \(L\) 的两盏灯，它们对灯的照射效果很满意。
如果存在这样的情况，你有一次机会，可以选择两个相邻的探照灯，交换它们的位置，然后使得所有探照灯都被照亮。形式化的说，你可以选择一个 \(i (1 \leq i < n)\) ，然后交换 \(d_i\) 和 \(d_{i+1}\) 的值，使得一次操作后所有探照灯都被照亮。
现在，你需要判断是否需要操作，如果需要操作，输出你的操作。
输入格式 第一行，一个整数 \(n\) 。
第二行，一个长度为 \(n\) 的字符串，由字符 \(L, R\) 组成。
输出格式 输出一行，一个整数表示答案。
如果所有灯已经被照亮，那么输出 \(0\) 。
否则，如果可以通过一次题目描述中的交换操作把所有灯照亮，输出交换发生的数字的下标。（即，如果交换 \(d_i\) 与 \(d_{i+1}\) ，请输出 \(i\) ）。如果有多种合法方案，请输出下标最小的方案。
否则，如果没有合法的方案在一次操作就达成目标，输出 \(-1\) 。
样例 输入1
输出1
输入2
输出2
提示 对于 30% 的数据，满足 \(n \leq 10\)
对于 70% 的数据，满足 \(n \leq 1000\)
对于 100% 的数据，满足 \(n \leq 100000\) 。
时空限制 1000ms 25.6MB
思路与题解 考虑灯是否亮的一个数组 origin ，如果某一位为 L ，左边灯全变 1，假设这个字符串是 1 索引的，origin[1...i-1] 都是 1，差分数组 del[i]--,del[1]++，如果某一位为 R，右边灯全变 1，origin[i+1...n] 都是 1，差分数组 del[i+1]++，由于是从左往右遍历，就不管右边灯关不关闭了，这样就可以通过差分数组得到 origin 数组
由于可以翻转一次，注意到如果是 LR 交换成 RL，那么 origin 数组中 i 位置到 i+1 位置的灯都变亮了，所以只需要枚举 LR 的位置，在 origin 为 0 的时候判断是否可以翻转，并判断之后是不是全 1 即可
注意字符串是 0 索引的，并且注意边界条件
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <iostream> #include <vector> #define print(vector) \ for (auto x : vector) \ cout << x << " " ; \ cout << endl; using namespace std;int main () int n; cin >> n; string s; cin >> s; vector<int > origin (n+1 , 0 ) , del (n+2 , 0 ) ; vector<bool > change (n+1 ,false ) ; for (int i = 0 ; i < n; ++i) { if (s[i] == 'L' ) { del[i+1 ]--; del[1 ]++; } else del[i+2 ]++; } for (int i = 0 ; i < n-1 ; ++i) { if (s[i] == 'L' && s[i+1 ] == 'R' ) change[i+1 ] = true ; } for (int i = 1 ; i <= n; ++i) { origin[i] = origin[i-1 ] + del[i]; } bool hasChange = false ; int ans = 0 ; for (int i = 1 ; i <= n; ++i) { if (origin[i] == 0 ) { if (!hasChange && change[i]) { hasChange = true ; ans = i; i++; continue ; } else { cout << -1 ; return 0 ; } } } cout << ans; return 0 ; }
E.SB. 贪吃蛇大作战 Description Gromah 最近还读了一款叫做”贪吃蛇大作战”的游戏。
给定一个 \(n \times m\) 的地图，其中有些格子是空的，有些格子上有食物。初始时贪吃蛇的头在地图中的某个格子上，每次 Gromah 会控制贪吃蛇的头朝着上下左右四个方向中的一个方向移动一个单位，如果贪吃蛇的头撞到了墙（即坐标不在 \((1,1) \sim (n,m)\) 范围内），则其立即死亡；否则如果贪吃蛇的头所到达的格子上有一个食物，则贪吃蛇会吃掉这个食物，当然一个食物被吃掉之后就会消失。此外，贪吃蛇的头可以和自己的身体重合，贪吃蛇的身体在本题并不重要，保证贪吃蛇的初始位置上不存在食物。
现给定地图，贪吃蛇的头的初始位置，移动序列。如果贪吃蛇中途死亡，则输出 “GG”；否则如果贪吃蛇最后依然存活，输出贪吃蛇的食物的数量。
第一行两个整数 \(n, m\) ，表示地图大小。
接下来 \(n\) 行，每行一个长为 \(m\) 的只包含 “.”、“o”和 “@”的字符串 \(s\) ，表示地图。其中 “.” 表示没有食物，“o”表示有一个食物，“@”表示贪吃蛇的头的初始位置。
接下来一行一个只包含 “W”，“A”，“S”，“D”的字符串 \(t\) ，表示操作序列，其中 “W” 表示向上，“A” 表示向左，“S” 表示向下，“D” 表示向右。
保证地图中有且仅有一个 “@”。
Output 如果贪吃蛇中途死亡，则输出 “GG”；否则输出一个整数，表示贪吃蛇吃的食物数量。
Samples 输入样例 1
1 2 3 4 5 6 4 5 .oo.. .oo.. .oo.. ..... WASDS
输出样例 1
输入样例 2
1 2 3 4 5 6 4 5 .oo.. .oo.. .oo.. ..... WASDSDDDWWDA
输出样例 2
Limitation \(1 \leq n, m \leq 400, 1 \leq |t| \leq 10^5\)
思路与题解 全作业最简单的题，小模拟
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <iostream> #include <vector> using namespace std;int n, m;vector<vector<char >> map; string s; int count = 0 ;int initX, initY;void move (char dir) if (dir == 'W' ) { initX--; } else if (dir == 'S' ) { initX++; } else if (dir == 'A' ) { initY--; } else if (dir == 'D' ) { initY++; } } int main () cin >> n >> m; vector<char > temp (m) ; map.resize (n, temp); for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < m; ++j) { cin >> map[i][j]; if (map[i][j] == '@' ) { initX = i; initY = j; } } } cin >> s; for (auto c : s) { move (c); if (initX < 0 || initX >= n || initY < 0 || initY >= m || map[initX][initY] == '#' ) { cout << "GG" << endl; return 0 ; } else if (map[initX][initY] == 'o' ) { count++; map[initX][initY] = '.' ; } } cout << count; return 0 ; }
SA. 同构匹配 题目背景 动态匹配不够刺激，同构匹配，刺激。
题目描述 Power最近学得了一种魔法，每次操作可以把字符串中已有的两种不同的字母互换，形式化的来讲，可以选择字符 \(c_i\) 和字符 \(c_j\) ，然后把字符串中的所有字符 \(c_i\) 替换成 \(c_j\) ，同时把所有的 \(c_j\) 替换成 \(c_i\) 。比如，对于字符串 \(abbac\) ，他可以交换字符 \(b\) 和 \(c\) ，从而把字符串变成 \(accab\) ; 如果他继续交换字符 \(a\) 和 \(b\) ，那么字符串就会变成 \(bccba\) 。
考虑两个字符串 \(S\) 和 \(T\) ，我们称 \(S\) 和 \(T\) 是同构的，当且仅当 Power 在原样预览效果的前提下，能够将 \(S\) 变成了 \(T\) 。比如，\(abbac\) 和 \(bccba\) 就是同构的; 而 \(abaac\) 、\(abbac\) 、\(adae\) 、\(abb\) 这些两两之间都不同构。
现在有一个字符串 \(S\) 。然后有 \(m\) 次询问，每次询问给出两组下标 \(l_1, r_1\) 和 \(l_2, r_2\) ，表示 \(S\) 的两个子串。问子串 \(S[l_1, r_1]\) 和 \(S[l_2, r_2]\) 是否是同构的，是则输出 Yes，否则输出 No。
\(S[l, r]\) 表示的是从 \(S\) 串的第 \(l\) 个字符开始，连接到第 \(r\) 个字符形成的子串。
输入格式 第一行字符串 \(S\) 。
第二行整数 \(m\) 。
接下来 \(m\) 行每行四个整数，\(l_1, r_1, l_2, r_2\) 。表示一组询问。
输出格式 一共 \(m\) 行，每行表示询问的答案。
样例 #1 样例输入 #1
1 2 3 4 5 6 abbacaaeb 4 1 5 1 9 1 2 6 6 3 5 7 7 1 1 2 2
样例输出 #1
样例 #2 样例输入 #2
1 2 3 4 5 6 7 8 georgeianbegorge 6 1 5 2 6 1 2 6 6 1 4 1 5 2 9 2 9 1 1 5 9 3 6 13 16
样例输出 #2
提示 【数据范围】： 对于20%的数据，保证 \(r_1 - l_1 \leq 9, r_2 - l_2 \leq 9\) 。
对于50%的数据，保证 \(m = 1\)
对于100%的数据，保证 \(|S| \leq 2 \times 10^5, m \leq 10^5, 1 \leq l_1 \leq r_1 \leq |S|, 1 \leq l_2 \leq r_2 \leq |S|\) ，所有字符串由小写字母组成。
【时间限制】1000ms 【空间限制】256MB
思路与题解 哈希解
首先两个子串出现的字符种类数必须相同
然后可以按它们出现的位置组成的多重集进行哈希
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 #include <bits/stdc++.h> using namespace std;int main () ios::sync_with_stdio (false ); cin.tie (nullptr ); string s; int m; cin >> s >> m; int n = (int )s.size (); const int MOD[2 ] = {998244353 , 1000000007 }; const int BASE[2 ] = {131 , 137 }; vector<long long > pw[2 ]; vector<vector<int >> h[2 ]; for (int i = 0 ; i < 2 ; ++i) { pw[i].assign (n + 1 , 1 ); for (int j = 1 ; j <= n; ++j) { pw[i][j] = (pw[i][j - 1 ] * BASE[i]) % MOD[i]; } h[i].assign (26 , vector <int >(n + 1 , 0 )); for (int j = 0 ; j < 26 ; ++j) { for (int k = 0 ; k < n; ++k) { int v = (s[k] - 'a' == j); h[i][j][k + 1 ] = ((long long )h[i][j][k] * BASE[i] + v ) % MOD[i]; } } } auto get_hash = [&](int i, int j, int l, int r) -> int { long long res = h[i][j][r + 1 ] - (long long )h[i][j][l] * pw[i][r - l + 1 ] % MOD[i]; if (res < 0 ) res += MOD[i]; return (int )res; }; while (m--) { int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; l1--; r1--; l2--; r2--; int len1 = r1 - l1 + 1 ; int len2 = r2 - l2 + 1 ; if (len1 != len2) { cout << "No\n" ; continue ; } array<array<int ,26>,2> a{}, b{}; bool ok = true ; for (int i = 0 ; i < 2 ; ++i) { for (int j = 0 ; j < 26 ; ++j) { a[i][j] = get_hash (i, j, l1, r1); b[i][j] = get_hash (i, j, l2, r2); } } for (int i = 0 ; i < 2 ; ++i) { for (int j = 0 ; j < 26 ; ++j) { if ((a[i][j] == 0 ) != (b[i][j] == 0 )) { ok = false ; break ; } } if (!ok) break ; } if (ok) { for (int i = 0 ; i < 2 ; ++i) { array<int ,26> ha = a[i], hb = b[i]; sort (ha.begin (), ha.end ()); sort (hb.begin (), hb.end ()); if (ha != hb) { ok = false ; break ; } } } if (ok) cout << "Yes\n" ; else cout << "No\n" ; } return 0 ; }
SC. 区间乘积的分类 题目背景 from Gym
题目描述 有一个长度为 \(n\) 的整数序列 \(a_1, a_2, \ldots, a_n\) 。
接下来你需要三个值：
有多少个点对 \((l, r)\) ，满足 \(l \leq r\) 且 \(a_l \cdot a_{l+1} \cdots a_{r-1} \cdot a_r < 0\) 有多少个点对 \((l, r)\) ，满足 \(l \leq r\) 且 \(a_l \cdot a_{l+1} \cdots a_{r-1} \cdot a_r = 0\) 有多少个点对 \((l, r)\) ，满足 \(l \leq r\) 且 \(a_l \cdot a_{l+1} \cdots a_{r-1} \cdot a_r > 0\) 输入格式 第一行，正整数 \(n\) 。
接下来一行，\(n\) 个整数。
输出格式 一行三个整数，用空格隔开，分别对应题目描述中的三个问题的答案。
样例 #1 样例输入 #1
样例输出 #1
样例 #2 样例输入 #2
1 2 10 4 0 -4 3 1 2 -4 3 0 3
样例输出 #2
样例 #3 样例输入 #3
样例输出 #3
提示 对30%的数据满足：\(n \leq 1000\)
对100%的数据满足：\(1 \leq n \leq 200000\) ，\(-10^8 \leq a_i \leq 10^9\)
思路与题解 考场上的神秘思路
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <iostream> #include <vector> using namespace std;int c2i (char c) return c - '0' ; } int main () string s; cin >> s; vector<int > v (10 ,0 ) ; for (int i = 1 ; i <= 9 ; ++i) { cin >> v[i]; } vector<int > cnt (10 , 0 ) ; for (char c : s) cnt[c2i (c)]++; vector<int > need (10 , 0 ) ; for (int d = 0 ; d < 10 ; ++d) need[d] = cnt[d] - v[d]; string st; int n = s.size (); st.reserve (n); for (char c : s) { int cur = c2i (c); cnt[cur]--; if (need[cur] == 0 ) continue ; while (!st.empty ()) { int top = c2i (st.back ()); if (top < cur && cnt[top] - 1 >= need[top]) { st.pop_back (); need[top]++; } else break ; } st.push_back (c); need[cur]--; } cout << st; return 0 ; }
其实有更简单的解法
