A 括号匹配（进阶版）
分数 10
编写程序检查给定字符串中包含的括号是否正确匹配，本题中的括号有{ }、[ ]、( )、< >四种。另外再加上一个新的约束条件：当有多种括号嵌套时，嵌套的顺序应为{ → [ → ( → <，即a–g+b∗[(d∗<e–f>)]、a+[b+(c–d)∗e]都是正确的匹配，而a+(b∗[c+d])则不是正确匹配。注意本题不允许相同类型括号的嵌套，即a+(b∗(c+d))不是正确匹配。本题不需要判断表达式是否合法，只需判断字符串中包含的括号是否正确匹配。
输入格式:
第一行为一个整数n，表示字符串的个数。接下来n行，每行为一个字符串。1<n≤100，字符串长度不超过1000。
输出格式:
对于每个字符串，若为正确匹配则输出"Match" ，若不匹配则输出"Fail"。
输入样例1:
8 a+(b*[c+d]) g{b[(<c>)d]e}x [()] ((())) <>()[]{} [{}] x=y+{z+(b)} ][()输出样例1:
Fail Match Match Fail Match Fail Match Fail输入样例2:
6 {[afds(a<afd>)]}yt [()rew] <>()[wre]{} [{qw}] rew{(weq)}jjk <><{}>[][](){[{}]}输出样例2:
Match Match Match Fail Match Fail
#include<iostream> #include<cstring> #include<algorithm> #include<stack> using namespace std; const int N = 10010; int n;bool pan(string s) {stack<char>stk;for (int i = 0; i < s.size(); i++) {if (s[i] == '{') {if (stk.size() && (stk.top() == '[' || stk.top() == '(' || stk.top() == '<'|| stk.top() == '{')) {return false;}else {stk.push(s[i]);}}if (s[i] == '}') {if (!stk.size() || stk.top() != '{') {return false;}else {stk.pop();}}if (s[i] == '[') {if (stk.size()&&(stk.top() == '(' || stk.top() == '<'|| stk.top() == '[')) {return false;}else {stk.push(s[i]);}}if (s[i] == ']') {if (!stk.size() || stk.top() != '[') {return false;}else {stk.pop();}}if (s[i] == '(') {if (stk.size() && (stk.top() == '<'||stk.top()=='(')) {return false;}else {stk.push(s[i]);}}if (s[i] == ')') {if (!stk.size() || stk.top() != '(') {//cout << stk.top() << endl;return false;}else {stk.pop();}}if (s[i] == '<') {if (stk.size()&&stk.top() == '<') {return false;}else {stk.push(s[i]);}}if (s[i] == '>') {if (!stk.size()||stk.top() != '<') {return false;}else {stk.pop();}}}if (stk.size()) {return false;}else {return true;}}void solve() {string str;cin >> str;if (pan(str)) {cout<<"Match"<<endl;}else {cout<<"Fail"<<endl;}}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;while (n--) {solve();} }
B 调皮的哈利
分数 10
贝蒂是个打字高手，打字时有不看屏幕的习惯。在一次贝蒂打字时，调皮的哈利常常趁贝蒂不注意按下Home键、End键、左右方向键和退格键。当Home键被按下时，输入光标会跳到文本最开头；当End键被按下时，输入光标会跳到文本末尾；当左/右方向键被按下时，输入光标会向左/右移动一位；当退格键被按下时，输入光标左面的一个字符会被删除。现给出贝蒂和哈利按键的字符串，其中'{'表示Home键，'}'表示End键，'<'表示左方向键，'>'表示右方向键，'#'表示退格键，其余字符均表示输入的内容，请输出屏幕上最终显示的文本。
输入格式:
输入一个字符串，长度不超过5×104，包含大小写字母、空格、下划线、{、}、<、>、#，表示贝蒂和哈利的按键序列。
输出格式:
输出为屏幕上最终显示的字符串。
输入样例1:
jlu_cc{i_love_}st输出样例1:
i_love_jlu_ccst输入样例2:
stre<<aaa输出样例2:
staaare输入样例3:
xxx>>>yyy##z<<>k输出样例3:
xxxykz输入样例4:
abcd{efghi}jklm{nopq}rs{t}uvwxyz输出样例4:
tnopqefghiabcdjklmrsuvwxyz
题解：
这一题暴力会超时，但是我用数组模拟指针出现了一点问题，所以我中和了两种方法过了。
希望有人能指正。
#include "bits/stdc++.h" using namespace std; const int N = 5e5 + 10; string str; list<char> L; struct P {char c;int next;int pre; }; P a[N]; void work1() {int now = 0;for (auto ch : str) {auto p = L.begin();switch (ch){case '#':if (now >= 1) {for (int i = 0; i < now - 1; ++i) {p++;}L.erase(p++);now--;}break;case '{':now = 0;break;case '}':now = L.size();break;case '<':now--;if (now < 0) now = 0;break;case '>':now++;if (now >= L.size()) now = L.size();break;default:for (int i = 0; i < now; i++) {p++;}L.insert(p, ch);now++;break;}}string ans = string(L.begin(), L.end());cout << ans << endl; } void work2() {int i = 0;int head = 0;int tail = N - 1;int pn = head;a[head].next = tail;a[head].pre = -1;a[tail].next = -1;a[tail].pre = head;while (i < str.size()) {if (str[i] == '{') {pn = head;}else if (str[i] == '}') {pn = a[tail].pre;}else if (str[i] == '<') {if (pn != head) {pn = a[pn].pre;}}else if (str[i] == '>') {if (pn != a[tail].pre) {pn = a[pn].next;}}else if (str[i] == '#') {if (pn != head) {int p = pn;pn = a[p].pre;a[pn].next = a[p].next;}}else {int now = i + 1;int ne = a[pn].next;a[now].c = str[i];a[now].next = ne;a[ne].pre = now;a[now].pre = pn;a[pn].next = now;pn = now;}i++;}pn = a[head].next;while (pn != tail) {cout << a[pn].c;pn = a[pn].next;} } int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);getline(cin, str);if (str.size() < 10000) {work1();}else {work2();}}
C 表达式求值
分数 10
给定一个中缀表达式，请编写程序计算该表达式的值。表达式包含+、-、*、/、^、(、)，所有运算均为二元运算，操作数均为正整数，但可能不止一位，不超过10位。运算结果为整数，值域为[−231,231)。除法运算结果若为小数则进行截尾取整。若除法运算中除数为0，则输出INVALID。幂运算须自行实现，不允许调用pow等系统函数。测试数据保证幂运算中指数为非负，底数不为0。
输入格式:
输入为多行，每行为一个长度不超过1000的字符串，表示中缀表达式。
输出格式:
对每个表达式输出一行：为一个整数（表达式的值）或为一个字符串INVALID。
输入样例:
5+(10*2)-6 8*(999+1) 1+5/(1-1) 7*2^3输出样例:
19 8000 INVALID 56
题解：
中缀表达式求解，转后缀，可以参考我的博客中缀表达式求解，这里不赘述了。注意快速幂，或者判断特解，1的多次幂。
#include<iostream> #include<unordered_map> #include<stack> #include<cstring> using namespace std; const int N = 1e5 + 10; int pro[200]; stack<int>in; stack<char>ch; string s; int qmi(int a, int b) {int res = 1;while (b) {if (b & 1) {res *= a;}a *= a;b >>= 1;}return res; } bool eval() {int b = in.top();in.pop();int a = in.top();in.pop();char c = ch.top();ch.pop();int x;if (c == '+') {x = a + b;}else if (c == '-') {x = a - b;}else if (c == '*') {x = a * b;}else if (c == '/'){if (b == 0) {return false;}else {x = a / b;}}else if (c == '^') {x = qmi(a, b);}in.push(x);return true; }int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);pro['-']=1;pro['+']=1;pro['*']=2;pro['/']=2;pro['^']=3;while (cin >> s) {bool flag = 1;for (int i = 0;i < s.size();i++) {char c = s[i];if (!flag) {break;}if (isdigit(c)) {int x = c - '0';int j = i + 1;while (j < s.size() && isdigit(s[j])) {x = x * 10 + s[j++] - '0';}i = j - 1;in.push(x);}else if (c == '(') {ch.push('(');}else if (c == ')') {while (ch.size() && ch.top() != '(') {if (!eval()) {flag = 0;break;}}if (ch.size()) {ch.pop();}}else {while (ch.size() && pro[ch.top()] >= pro[c]) {if (!eval()) {flag = 0;break;}}ch.push(c);}}while (ch.size()) {if (!eval()) {flag = 0;break;}}if (!flag) {cout << "INVALID" << endl;while (in.size()) {in.pop();}while (ch.size()) {ch.pop();}}else {cout << in.top() << endl;in.pop();}}return 0; }
D EDG
分数 10
2021年11月6日，英雄联盟全球总决赛打响，中国电子竞技战队Edward Gaming（EDG）以3:2力克韩国强敌DWG KIA（DK）战队，历史上首次夺得全球总冠军。一时间全网沸腾，大家纷纷在社交平台上直呼“edgnb”。现给定一段文本，请编写程序识别出连续的k个“edgnb”组成的字符串在该文本中出现了多少次。
输入格式:
第一行为1个整数T，表示数据组数。对于每组数据，第一行为1个字符串，表示给定的文本。第二行为1个整数k，含义如题目所述。（1≤T≤10。各组数据给定的字符串长度之和不超过105，且字符串中只包含a-z的小写字母。k≥1且k×5小于给定字符串长度）。
输出格式:
对于每组数据输出一行，为1个整数，表示所求的出现次数。
输入样例:
5 xyzedgnbabcedgnb 1 xyzedgnbabcedgnb 2 defedgnbedgnbxyz 2 edgnbedgnbedgnb 2 fxedgnbedgnbedgnbedgnbmem 3输出样例:
2 0 1 2 2数据规模:
测试点0：5≤T≤10，400≤T个字符串长度之和≤500，k=1
测试点1：5≤T≤10，400≤T个字符串长度之和≤500，k≥1
测试点2：5≤T≤10，4000≤T个字符串长度之和≤5000，k≥1
测试点3：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1
测试点4：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1
题解：
KMP就完了。
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e6 + 10; char ss[10] = "edgnb"; char s[N]; char str[N]; int ne[N]; int k; int kmp() {int ans = 0;int n = 5*k;int m = strlen(str + 1);for (int i = 2, j = 0; i <= n; i++) {while (j > 0 && s[i] != s[j + 1]) {j = ne[j];}if (s[i] == s[j + 1]) {j++;}ne[i] = j;}for (int i = 1, j = 0; i <= m; i++) {while (j > 0 && str[i] != s[j + 1]) {j = ne[j];}if (str[i] == s[j + 1]) {j++;}if (j == n) {ans++;j=ne[j];}}return ans; } void init(int k) {for (int i = 1; i < N; i++) {s[i] = 0;}int o = 1;for (int i = 1; i <= k; i++) {for (int j = 0;j <5; j++) {s[o++] = ss[j];}} }void solve() {memset(str, 0, sizeof(str));cin >> &str[1];cin >> k;init(k);//cout << s + 1 << endl;int res = kmp();cout << res << endl; }int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0; }
E 字母游戏
分数 10
波比和哈丽在玩一个字母游戏，波比给出一个字符串S，要求哈丽按照一定规则，基于该字符串算出一个数字X。
规则是：
（1）求出S的最长重复后缀P（P是S的后缀且在S中出现大于1次，例如yacbacba的最长重复后缀是acba），
（2）求出在S中去除第二长相等前后缀（S中所有相等的前后缀中第2长者，例如abcabcxxxabcabc中最长相等前后缀是abcabc，第二长的相等前后缀则是abc）后剩下的子串Q（例如abcabcxxxabcabc去除第二长相等前后缀后，剩下abcxxxabc）。
则X=P的长度+Q的长度。
注意一个字符串不能称为自己的前缀或后缀。子串Q至少为空串，其长度大于等于0，不能为负数。
请编写程序帮助哈丽根据给定字符串S，根据上述规则计算出数字X。
输入格式:
输入为若干行，每行为一个字符串，包含不超过100000个字母。
输出格式:
输出为若干行，每行一个整数，表示输入字符串所计算出的数字。
输入样例:
abcabcxxxabcabc xacbacba abc aaa输出样例:
15 12 3 3
题解：
这个题本质上就是对next数组的求解。最长重复后缀就是把字符串倒置后求最大next值。至于第二长的相等前后缀就是把next数组嵌套一次。当然一般的kmp都能用二分加kmp暴力求解。这里也给出暴力做法。注意判断负数值，没判只能拿5分。。（别问我怎么知道的）
法一：二分+kmp（（n+m）logn）
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; char a[N], b[N]; int ne[N]; int ne2[N]; string str; vector<string>ss; void init() {for (int i = 1;i < N;i++) {a[i] = 0;ne[i]=0;}for (int i = 1;str[i - 1];i++) {a[i] = str[i - 1];} } void fne(int x) {for (int i = 2, j = 0;i <= x;i++) {while (j > 0 && a[i] != a[j + 1]) {j = ne[j];}if (a[i] == a[j + 1]) {j++;}ne[i] = j;} } void fne2(int x) {for (int i = 1;ne2[i];i++) {ne2[i] = 0;}for (int i = 2, j = 0;i <= x;i++) {while (j > 0 && b[i] != b[j + 1]) {j = ne2[j];}if (b[i] == b[j + 1]) {j++;}ne2[i] = j;} } bool kmp(int x,int y) {if (x <= 0) {return false;}for (int i = 1, j = 0;i <= y-1;i++) {while (j > 0 && a[i] != b[j + 1]) {j = ne2[j];}if (a[i] == b[j + 1]) {j++;}if (j == x) {return true;}}return false; } bool find(int x,int y) {for (int i = 1;b[i];i++) {b[i] = 0;}for (int i = 1;a[y - x + i];i++) {b[i] = a[y - x + i];}//cout << b + 1 << endl;fne2(x);if (kmp(x,y)) {return true;}else {return false;}}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);while (cin >> str) {int ans = 0;int n = str.size();init();fne(n);int l = 0, r = n-1;int mid = l+r>>1;int o = 0;while (l <= r) {//cout << mid << endl;if (find(mid,n)) {if (mid > o) {o = mid;}l = mid + 1;}else {r = mid-1;}mid = (l + r )>> 1;}//cout << o << endl;//cout << ne[ne[n]] << endl;ans += o;if (n-2*ne[ne[n]]>0)ans += (n - 2 * ne[ne[n]]);cout << ans << endl;}}法二：倒置求next数组（On）
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; char str[N]; void fne(int *next,int n,char *ss) {for (int i = 2, j = 0;i <= n;i++) {while (j > 0 && ss[i] != ss[j + 1]) {j = next[j];}if (ss[i] == ss[j + 1]) {j++;}next[i] = j;} } void solve() {int n = strlen(str + 1);int ne[N] ;int ne2[N] ;char s[N] ;for (int i = n;i >= 1;i--) {s[i] = str[n - i + 1];}fne(ne, n, str);fne(ne2, n, s);int max_ne = 0;for (int i = 1;i <= n;i++) {if (max_ne < ne2[i]) {max_ne = ne2[i];}}int res = 0;if (n - 2 * ne[ne[n]] > 0) {res += (n - 2 * ne[ne[n]]);}//cout << max_ne << endl;res += max_ne;cout << res << endl;}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);while (cin >> &str[1]) {solve();} }
F 小龙猜数字
我们称一个字符串的秩为：该字符串长度减去该字符串的最短相等前后缀的长度。若该字符串不存在相等的前后缀，则其秩为0。
例如：abcabcxabcabc最短相等前后缀为abc，该字符串的秩为10。
Pororo和小龙玩猜字游戏，Pororo给出一个字符串S，小龙需计算S及S中所有前缀子串的秩之和。请编写程序帮助小龙猜数字。
输入格式:
输入为2行，第1行为字符串S的长度，第2行为具体的字符串。字符串长度不超过106。
输出格式:
输出 一个整数表示字符串S及其所有前缀的秩之和。
注：结果超出int型变量范围，请使用long long型变量。
输入样例1:
6 ababab输出样例1:
12样例1解释:
a的秩为0，ab的秩为0，aba的秩为2，abab的秩为2，ababa的秩为4，ababab的秩为4。
输入样例2:
10 bbcabbabbc输出样例2:
32
题解：
求最短相等前后缀就是求next数组后依次嵌套。
#include<iostream> #include<cstring> using namespace std; const int N = 1e6 + 10; char a[N]; int ne[N]; int n; int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;cin >> &a[1];//cout << a+1 << endl;for (int i = 2, j = 0; i <= n; i++) {while (j > 0 && a[i] != a[j + 1]) {j = ne[j];}if (a[i] == a[j + 1]) {j++;}ne[i] = j;}for (int i = 1; i <= n; i++) {if (ne[i] == 0) {continue;}else {if (ne[ne[i]] == 0) {continue;}else {ne[i] = ne[ne[i]];}}}long long ans = 0;for (int i = 1; i <= n; i++) {if (ne[i] == 0) {continue;}else {ans += (i - ne[i]);}}cout << ans; }
![[c++高阶]AVL树的深度剖析模拟实现](https://i-blog.csdnimg.cn/direct/c3a7cb352c8349ca9b6abf5b1e237502.png)
