题解

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

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

P2629 题目 题目描述： Uim 在公司里面当秘书，现在有 nnn 条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于老板之前的心情加上这条消息的好坏度。最开始老板的心情是 000，一旦老板心情到了 000 以下就会勃然大怒，炒了 Uim 的鱿鱼。 Uim 为了不被炒，提前知道了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望知道如何才能不让老板发怒。 Uim 可以使用一种叫 “倒叙” 的手法，例如有 nnn 条消息，Uim 可以任取一个整数 kkk（1≤k≤n1 \leq k \leq n1≤k≤n），先从 kkk 事件通报到 nnn 事件，再从 111 事件通报到 k−1k-1k−1 事件。特别的，当 k=1k=1k=1 时按照原顺序通报。 他希望知道，有多少个这样的 kkk 可以让老板不发怒。 输入格式： 第一行一个整数 nnn（1≤n≤1061 \le n \le10^61≤n≤106），表示有 nnn 个消息。 第二行 nnn 个整数，按时间顺序给出第 iii 条消息的好坏度...

P1714 题目 题目描述： 今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 nnn 个相同的小块，每小块都有对应的幸运值。 小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 m(m≤n)m(m\le n)m(m≤n) 小块的蛋糕。 请你帮他从这 nnn 小块中找出连续的 k(1≤k≤m)k(1 \le k\le m)k(1≤k≤m) 块蛋糕，使得其上的总幸运值最大。 形式化地，在数列 {pn}\{p_n\}{pn​} 中，找出一个子段 [l,r](r−l+1≤m)[l,r](r-l+1\le m)[l,r](r−l+1≤m)，最大化 ∑i=lrpi\sum\limits_{i=l}^rp_ii=l∑r​pi​。 输入格式： 第一行两个整数 n,mn,mn,m。分别代表共有 nnn 小块蛋糕，小 Z 最多只能吃 mmm 小块。 第二行 nnn 个整数，第 iii 个整数 pip_ipi​ 代表第 iii 小块蛋糕的幸运值。 输出格式： 仅一行一个整数，即小 Z 能够得到的最大幸运值。 数据范围与说明： ...

P2032 题目 题目描述： 有一个 1×n1 \times n1×n 的矩阵，有 nnn 个整数。 现在给你一个可以盖住连续 kkk 个数的木板。 一开始木板盖住了矩阵的第 1∼k1 \sim k1∼k 个数，每次将木板向右移动一个单位，直到右端与第 nnn 个数重合。 每次移动前输出被覆盖住的数字中最大的数是多少。 输入格式： 第一行两个整数 n,kn,kn,k，表示共有 nnn 个数，木板可以盖住 kkk 个数。 第二行 nnn 个整数，表示矩阵中的元素。 输出格式： 共 n−k+1n - k + 1n−k+1 行，每行一个整数。 第 iii 行表示第 i∼i+k−1i \sim i + k - 1i∼i+k−1 个数中最大值是多少。 数据范围与说明： 对于 20%20\%20% 的数据，1≤k≤n≤1031 \leq k \leq n \leq 10^31≤k≤n≤103。 对于 50%50\%50% 的数据，1≤k≤n≤1041 \leq k \leq n \leq 10^41≤k≤n≤104。 对于 100%100\%100% 的数据，1≤k≤n≤2×1061...

P1440 题目 题目描述： 一个含有 nnn 项的数列，求出每一项前的 mmm 个数到它这个区间内的最小值。若前面的数不足 mmm 项则从第 111 个数开始，若前面没有数则输出 000。 输入格式： 第一行两个整数，分别表示 nnn，mmm。 第二行，nnn 个正整数，为所给定的数列 aia_iai​。 输出格式： nnn 行，每行一个整数，第 iii 个数为序列中 aia_iai​ 之前 mmm 个数的最小值。 数据范围与说明： 对于 100%100\%100% 的数据，保证 1≤m≤n≤2×1061\le m\le n\le2\times10^61≤m≤n≤2×106，1≤ai≤3×1071\le a_i\le3\times10^71≤ai​≤3×107。 输入输出样例 #1 输入： 126 27 8 1 4 3 2 输出： 123456077113 代码 1234567891011121314151617181920#include<bits/stdc++.h>using namespace std;int q[2000005],...

P8637（洛谷题面） 题目 题目描述： 有 NNN 个瓶子，编号 1∼N1 \sim N1∼N，放在架子上。 比如有 555 个瓶子： 2,1,3,5,42,1,3,5,4 2,1,3,5,4 要求每次拿起 222 个瓶子，交换它们的位置。 经过若干次后，使得瓶子的序号为： 1,2,3,4,51,2,3,4,5 1,2,3,4,5 对于这么简单的情况，显然，至少需要交换 222 次就可以复位。 如果瓶子更多呢？你可以通过编程来解决。 输入格式： 第一行：一个正整数 NNN（N<10000N<10000N<10000），表示瓶子的数目。 第二行：NNN 个正整数，用空格分开，表示瓶子目前的排列情况。 输出格式： 输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。 数据范围与说明： 时限 1 秒, 256M。蓝桥杯 2016 年第七届省赛 蓝桥杯 2016 年省赛 B 组 I 题。 输入输出样例 #1 输入： 1253 1 2 5 4 输出： 13 输入输出样例 #2 输入： 1255 4 3 2 1 输出： 12 ...