输入输出样例

# 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;}

# 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))

# 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;}

# 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])

# 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堆顶（当前中位数）。