深基15.例2】寄包柜
题目描述
超市里有 n个寄包柜。每个寄包柜格子数量不一，第 i 个寄包柜有 a_i个格子，不过我们并不知道各个 a_i 的值。对于每个寄包柜，格子编号从 1 开始，一直到 a_i。现在有 q 次操作：
1 i j k：在第 i 个柜子的第 j 个格子存入物品 k。当 k=0 时说明清空该格子。2 i j：查询第 i个柜子的第 j个格子中的物品是什么，保证查询的柜子有存过东西。
已知超市里共计不会超过 10^7个寄包格子，a_i是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。
输入格式
第一行 2 个整数 n 和 q，寄包柜个数和询问次数。
接下来 q个整数，表示一次操作。
输出格式
对于查询操作时，输出答案，以换行隔开。
样例 #1
样例输入 #1
5 4 1 3 10000 118014 1 1 1 1 2 3 10000 2 1 1
样例输出 #1
118014 1
用vector实现可变长度的二维数组，降低时间复杂度
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, q; cin >> n >> q;
vector < vector<int> > v(n + 1);//+1防止出现段错误
while (q--) {
int flag, i, j, k;
cin >> flag;
if (flag == 1) {
cin >> i >> j >> k;
if (v[i].size() < j + 1)v[i].resize(j + 1);//第i个柜子的格子数小于j格，就给vector重新分配内存
v[i][j] = k;//存放物品k
}
else
{
cin >> i >> j;
cout << v[i][j]<<endl;
}
}
}最后发现还有用map的解法...学到了
题解 P3613 【【深基15.例2】寄包柜】 - 星海横流，岁月成碑。 - 洛谷博客 (luogu.org)
P1241 括号序列
题目描述
定义如下规则：
- 空串是「平衡括号序列」
- 若字符串 SS 是「平衡括号序列」，那么 \texttt{[}S\texttt][S] 和 \texttt{(}S\texttt)(S) 也都是「平衡括号序列」
- 若字符串 AA 和 BB 都是「平衡括号序列」，那么 ABAB（两字符串拼接起来）也是「平衡括号序列」。
例如，下面的字符串都是平衡括号序列：
()，[]，(())，([])，()[]，()[()]
而以下几个则不是：
(，[，]，)(，())，([()
现在，给定一个仅由 (，)，[，]构成的字符串 ss，请你按照如下的方式给字符串中每个字符配对：
- 从左到右扫描整个字符串。
- 对于当前的字符，如果它是一个右括号，考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应（即小括号匹配小括号，中括号匹配中括号），则将二者配对。如果左侧未匹配的左括号不存在或与之不对应，则其配对失败。
配对结束后，对于 ss 中全部未配对的括号，请你在其旁边添加一个字符，使得该括号和新加的括号匹配。
输入格式
输入只有一行一个字符串，表示 ss。
输出格式
输出一行一个字符串表示你的答案。
输入输出样例
输入 #1复制
([()
输出 #1复制
()[]()
输入 #2复制
([)
输出 #2复制
()[]()
说明/提示
数据规模与约定
对于全部的测试点，保证 ss 的长度不超过 100，且只含 (，)，[，] 四个字符。
这个题目的匹配规则说的不是很清楚，样例输出也模棱两可，导致理解起来很困难，如果按照自己理解简单去写大概率会出错！！！
这里某位博主给出了一组测试数据，对照这个数据理解起来会好一点
题解 P1241 【括号序列】 - SYJ 的博客 - 洛谷博客 (luogu.com.cn)
输入：( [ ) ] )
输出：( [ ( ) ] )
总之就是，对于输入的右括号{以“）”这个为例}，从离他左边最近的括号开始匹配，匹配对象是没有匹配成功的左括号（若匹配的是已经匹配成功的左括号，忽略它），分为两种情况：（1）匹配到"(",且这个“(”没有被其它括号匹配成功，那么这个输入的右括号匹配成功，结束匹配
（2）匹配到‘[’,且这个‘[’没有被其它括号匹配成功，那么这个有括号匹配失败，结束匹配。
其实看代码比文字说明会更好理解
#include<bits/stdc++.h>
using namespace std;
int flag[101]; // 记录是否匹配成功
int main()
{
int i, j;
string s;
cin >> s;
for (i = 0; i < s.length(); i++) {//处理右括号，不管左括号
if (s[i] == ')') {
for (j = i - 1; j >= 0; j--) {
if (s[j] == '(' && flag[j] == 0) { // 判断是否为没匹配成功的左括号'('
flag[i] = flag[j] = 1;
break;
}
else if (s[j] == '[' && flag[j] == 0) break; // 匹配到未匹配成功的'['，匹配失败
}
}
else if (s[i] == ']') {
for (j = i - 1; j >= 0; j--) {
if (s[j] == '[' && flag[j] == 0) {
flag[i] = flag[j] = 1;
break;
}
else if (s[j] == '(' && flag[j] == 0)
break;
}
}
}
for (i = 0; i < s.length(); i++) {
if (flag[i] == 0) { //
if (s[i] == '(' || s[i] == ')') cout << "()";//补齐
else cout << "[]";
}
else cout << s[i];
}
return 0;
}