思维245E · Mishap in Club
Polycarpus 最近真是倒霉！他刚在“二进制猫”咖啡馆找到一份工作，俱乐部就被盗了。所有冰淇淋都被偷走了。
在被盗的那天晚上，Polycarpus 仔细记录了所有俱乐部访客。每当有访客进入俱乐部时，Polycarpus 就在记录中写下字符“+”。同样，每当有访客离开俱乐部时，Polycarpus 就在记录中写下字符“-”。我们知道所有进出事件都是连续发生的，也就是说，没有两个事件同时发生。Polycarpus 不记得在他的轮班开始时和结束时俱乐部里是否有人。
现在警方想知道 Polycarpus 可能见过的最少不同人数。假设他能看到任何进出俱乐部的人。每个人可以任意次数地进出。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
输入的唯一一行包含一个由字符“+”和“-”组成的序列，这些字符一个接一个地书写，没有任何分隔符。字符按照相应事件发生的顺序书写。给定序列的长度为 1 到 300 个字符（含）。
输出
输出所要求的最少人数
样例
输入
+-+-+
输出
1
输入
---
输出
3
提示
难度 1400 · greedy, implementation
构造1215C · Swap Letters
Monocarp 有两个长度相等的字符串 s 和 t。两个字符串都由小写拉丁字母 “a” 和 “b” 组成。
Monocarp 想让这两个字符串 s 和 t 彼此相等。他可以任意次执行以下操作：在字符串 s 中选择一个下标 pos_1，在字符串 t 中选择一个下标 pos_2，并交换 s_{pos_1} 与 t_{pos_2}。
你必须确定 Monocarp 为使 s 和 t 相等所需执行的最少操作次数，并输出任意一个最优操作序列——或者说，使这些字符串相等是不可能的。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
第一行包含一个整数 n (1 ≤ n ≤ 2 · 10^{5})——s 和 t 的长度。
第二行包含一个由 n 个字符 “a” 和 “b” 组成的字符串 s。
第三行包含一个由 n 个字符 “a” 和 “b” 组成的字符串 t。
输出
如果不可能使这些字符串相等，输出 -1。
否则，第一行输出 k——使字符串相等所需的最少操作次数。在接下来的 k 行中，每行输出两个整数——字符串 s 中的下标和字符串 t 中的下标，用于对应的交换操作。
样例
输入
4
abab
aabb
输出
2
3 3
3 2
输入
1
a
b
输出
-1
输入
8
babbaabb
abababaa
输出
3
2 6
1 3
7 8
提示
在第一个样例中，两次操作就足够了。例如，你可以交换 s 中的第三个字母与 t 中的第三个字母。然后 s = “abbb”，t = “aaab”。然后交换 s 中的第三个字母与 t 中的第二个字母。之后 s 和 t 都等于 “abab”。
在第二个样例中，不可能使两个字符串相等。
提示
难度 1500 · constructive algorithms, greedy