题解

【NOIP 2015 提高组】跳石头（洛谷题面） 题目 题目描述： 一年一度的“跳石头”比赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 NNN 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 MMM 块岩石（不能移走起点和终点的岩石）。 输入格式： 第一行包含三个整数 L,N,ML,N,ML,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1L \geq 1L≥1 且 N≥M≥0N \geq M \geq 0N≥M≥0。 接下来 NNN 行，每行一个整数，第 iii 行的整数 Di (0<Di<L)D_i\,( 0 < D_i < L)Di​(0<Di​<L)， 表示第 iii...

P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows（洛谷题面） 题目 题目描述： 农夫约翰建造了一座有 nnn 间牛舍的小屋，牛舍排在一条直线上，第 iii 间牛舍在 xix_ixi​ 的位置，但是约翰的 mmm 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。 牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？ 输入格式： 第一行用空格分隔的两个整数 nnn 和 mmm； 下面 nnn 行为 nnn 个用空格隔开的整数，表示位置 xix_ixi​。 输出格式： 一行一个整数，表示最大的最小距离值。 数据范围与说明： 【样例解析】把牛放在 111，444，888 这三个位置，距离是 333。容易证明最小距离已经最大。 【数据范围】对于 100%100\%100% 的数据，2≤n≤1052 \le n \le...

P1102 A-B 数对（洛谷题面） 题目 题目描述： 给出一串正整数数列以及一个正整数 CCC，要求计算出所有满足 A−B=CA - B = CA−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。 输入格式： 输入共两行。 第一行，两个正整数 N,CN,CN,C。 第二行，NNN 个正整数，作为要求处理的那串数。 输出格式： 一行，表示该串正整数中包含的满足 A−B=CA - B = CA−B=C 的数对的个数。 数据范围与说明： 对于 75%75\%75% 的数据，1≤N≤20001 \leq N \leq 20001≤N≤2000。 对于 100%100\%100% 的数据，1≤N≤2×1051 \leq N \leq 2 \times 10^51≤N≤2×105，0≤ai<2300 \leq a_i <2^{30}0≤ai​<230，1≤C<2301 \leq C < 2^{30}1≤C<230。 2017/4/29 新添数据两组 输入输出样例 #1 输入： 124 11 1 2 3 输出： 13 ...

P11395 题目 题目描述： 喵喵喵群里面，吃喵喵是坏文明。 现在群友有 qqq 个问题，每个问题形如 A or B?，其中 A,BA,BA,B 为仅含小写字母的非空字符串。 对于每个问题，你可以回答 AAA 或 BBB 中的任意一个不是 eat 的字符串。特别地，如果 AAA 和 BBB 都是 eat，你需要回答 or。 输入格式： 输入的第一行有一个正整数 qqq，表示问题的数量。 之后有 qqq 行，每行有一个问题。 输出格式： 对于每个问题，输出一行一个字符串，表示你对于这个问题的答案。 数据范围与说明： 【样例 1 解释】 对于第一个问题，你可以从 yummy 和 yucky 两个单词中的任意一个，所以既可以回答 yummy 也可以回答 yucky。注意：在这个问题输出 or 将导致答案错误。 对于第二个问题，因为第一个单词是 eat，要避开，因此必须输出 stick。 对于第三个问题，因为第二个单词是 eat，要避开，因此必须输出 rua。 对于第四个问题，两个单词都是 eat，所以要输出 or。 【样例 2 解释】 本样例共有 323232...

【模板】堆（洛谷题面） 题目 题目描述： 给定一个数列，初始为空，请支持下面三种操作： 给定一个整数 xxx，请将 xxx 加入到数列中。 输出数列中最小的数。 删除数列中最小的数（如果有多个数最小，只删除 111 个）。 输入格式： 第一行是一个整数，表示操作的次数 nnn。 接下来 nnn 行，每行表示一次操作。每行首先有一个整数 opopop 表示操作类型。 若 op=1op = 1op=1，则后面有一个整数 xxx，表示要将 xxx 加入数列。 若 op=2op = 2op=2，则表示要求输出数列中的最小数。 若 op=3op = 3op=3，则表示删除数列中的最小数。如果有多个数最小，只删除 111 个。 输出格式： 对于每个操作 222，输出一行一个整数表示答案。 数据范围与说明： 【数据规模与约定】 对于 30%30\%30% 的数据，保证 n≤15n \leq 15n≤15。 对于 70%70\%70% 的数据，保证 n≤104n \leq 10^4n≤104。 对于 100%100\%100% 的数据，保证 1≤n≤1061 \leq n...

P1229 题目 题目描述： 我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树： 所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。 输入格式： 共两行，第一行表示该二叉树的前序遍历结果 s1s_1s1​，第二行表示该二叉树的后序遍历结果 s2s_2s2​。 保证至少存在一棵二叉树满足给出的信息，s1,s2s _ 1, s _ 2s1​,s2​ 中只含小写字母，且在某个字符串中不存在相同的字母。 输出格式： 输出可能的中序遍历序列的总数，结果不超过 263−12^{63}-1263−1。 数据范围与说明： 输入输出样例 #1 输入： 12abc cba 输出： 14 ...

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; ...