彬子的Blog

P2249 【深基13.例1】查找（洛谷题面） 题目 题目描述： 输入 nnn 个不超过 10910^9109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,ana_1,a_2,\dots,a_{n}a1​,a2​,…,an​，然后进行 mmm 次询问。对于每次询问，给出一个整数 qqq，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1-1−1 。 输入格式： 第一行 222 个整数 nnn 和 mmm，表示数字个数和询问次数。 第二行 nnn 个整数，表示这些待查询的数字。 第三行 mmm 个整数，表示询问这些数字的编号，从 111 开始编号。 输出格式： 输出一行，mmm 个整数，以空格隔开，表示答案。 数据范围与说明： 数据保证，1≤n≤1061 \leq n \leq 10^61≤n≤106，0≤ai,q≤1090 \leq a_i,q \leq 10^90≤ai​,q≤109，1≤m≤1051 \leq m \leq 10^51≤m≤105 本题输入输出量较大，请使用较快的 IO 方式。 输入输出样例...

P1873 题目 题目描述： 伐木工人 Mirko 需要砍 MMM 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。 Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 HHH（米），伐木机升起一个巨大的锯片到高度 HHH，并锯掉所有树比 HHH 高的部分（当然，树木不高于 HHH 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,1020,15,1020,15,10 和 171717，Mirko 把锯片升到 151515 米的高度，切割后树木剩下的高度将是 15,15,1015,15,1015,15,10 和 151515，而 Mirko 将从第 111 棵树得到 555 米，从第 444 棵树得到 222 米，共得到 777 米木材。 Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 HHH，使得他能得到的木材至少为 MMM...

P10424（洛谷题面） 题目 题目描述： 一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位……）上的数字是奇数，偶数位（十位、千位、十万位……）上的数字是偶数，我们就称之为“好数”。 给定一个正整数 NNN，请计算从 111 到 NNN 一共有多少个好数。 输入格式： 一个整数 NNN。 输出格式： 一个整数代表答案。 数据范围与说明： 样例 1 解释 242424 以内的好数有 1,3,5,7,9,21,231,3,5,7,9,21,231,3,5,7,9,21,23，一共 777 个。 数据规模与约定 对于 10%10\%10% 的测试数据，1≤N≤1001 \leq N \le 1001≤N≤100。 对于全部的测试数据，1≤N≤1071 \le N \leq 10^71≤N≤107。 输入输出样例 #1 输入： 124 输出： 17 输入输出样例 #2 输入： 12024 输出： 1150 ...

P1017 [NOIP 2000 提高组] 进制转换（洛谷题面） 题目 题目描述： 我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以 101010 为底数的幂之和的形式。例如 123123123 可表示为 1×102+2×101+3×1001 \times 10^2+2\times 10^1+3\times 10^01×102+2×101+3×100 这样的形式。 与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数，以 222 为底数的幂之和的形式。 一般说来，任何一个正整数 RRR 或一个负整数 −R-R−R 都可以被选来作为一个数制系统的基数。如果是以 RRR 或 −R-R−R 为基数，则需要用到的数码为 0,1,…,R−10,1,\dots,R-10,1,…,R−1。 例如当 R=7R=7R=7 时,所需用到的数码是 0,1,2,3,4,5,60,1,2,3,4,5,60,1,2,3,4,5,6，这与其是 RRR 或 −R-R−R 无关。如果作为基数的数绝对值超过...

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