彬子的Blog

P1030（洛谷题面） 题目 题目描述： 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ）。 输入格式： 共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。 输出格式： 共一行一个字符串，表示一棵二叉树的先序。 数据范围与说明： 【题目来源】 NOIP 2001 普及组第三题 输入输出样例 #1 输入： 12BADCBDCA 输出： 1ABCD 题意 简述： 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ）。 代码 C++ 12345678910111213141516171819#include<bits/stdc++.h>using namespace std;string a,b;void func(string x,string y){ if(x.size()>0){ char ch=y[y.size()-1]; cout<<ch; int...

P1087（洛谷题面） 题目 题目描述： 我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。 FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2N2^N2N 的 01 串 SSS 可以构造出一棵 FBI 树 TTT，递归的构造方法如下： TTT 的根结点为 RRR，其类型与串 SSS 的类型相同； 若串 SSS 的长度大于 111，将串 SSS 从中间分开，分为等长的左右子串 S1S_1S1​ 和 S2S_2S2​；由左子串 S1S_1S1​ 构造 RRR 的左子树 T1T_1T1​，由右子串 S2S_2S2​ 构造 RRR 的右子树 T2T_2T2​。 现在给定一个长度为 2N2^N2N 的 01 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。 输入格式： 第一行是一个整数 N(0≤N≤10)N(0 \le N \le 10)N(0≤N≤10)， 第二行是一个长度为 2N2^N2N 的 01...

【NOIP 2013 普及组】表达式求值（洛谷题面） 题目 题目描述： 给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。 输入格式： 一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 + 和乘法运算符 *，且没有括号，所有参与运算的数字均为 000 到 231−12^{31}-1231−1 之间的整数。 输入数据保证这一行只有 0123456789+* 这 121212 种字符。 输出格式： 一个整数，表示这个表达式的值。 注意：当答案长度多于 444 位时，请只输出最后 位，前导 不输出。 数据范围与说明： 对于 30%30\%30% 的数据，0≤0≤0≤ 表达式中加法运算符和乘法运算符的总数 ≤100≤100≤100。 对于 80%80\%80% 的数据，0≤0≤0≤ 表达式中加法运算符和乘法运算符的总数 ≤1000≤1000≤1000。 对于 100%100\%100% 的数据，0≤0≤0≤ 表达式中加法运算符和乘法运算符的总数 ≤100000≤100000≤100000。 输入输出样例...

P1739 表达式括号匹配（洛谷题面） 题目 题目描述： 假设一个表达式有英文字母（小写）、运算符（+、-、*、/）和左右小（圆）括号构成，以 @ 作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则输出 YES；否则输出 NO。表达式长度小于 255255255，左圆括号少于 202020 个。 输入格式： 一行：表达式。 输出格式： 一行：YES 或 NO。 数据范围与说明： 表达式长度小于 255255255，左圆括号少于 202020 个。 输入输出样例 #1 输入： 12*(x+y)/(1-x)@ 输出： 1YES 输入输出样例 #2 输入： 1(25+x)*(a*(a+b+b)@ 输出： 1NO 代码 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;string s;stack <int> stk;int main(){ int i=0; ...

P1449 后缀表达式（洛谷题面） 题目 题目描述： 所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。 本题中运算符仅包含 +-*/\texttt{+-*/}+-*/。保证对于 /\texttt{/}/ 运算除数不为 0。特别地，其中 /\texttt{/}/ 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。 如：3*(5-2)+7\texttt{3*(5-2)+7}3*(5-2)+7 对应的后缀表达式为：3.5.2.-*7.+@\texttt{3.5.2.-*7.+@}3.5.2.-*7.+@。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。 输入格式： 输入一行一个字符串 sss，表示后缀表达式。 输出格式： 输出一个整数，表示表达式的值。 数据范围与说明： 数据保证，1≤∣s∣≤501 \leq |s| \leq 501≤∣s∣≤50，答案和计算过程中的每一个值的绝对值不超过 10910^9109。 输入输出样例...

P5788 题目 题目描述： 给出项数为 nnn 的整数数列 a1…na_{1 \dots n}a1…n​。 定义函数 f(i)f(i)f(i) 代表数列中第 iii 个元素之后第一个大于 aia_iai​ 的元素的下标，即 f(i)=min⁡i<j≤n,aj>ai{j}f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}f(i)=mini<j≤n,aj​>ai​​{j}。若不存在，则 f(i)=0f(i)=0f(i)=0。 试求出 f(1…n)f(1\dots n)f(1…n)。 输入格式： 第一行一个正整数 nnn。 第二行 nnn 个正整数 a1…na_{1\dots n}a1…n​。 输出格式： 一行 nnn 个整数表示 f(1),f(2),…,f(n)f(1), f(2), \dots, f(n)f(1),f(2),…,f(n) 的值。 数据范围与说明： 【数据规模与约定】 对于 30%30\%30% 的数据，n≤100n\leq 100n≤100； 对于 60%60\%60%...

【模板】单调栈（P5788） 题目 题目描述： 给出项数为 nnn 的整数数列 a1…na_{1 \dots n}a1…n​。 定义函数 f(i)f(i)f(i) 代表数列中第 iii 个元素之后第一个大于 aia_iai​ 的元素的下标，即 f(i)=min⁡i<j≤n,aj>ai{j}f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}f(i)=mini<j≤n,aj​>ai​​{j}。若不存在，则 f(i)=0f(i)=0f(i)=0。 试求出 f(1…n)f(1\dots n)f(1…n)。 输入格式： 第一行一个正整数 nnn。 第二行 nnn 个正整数 a1…na_{1\dots n}a1…n​。 输出格式： 一行 nnn 个整数表示 f(1),f(2),…,f(n)f(1), f(2), \dots, f(n)f(1),f(2),…,f(n) 的值。 数据范围与说明： 【数据规模与约定】 对于 30%30\%30% 的数据，n≤100n\leq 100n≤100； 对于 60%60\%60%...

P2947 题目 题目描述： 约翰的 N(1≤N≤105)N(1\le N\le10^5)N(1≤N≤105) 头奶牛站成一排，奶牛 iii 的身高是 Hi(1≤Hi≤106)H_i(1\le H_i\le10^6)Hi​(1≤Hi​≤106)。现在，每只奶牛都在向右看。对于奶牛 iii，如果奶牛 jjj 满足 i<ji<ji<j 且 Hi<HjH_i<H_jHi​<Hj​，我们可以说奶牛 iii 可以仰望奶牛 jjj。 求出每只奶牛离她最近的仰望对象。 输入格式： 第 111 行输入 NNN，之后 NNN 行第 i+1i+1i+1 行输入一个身高 HiH_iHi​。 输出格式： 共 NNN 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 000。 数据范围与说明： 【输入说明】 666 头奶牛的身高分别为 333, 222, 666, 111, 111, 222。 【输出说明】 奶牛 1,21,21,2 仰望奶牛 333，奶牛 4,54,54,5 仰望奶牛 666，奶牛 333 和 666...

P1540 [NOIP 2010 提高组] 机器翻译（洛谷题面） 题目 题目描述： 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。 假设内存中有 MMM 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M−1M-1M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 MMM 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。 假设一篇英语文章的长度为 NNN 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。 输入格式： 共 222 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数...

P2422 题目 题目描述： kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 AiA_iAi​，AiA_iAi​ 越大，表示人感觉越舒适。在一段时间 [i,j]\left[i, j\right][i,j] 内，人的舒适程度定义为 [i,j]\left[i, j\right][i,j] 中最不舒服的那一天的感受值 ×\times× [i,j]\left[i, j\right][i,j]中每一天感受值的和。现在给出 kkk 在连续 NNN 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？ 输入格式： 第一行为 NNN，代表数据记录的天数。 第二行 NNN 个整数，代表每一天的感受值。 输出格式： 一行，表示在最舒适的一段时间中的感受值。 数据范围与说明： kkk 最开心的一段时间是第 333 天到第 555 天，开心值：(6+4+5)×4=60(6+4+5)\times4=60(6+4+5)×4=60。 对于 30%30\%30% 的数据，1≤N≤1001\le N\le 1001≤N≤100。 对于 70%70\%70% 的数据，1≤N≤20001\le...