输入输出样例

# P1229 遍历问题## 题目描述我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。## 输入格式共两行，第一行表示该二叉树的前序遍历结果 s_1，第二行表示该二叉树的后序遍历结果 s_2。保证至少存在一棵二叉树满足给出的信息，s _ 1, s _ 2 中只含小写字母，且在某个字符串中不存在相同的字母。## 输出格式输出可能的中序遍历序列的总数，结果不超过 2^{63}-1。#1##1```abccba```##1```4```定义 dfs(preL, preR, postL, postR)返回该区间对应的中序序列数。根 = pre[preL]，在后序中找到根的位置 postRootIdx。左子树长度 = postRootIdx - postL。如果左子树长度 == 0（即 pre[preL+1] 不存在或 pre[preL+1] == post[postR-1] 吗？要仔细判断）—— 实际上判断条件：前序第二个字符 pre[preL+1] 在后序中的位置如果是 postR-1（即后序的倒数第二个），则说明左子树为空或右子树为空？其实应该是：前序第二个字符在后序中的位置如果是 postR-1，说明该节点只有一个孩子，且这个孩子是左孩子还是右孩子不确定。此时，总方案数 = dfs(左子树) * dfs(右子树) * 2？但注意，这里左子树长度是 1（那个孩子），右子树长度 0，所以 dfs(左子树) 是那个孩子的子树的中序方案数，dfs(右子树)=1，所以这一层方案数 = dfs(child) * 2。如果左子树长度 > 0 且 pre[preL+1] != post[postR-1]，则正常划分左右，方案数 = dfs(left) * dfs(right)。代码如下：#include <iostream>#include <string>#include <vector>using namespace std;typedef long long ll;string pre, post;vector<int> post_pos(26, -1);ll solve(int preL, int preR, int postL, int postR) {if (preL > preR) return 1;if (preL == preR) return 1;int root = pre[preL];int leftRoot = pre[preL + 1];int idx = post_pos[leftRoot - 'a'];int leftLen = idx - postL + 1;if (leftLen == 0 || pre[preL + 1] == post[postR - 1]) {// 此时 preL+1..preR 是唯一的孩子子树return solve(preL + 1, preR, postL, postR - 1) * 2;} else {ll leftCount = solve(preL + 1, preL + leftLen, postL, idx);ll rightCount = solve(preL + leftLen + 1, preR, idx + 1, postR - 1);return leftCount * rightCount;}}int main() {cin >> pre >> post;int n = pre.size();for (int i = 0; i < n; i++) {post_pos[post[i] - 'a'] = i;}ll ans = solve(0, n - 1, 0, n - 1);cout << ans << endl;return 0;}

# P2678 [NOIP 2015 提高组] 跳石头## 题目背景NOIP2015 Day2T1## 题目描述一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。## 输入格式第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$， 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。## 输出格式一个整数，即最短跳跃距离的最大值。#1##1```25 5 2211141721```##1```4```## 说明/提示### 输入输出样例 1 说明将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离 17 的岩石跳到距离 21 的岩石，或者从距离 21 的岩石跳到终点）。### 数据规模与约定对于 $20\%$的数据，$0 \le M \le N \le 10$。对于 $50\%$ 的数据，$0 \le M \le N \le 100$。对于 $100\%$ 的数据，$0 \le M \le N \le 50000,1 \le L\le 10^9$。代码如下：def main():import sysinput = sys.stdin.read().split()L = int(input[0])N = int(input[1])M = int(input[2])D = list(map(int, input[3:3+N]))def is_possible(x):prev = 0remove = 0for d in D:if d - prev < x:remove += 1else:prev = dif L - prev < x:remove += 1return remove <= Mleft, right = 1, Lans = 0while left <= right:mid = (left + right) // 2if is_possible(mid):ans = midleft = mid + 1else:right = mid - 1print(ans)if __name__ == "__main__":main()代码说明对于is_possible(x)：初始化prev=0（起点位置），remove=0（移走计数）。遍历每块岩石：若当前岩石与prev的距离<x，则移走（remove+1）；否则保留（prev更新）。最后检查最后一块保留岩石到终点的距离：若<x，需额外移走（remove+1）。返回remove≤M（是否可行最后二分查找通过不断调整左右边界，找到最大的可行x

# P1102 A-B 数对## 题目背景出题是一件痛苦的事情！相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！## 题目描述给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。## 输入格式输入共两行。第一行，两个正整数 $N,C$。第二行，$N$ 个正整数，作为要求处理的那串数。## 输出格式一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。#1##1```4 11 1 2 3```##1```3```## 说明/提示对于 $75\%$ 的数据，$1 \leq N \leq 2000$。对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。2017/4/29 新添数据两组代码如下：import sysfrom collections import defaultdictdef main():data = sys.stdin.read().split()n = int(data[0])c = int(data[1])a = list(map(int, data[2:2+n]))freq = defaultdict(int)for num in a:freq[num] += 1ans = 0if c == 0:for num, cnt in freq.items():ans += cnt * (cnt - 1)else:for num, cnt in freq.items():if num + c in freq:ans += cnt * freq[num + c]print(ans)if __name__ == "__main__":main()使用了哈希表统计每个数字出现的次数。然后分类计算：C = 0时：每个数字 x能组成的有效数对数为 cnt[x] × (cnt[x] - 1)。C ≠ 0时：对每个数字 x，若 x + C存在于哈希表中，则数对数为 cnt[x] × cnt[x + C]。此方法时间复杂度为 O(N)

# P1168 中位数## 题目描述给定一个长度为 $N$ 的非负整数序列 $A$，对于前奇数项求中位数。## 输入格式第一行一个正整数 $N$。第二行 $N$ 个正整数 $A_{1\dots N}$。## 输出格式共 $\lfloor \frac{N + 1}2\rfloor$ 行，第 $i$ 行为 $A_{1\dots 2i - 1}$ 的中位数。#1##1```71 3 5 7 9 11 6```##1```1356```#2##2```73 1 5 9 8 7 6```##2```3356```## 说明/提示对于 $20\%$ 的数据，$N \le 100$；对于 $40\%$ 的数据，$N \le 3000$；对于 $100\%$ 的数据，$1 \le N ≤ 100000$，$0 \le A_i \le 10^9$。代码如下#include <iostream>#include <queue>#include <vector>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;priority_queue<int> maxHeap;priority_queue<int, vector<int>, greater<int>> minHeap;for (int i = 0; i < n; i++) {int x;cin >> x;if (maxHeap.empty() || x <= maxHeap.top()) {maxHeap.push(x);} else {minHeap.push(x);}// 调整堆大小：确保maxHeap.size() == minHeap.size() 或 maxHeap.size() == minHeap.size() + 1if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}// 奇数项（第1,3,5,...个）时输出中位数if (i % 2 == 0) {cout << maxHeap.top() << '\n';}}return 0;}先读取序列长度 n和序列元素，新元素根据与maxHeap堆顶的大小关系插入对应堆。调整堆大小：若maxHeap过大，移堆顶到minHeap；若minHeap过大，移堆顶到maxHeap。输出中位数：每处理完第1、3、5...个元素（下标为偶数），输出maxHeap堆顶（当前中位数）。

# P1087 [NOIP 2004 普及组] FBI 树## 题目描述我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2^N 的 01 串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：1. T的根结点为 R，其类型与串 S 的类型相同；2. 若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S_1 和 S_2；由左子串 S_1 构造 R 的左子树 T_1，由右子串 S_2 构造 R的右子树 T_2。现在给定一个长度为 $2^N$ 的 01 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。## 输入格式第一行是一个整数 N(0 \le N \le 10)，第二行是一个长度为 2^N 的 01 串。## 输出格式一个字符串，即 FBI 树的后序遍历序列。#1##1```310001011```##1```IBFBBBFIBFIIIFF```noip2004普及组第3题函数 build(l, r)处理子串 s[l..r]：如果 l == r，根据 s[l]返回 "B"或 "I"。否则，计算中点 mid = (l + r) / 2，递归得到左子树后序 left_str和右子树后序 right_str。判断当前子串类型：如果全 0→ "B"。如果全 1→ "I"，否则 → "F"。返回 left_str + right_str + ，当前节点类型判断全 0 / 全 1​，可以在递归时传入子串范围，检查该范围内是否所有字符相同且为 '0'或 '1'。代码如下：#include <iostream>#include <string>using namespace std;string s;int n;// 判断子串 s[l..r] 是否全为 chbool allChar(int l, int r, char ch) {for (int i = l; i <= r; i++) {if (s[i] != ch) return false;}return true;}// 递归构建后序遍历string build(int l, int r) {if (l == r) {if (s[l] == '0') return "B";else return "I";}int mid = (l + r) / 2;string leftStr = build(l, mid);string rightStr = build(mid + 1, r);// 判断当前节点类型bool has0 = !allChar(l, r, '1');bool has1 = !allChar(l, r, '0');string nodeType;if (!has0 && has1) nodeType = "I";else if (has0 && !has1) nodeType = "B";else nodeType = "F";return leftStr + rightStr + nodeType;}int main() {cin >> n;cin >> s;int len = 1 << n; // 2^n// 确保长度正确s = s.substr(0, len);cout << build(0, len - 1) << endl;return 0;}

# P1030 [NOIP 2001 普及组] 求先序排列## 题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 <=8。## 输入格式共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。## 输出格式共一行一个字符串，表示一棵二叉树的先序。#1##1```BADCBDCA```##1```ABCD```## 说明/提示**【题目来源】**NOIP 2001 普及组第三题处理树，像是在打史莱姆，史莱姆会分裂成两个小史莱姆，就像是左子树，和右子树，写这道题用了栈的思路。求先序排列，总是要先求左子树，所以可以让右子树先入栈，左子树再入栈，对栈顶的左子树处理，又有新的左右子树，通过循环操作，处理完整棵树。代码如下：n=input()m=input()list1=[]list2=[n]def check(list2):max_num=0if len(list2[len(list2)-1])==1:list1.append(list2[len(list2)-1])del list2[len(list2)-1]else:for item in list2[len(list2)-1]:if m.index(item)>max_num:max_num=m.index(item)num=max_numlist1.append(m[num])str=list2 [len(list2)-1]del list2 [len(list2)-1]num1=str.index(m[num])if str[num1+1::]!='':list2.append(str[num1+1::])if str[0:num1]!='':list2.append(str[0:num1])while(list2!=[]):check(list2)print(''.join(list1))

# P1449 后缀表达式## 题目描述所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。本题中运算符仅包含 {+-*/}。保证对于 {/}运算除数不为 0。特别地，其中 {/}运算的结果需要**向 0 取整**（即与 C++ `/` 运算的规则一致）。如{3*(5-2)+7}对应的后缀表达式为：{3.5.2.-*7.+@}。在该式中，`@` 为表达式的结束符号。`.` 为操作数的结束符号。## 输入格式输入一行一个字符串 $s$，表示后缀表达式。## 输出格式输出一个整数，表示表达式的值。#1##1```3.5.2.-*7.+@```##1```16```#2##2```10.28.30./*7.-@```##2```-7```这道题比较简单可以用栈，也可以不用栈。代码如下：import sysinput=sys.stdin.readlinestr1=input()list2=[]num=''for item in str1:if ord('0')<=ord(item)<=ord('9') or item=='.':if item!='.':num=num+itemelse:list2.append(int (num))num=''elif item=="@":breakelse:if item=="+":list2.append(list2[len(list2)-1]+list2[len(list2)-2])elif item=="-":list2.append(list2[len(list2)-2]-list2[len(list2)-1])elif item=='*':list2.append(list2[len(list2)-2]*list2[len(list2)-1])elif item=='/':list2.append(list2[len(list2)-2]//list2[len(list2)-1])del list2[len(list2)-3]del list2[len(list2)-2]print(list2[0])

# P5788 【模板】单调栈## 题目背景模板题，无背景。## 题目描述给出项数为 n 的整数数列 a{1...n}。定义函数 f(i)代表该a数列中第 i 个元素之后第一个大于 a_i 的元素的**下标**，即 f(i)=\min_{i<j\leq n, a_j > a_i} {j}。若不存在，则 f(i)=0。试求出 f(1...n)。## 输入格式第一行一个正整数 n。第二行 n 个正整数 a{1...n}。## 输出格式一行 n个整数表示 f(1), f(2), ..., f(n) 的值。#1##1```51 4 2 3 5```##1```2 5 4 5 0```这道题是一道模板题，跟书上的奶牛向右看一样，具体做法是从后往前遍历，栈内存储数列的序号，最开始空栈则入栈，遍历到小于栈顶则入栈，遍历到大于等于的栈顶则弹出栈顶，空栈入栈的将0存入数组，遍历到小于栈顶则栈顶是目标，存入一个数组。最后结束，顺序遍历数组。代码如下：#include<stdio.h>long long list1[3000005];long long list2[3000005];struct my_stack{long long a[3000005];int size;}st;void push(long long n,struct my_stack *p){p->a[p->size++]=n;}void pop(struct my_stack *p){p->size--;}int top(struct my_stack *p) {return p->a[p->size-1];}int empty(struct my_stack *p) {return p->size==0 ? 1 : 0 ;}int main (){int n;scanf("%d",&n);for (int i=0;i<n;i++)  {scanf("%lld",&list1[i]);list2[i]=list1[i];}for (int i=n-1;i>=0;i--){while(1){if (empty(&st)){push(i,&st);list2[i]=0;break;}else if (list1[i]<list1[top(&st)]){list2[i]=top(&st)+1;push(i,&st);break;}else { pop(&st);}}}for (int i=0;i<n-1;i++)  printf("%lld ",list2[i]);printf("%lld",list2[n-1]);return 0;}