第七周作业

MT2115 五彩斑斓的世界

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

小码哥是一个喜欢字符串的男孩子。
小码哥现在有一个字符集为 a | () 的字符串，他想要对这个字符串进行化简，具体规则如下：

1. 一个纯 a 串无法被化简；
2. 一个由 | 分隔的串，可以化简为两侧较长的一个：如a | aa可化简为aa；
3. 一个带有 ( ) 的串，化简时先化简括号内的串。

由于小码哥忙于他的研究，化简这个字符串的重任被交到了你的身上。

格式

输入格式：输入一个字符集为 a | () 的字符串，为需要化简的字符串。
输出格式：由于化简后的字符串字符集仅为 a ，只需要输出化简后字符串的长度即可。

样例 1

输入：aa(aa)|(aa|(a|aa))aa
输出：4

备注

测试数据保证括号匹配，且 | 两侧与括号内均不会出现空串；
测试数据保证输入的字符串长度不超过 1 0 5 10^5 105；

相关知识点：栈

题解

读完题可确定一件事，这道题的本质是字符串化简。而在化简规则中，由于其存在()符以改变化简过程的优先级，因此这就不可避免地需要用到一个数据结构——栈（当然，也可以用递归或搜索算法，但是最节约空间和时间的一定不是这两者）。接下来说明如何利用栈来对该字符串进行化简。

历程一：栈的设计

在用栈对目标字符串进行处理时，大家首先想到的肯定都是直接设一个 stack<char> 型的栈，接下来扫描输入的字符串，若不为 ) 就入栈，若为 ) 就出栈（并开始对此栈进行 pop() 操作，直到遇到 ( 时停止），接下来对出栈操作获取到的字符串进行处理即可（因为这里获取到的字符串可能会含有 | ，这种情况下必须选其中最长的那一串 a 串作为最终的结果，并将此字串再次push()进栈内）。最终，在代码执行过程中，只要存在某一时刻栈内元素为纯 a 串时（可通过设置一个记录栈内非 a 字符元素个数的变量实现），该栈的长度就为我们所需的答案。
举个简单的例子，假设存在字符串 aa(aaa)，下面我们模拟下stack<char> s的操作过程（以及其包含的元素变动）。初始情况下，栈 s 为空。

• 首先扫描到第一个字符 a ，不为 ) 则该字符入栈，即 s=[a]；
• 接着扫描到第二个字符 a ，不为 ) 则该字符入栈，即 s=[aa]；
• 然后扫描到第三个字符 ( ，不为 ) 则该字符入栈，即 s=[aa(]；
• 继续扫描到第四个字符 a ，不为 ) 则该字符入栈，即 s=[aa(a]；
• 继续扫描到第五个字符 a ，不为 ) 则该字符入栈，即 s=[aa(aa]；
• 继续扫描到第六个字符 a ，不为 ) 则该字符入栈，即 s=[aa(aaa]；
• 最后扫描到第七个字符 ) ，为 ) 则需要执行出栈操作（直到遇见 ( 才停止）。首先出栈第一个元素（为a），于是得到子串 a，此时栈内元素为 s=[aa(aa]；然后出栈第二个元素（为a），于是得到子串 aa，此时栈内元素为 s=[aa(a]；继续出栈第三个元素（为a），于是得到子串 aa，此时栈内元素为 s=[aa(]；接着出栈第四个元素（为(），于是终止出栈行为，并对当前得到的子串进行处理。由于该子串 aa 为纯 a 串，因此处理结果就是他本身。
• 将处理得到的字串 aaa 重新入栈，即有 s=[aaaaa]。此时，由于栈内无任何非 a 元素，且原字符串输入完毕，故算法终止，输出栈长度：s.size()=5。

以上的思路是完全 OK 的，但是这样的设计却不够完美。比如，对于存在较深层次的、或数量过多的 () 包含的字符串而言，这一部分的 a 串就会反复多次地出栈入栈（且出入栈的次数与其长度成正比）。这对于追求完美的 coder 来说是这是难以忍受的（尽管这样也能 AC）。

回想前面对纯 a 串的出入栈操作，其根本目的是记录原始字符串在消除 () 时所需要保留的纯 a 串的长度。那么，为什么不直接存储 a 串的长度呢？采用这样的方式，此时就应该将该栈设置为 stack<int> s 。如此一来，每次扫描字符串时，我们就不再需要频繁地去执行 s.push() 和 s.pop() ，而是只需要执行常数级的 pop() 和 push()。但这里有个新问题：当我们设置栈元素为某段字串的 a 长度时，如何去表示 () 和 | 呢？最简单直接的方式是为其赋 “非长度定义域” 内能取到的值（如 0, -1, -2, …）。假设在算法中，我们设置 | 符对应数字 -1，( 符对应数字 -2。若继续以字符串 aa(aaa)为例来演示更新后的栈操作，其过程如下：

• 定义长度指针 strLen=0，下面进入循环（遍历字符串）;
• 首先扫描到第一个字符 a ，则 strLen++（为1）；
• 接着扫描到第二个字符 a ，则 strLen++（为2）；
• 然后扫描到第三个字符 ( ，则先将 strLen 入栈，然后再将字符 ( 入栈（此时栈内容为 s=[2 -2] ），最后重置 strLen=0；
• 接着扫描到第四个字符 a ，则 strLen++（为1）；
• 继续扫描到第五个字符 a ，则 strLen++（为2）；
• 继续扫描到第六个字符 a ，则 strLen++（为3）；
• 最后扫描到第七个字符 ) ，则先将 strLen 入栈（此时栈内容为 s=[2 -2 3] ）。算法中，只要遇到 ) 就需要执行出栈操作（直到遇见 ( 才停止）。首先出栈第一个元素 3 （此时栈内容为 s=[2 -2] ）；接下来再出栈时，遇到的是正括号标记 -2 ，则出栈操作结束。然后将得到的 a 串长度 3 回栈，即此时栈内容为 s=[2 3] 。可以看出，改进后的栈相较原来的栈而言，其出入栈操作的次数得到了极大的降低。

历程二：多重分隔符

题目并没有给出诸如 aa|aaa|aa|a 这种字符串在计算时的顺序，我一开始还觉得是题目不够严谨，但后来才发现。| 符号的计算顺序无论是从左到右还是从右到左（甚至随便找一个位置然后随机发散计算），其最后的结果都是一致的。因此，在面对类似于 aa|aaa|aa|a 这种字符串时，我们只需要知道一件事：被 | 分隔的各子串中，谁最长？最简单直接的方法是定义两个变量：一个变量为 strLen ，用以暂存当前扫描到的字符长度；另一个变量为 strLenMax ，用以存储当前扫描过程中的最大字符串长度。接下来只需要对该字符串进行一次扫描，就能获取其中的最长子串长度了。若以 aa|aaa|aa|a 为例（假设从后往前扫描）：

• 定义长度指针 strLen=0，最长子串长度变量 strLenMax=0 下面进入循环（遍历字符串）;
• 扫描到字符 a ，则 strLen++（为1）；
• 扫描到字符 | ，则判断当前子串长度是否为目前的最大值，由于 strLen=1 > strLenMax=0 ，故更新 strLenMax=strLen=1。然后重置长度指针 strLen=0 ，并继续向前扫描；
• 扫描到字符 a ，则 strLen++（为1）；
• 扫描到字符 a ，则 strLen++（为2）；
• 扫描到字符 | ，则判断当前子串长度是否为目前的最大值，由于 strLen=2 > strLenMax=1 ，故更新 strLenMax=strLen=2。然后重置长度指针 strLen=0 ，并继续向前扫描；
• 扫描到字符 a ，则 strLen++（为1）；
• 扫描到字符 a ，则 strLen++（为2）；
• 扫描到字符 a ，则 strLen++（为3）；
• 扫描到字符 | ，则判断当前子串长度是否为目前的最大值，由于 strLen=3 > strLenMax=2 ，故更新 strLenMax=strLen=3。然后重置长度指针 strLen=0 ，并继续向前扫描；
• 扫描到字符 a ，则 strLen++（为1）；
• 扫描到字符 a ，则 strLen++（为2）。由于当前字符串已经遍历完毕，故当前子串的最终长度就为 2，接下来依然判断当前子串长度是否为目前的最大值，由于 strLen=2 < strLenMax=3 ，故不必更新。
• 扫描元素字符串结束，算法终止。

以上便是这道题的所有考点，其主要考察的是对栈的理解和使用，附带考点是模拟和字符串处理的相关知识。下面给出基于以上思路的完整代码（已 AC）：

/*五彩斑斓的世界 
*/ 
#include<bits/stdc++.h> 
using namespace std;void Simplification(string str)
{stack<int> s;int strLen = 0, strLenMax, tmp;// 遍历字符串以将 a|() 串变为仅由 | 划分的数字串（此时,用数字 -1 表示分隔符 | ） for(int i=0; str[i]; i++){// 若遇到正括号，则需要对当前的字符串长度统计结果进行暂存，以进行新的统计 if(str[i] == '('){s.push(strLen);// 重置字符串统计变量 strLen = 0; // 正括号阻断标记 s.push(-2);}// 若遇到分隔符，则需要对当前的字符串长度统计结果进行暂存（便于之后进行对比） else if(str[i] == '|'){s.push(strLen);// 重置字符串统计变量 strLen = 0; // 分隔符阻断标记s.push(-1);}// 若遇到反括号，则需要对当前一段由括号框起来的字符串进行处理 else if(str[i] == ')'){// 首先将当前统计的长度入栈 s.push(strLen); // 处理当前反括号匹配的正括号之间的数据strLen = strLenMax = 0;while(1){// 将栈的顶部元素出栈 tmp = s.top();s.pop();// 若该元素为分隔符，则需要将其与前面的字串长度进行对比，并取最大值。如“aa|aaa|a|aa” if(tmp == -1){strLenMax = max(strLen, strLenMax);strLen = 0;}// 若该元素为正括号，则需要比较更前面的字符串长度else if(tmp == -2){strLenMax = max(strLen, strLenMax);s.push(strLenMax);strLen = 0;break;}// 若该元素不为分隔符或正括号，则取出当前长度else strLen += tmp;} }// 否则记当前字符串长度 +1 else strLen++;}// 为循环结束时最后记录的纯 a 串长度进行保存s.push(strLen); // 接下来需要将栈中的所有数据进行汇总处理（此步骤执行时，栈内无括号，仅含分隔符）strLen = strLenMax = s.top();s.pop();while(!s.empty()){tmp = s.top();s.pop();if(tmp != -1) strLen += tmp;else{	strLenMax = max(strLen, strLenMax);strLen = 0;}}// 打印最大值cout<<max(strLen, strLenMax);
} int main( )
{string str;// 获取输入cin>>str;// 对字符串进行化简并打印化简后的长度 Simplification(str);return 0;
}

MT2116 栈间

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

小码哥用 STL 的 stack 容器创建了一个栈，但这个容器不能从中间访问。现在他想创建一个能从中间访问的“栈”，请你协助编写一个。
新的栈能实现以下操作:
1 x // 将整数 x 压入栈
2   // 输出栈顶元素
3 i // 输出栈的第 i 个元素（从 0 数起）
4   // 弹出栈顶元素

这个栈一开始是空的。

格式

输入格式：第一行输入一个正整数 $n$，表示操作次数。
     接下来 $n$ 行，每行输入一个操作，格式如题目描述中所示。
输出格式：对于每个操作 2 和 3，输出一行一个整数表示答案。

样例1

输入：7
   1 1
   1 4
   1 3
   2
   3 1
   4
   2
输出：3
   4
   4

备注

对于 100% 的数据：$1\le n\le 5000000$；
x 在 int 类型范围内，数列为空时只进行操作 1，进行操作 3 时一定能访问到栈内元素（即保证所有操作合法）

相关知识点：栈

题解

这题没啥难度，设置一个数组和指针，然后照题目意思编码即可。
然后，
突然发现，
还他就那个 Time Limit Exceed，
我这才发现，原来读写数据也是有讲究的哦，反正这道题告诉了我一个以前不以为然的事儿，故此记录：
执行速度：scanf > cin ；printf > cout。

/*栈间
*/#include<bits/stdc++.h> 
using namespace std;const int MAX = 5000005;
int s[MAX]; int main( )
{int n, opt, num, pos = 0; cin>>n;// 执行 n 次查询 while(n--){scanf("%d", &opt);switch(opt){case 1:scanf("%d", &num);s[pos++] = num;break;case 2:printf("%d\\n",s[pos-1]);break;case 3:scanf("%d", &num);printf("%d\\n",s[num]);break;case 4:pos--;break;}}return 0;
}

MT2117 双端队列

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

小码哥想创建一个双端队列，即：两头都能进，两头都能访问，两头都能出。请你创建一个这样的双端队列并帮他实现以下操作：
1 x // 将整数 x 增加到头部
2 x // 将整数 x 增加到尾部
3    // 访间头部的元素
4    // 访问尾部的元素
5    // 弹出（删除）头部的元素
6    // 弹出（删除）尾部的元素
这个双端数列一开始是空的。

格式

输入格式：第一行输入一个正整数 $n$，表示操作次数；
     接下来 $n$ 行，每行输入一个操作，格式如题目描述中所示。
输出格式：对于每个操作 3 和 4，输出一行一个整数表示答案。

样例 1

输入：11
   1 3
   1 6
   2 9
   3
   4
   5
   2 7
   2 8
   6
   3
   4
输出：6
   9
   3
   7

备注

对于 100% 的数据：$1\le n\le 1000000$；
x 在 int 类型范围内，数列为空时只进行操 1 和 2（即保证所有操作合法）。

相关知识点：队列

题解

可能上道题的 “考点” 确实太偏了，因此这道题把数据规模降了下来。
另一方面，双端队列在 STL 中是已经实现了的，所以这道题直接调用模板即可。

/*双端队列
*/#include<bits/stdc++.h> 
using namespace std;const int MAX = 1000005;
int s[MAX]; 
deque<int> q;int main( )
{int n, opt, num; cin>>n;// 执行 n 次查询 while(n--){scanf("%d", &opt);switch(opt){case 1:cin>>num;q.push_front(num);break;case 2:cin>>num;q.push_back(num);break;case 3:cout<<q.front()<<endl;break;case 4:cout<<q.back()<<endl;break;case 5:q.pop_front();break;case 6:q.pop_back();break;}}return 0;
}

MT2123 前k小数

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

小码哥现在手上有两个长度为 $n$ 的数列 $a，b$，通过 a i + b j ( 1 ≤ i , j ≤ n ) a_i+b_j (1≤i,j≤n) ai​+bj​(1≤i,j≤n) 可以构造出 $n\times n$ 个数，求构造出的数中前 $k$ 小的数。

格式

输入格式：第一行 2 个正整数 $n,k$；
     第二行 $n$ 个数，表示数列 $a$ ；
     第二行 $n$ 个数，表示数列 $b$ 。
输出格式：从小到大输出前 $k$ 小的数。

样例 1

输入：3 3
   2 6 6
   1 4 8
输出：3 6 7

备注

其中： 1 ≤ n ≤ 1 0 4 , 1 ≤ k ≤ n ∗ n ≤ 1 0 4 , 1 ≤ a i , b j ≤ 1 0 6 1≤n≤10^4,1≤k≤n*n≤10^4,1≤a_i,b_j≤10^6 1≤n≤104,1≤k≤n∗n≤104,1≤ai​,bj​≤106

相关知识点： 堆

题解

这道题和【洛谷】 P1631 序列合并 基本相同。

☞☞☞ 详细题解

下面直接给出本题的完整 AC 代码：

/*前k小数
*/
#include<bits/stdc++.h>
using namespace std;// 变量与范围声明
const int N = 10005;
int n,k,a[N],b[N];// 自定义数据结构
struct NODE {int ida, idb, num;bool operator>(const NODE &a) const { return num > a.num;}
}node;// 定义优先队列
priority_queue<NODE,vector<NODE>,greater<NODE> > q;int main(){// 录入数据cin>>n>>k;for (int i=0; i<n; i++) cin>>a[i];for (int i=0; i<n; i++) cin>>b[i];// 排序sort(a, a+n);sort(b, b+n);// 初始化优先队列for (int i = 0; i<n; i++) q.push({i,0, a[i] + b[0]});// 开始选数while(k--){// 取最小值并出栈 node = q.top(), q.pop();// 输出结果cout << node.num << " ";// 从偏序集中取数（并更新 idb 的值）node.num = a[node.ida] + b[++node.idb];// 将取出的数入队列q.push(node);}return 0;
}

MT2124 前k小数（进阶）

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

给你 $n$ 个长度为 $m$ 的已知数列，你一次可以从每个数列中选出一个元素，共 $n$ 个数，将这 $n$ 个数的和，放入 $a$ 数组中，穷举所有的选数可能，并且都放入 $a$ 数组中。
小码哥请你计算 $a$ 数列中前 $k$ 小数是多少?

格式

输入格式：第一行3个正整数 $n,m,k$；
     接下来 $n$ 行，每行 $m$ 个数（用空格分隔），一行表示一个数列。
输出格式：从小到大输出前 $k$ 小的数。

样例1

输入：2 2 2
   1 2
   1 2
输出：2 3

备注

其中：$1\le n\le 200,1\le k\le m\le 200$。

相关知识点：堆

题解

这道题改编自 “前 k 小数” ，它将输入的数组由 2 个变为了多个（但是范围并不大），因此求解思路很简单，那就是多执行几次前面的选数过程即可（每次选择两个尚未计算的数组，此时，每一次计算都将得到当前已选数组中的前 $k$ 小数的组合值，最终整个过程就会分别选出在各数组中的前 $k$ 小组合的数值）。

/*前 k 小数（进阶） 在前面代码的基础上，每次处理两个数组（将前 k 个最小值放进一个新数组中），然后不断迭代这个过程即可 
*/
#include<bits/stdc++.h>
using namespace std;const int N = 1e8 + 5;
int n,m,k,a[N],b[N],c[N];struct NODE {int ida, idb, num;bool operator>(const NODE &a) const { return num > a.num;}
}node;priority_queue<NODE,vector<NODE>,greater<NODE> > q;int main(){cin>>n>>m>>k;for (int i =1; i<=m; i++) cin >> a[i];for (int i =1; i<=m; i++) cin >> b[i]; sort(a + 1,a+ m + 1);sort(b + 1,b+ m + 1);for (int i = 1; i<=m; i++) q.push({i,1, a[i] + b[1]});for(int i=1;i<=k; i++){node = q.top(), q.pop();c[i]=node.num; node.num = a[node.ida] + b[++node.idb];q.push(node);}n -= 2;    while(n--){while(!q.empty()) q.pop();// 将 c[] 中的内容转存至 a[] for(int i=1;i<=k;i++) a[i] = c[i];for (int i =1; i<=m; i++)  cin >> b[i];sort(b + 1,b + m + 1);for (int i = 1; i<=k; i++) q.push({i,1, a[i] + b[1]});for(int i=1;i<=k; i++){node = q.top(), q.pop();c[i]=node.num; node.num = a[node.ida] + b[++node.idb];q.push(node);}}// 输出结果for(int i=1;i<=k;i++) cout<<c[i]<<" "; return 0;
}

END