算法

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

P10904（洛谷题面） 题目 题目描述： 小蓝正在数轴上挖矿，数轴上一共有 nnn 个矿洞，第 iii 个矿洞的坐标为 aia_iai​。小蓝从 000 出发，每次可以向左或向右移动 111 的距离，当路过一个矿洞时，就会进行挖矿作业，获得 111 单位矿石，但一个矿洞不能被多次挖掘。小蓝想知道在 移动距离不超过 mmm 的前提下，最多能获得多少单位矿石？ 输入格式： 输入的第一行包含两个正整数 n,mn,mn,m，用一个空格分隔。 第二行包含 nnn 个整数 a1,a2,⋯ ,ana_1, a_2,\cdots, a_na1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。 输出格式： 输出一行包含一个整数表示答案。 数据范围与说明： 【样例说明】 路径：0→−1→0→1→20\to -1\to 0\to 1\to 20→−1→0→1→2，可以对 {0,−1,1,2}\{0,-1,1,2\}{0,−1,1,2} 四个矿洞挖掘并获得最多 444 块矿石。 【评测用例规模与约定】 对于 20%20\%20% 的评测用例，1≤n≤1031 \le n \le...

P1305 新二叉树（洛谷题面） 题目 题目描述： 输入一串二叉树，输出其前序遍历。 输入格式： 第一行为二叉树的节点数 nnn。(1≤n≤261 \leq n \leq 261≤n≤26) 后面 nnn 行，第一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。 空节点用 * 表示 输出格式： 二叉树的前序遍历。 数据范围与说明： 输入输出样例 #1 输入： 12345676abcbdicj*d**i**j** 输出： 1abdicj 代码 1234567891011121314151617181920212223242526272829#include <bits/stdc++.h>using namespace std;struct programmer{ char lc; char rc;}lt[130];char h,h1;void d(char x){ if(x=='*'){ return; } cout<<x; d(lt[x].lc); ...

P1886 【模板】单调队列 / 滑动窗口（洛谷题面） 题目 题目描述： 有一个长为 nnn 的序列 aaa，以及一个大小为 kkk 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。 例如，对于序列 [1,3,−1,−3,5,3,6,7][1,3,-1,-3,5,3,6,7][1,3,−1,−3,5,3,6,7] 以及 k=3k = 3k=3，有如下过程： 窗口位置最小值最大值[1   3  -1] -3   5   3   6   7 −13 1  [3  -1  -3]  5   3   6   7 −33 1   3 [-1  -3   5]  3   6   7 −35 1   3  -1 [-3   5   3]  6   7 −35 1   3  -1  -3  [5   3   6]  7 36 1   3  -1  -3   5  [3   6   7]37\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} &...

P1085（洛谷题面） 题目 题目描述： 津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。 输入格式： 输入包括 777 行数据，分别表示周一到周日的日程安排。每行包括两个小于 101010 的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。 输出格式： 一个数字。如果不会不高兴则输出 000，如果会则输出最不高兴的是周几（用 1,2,3,4,5,6,71, 2, 3, 4, 5, 6, 71,2,3,4,5,6,7 分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。 数据范围与说明： NOIP2004 普及组第 1 题 2021-10-27：增加一组 hack...

约瑟夫问题（洛谷题面） 题目 题目描述： nnn 个人围成一圈，从第一个人开始报数,数到 mmm 的人出列，再由下一个人重新从 111 开始报数，数到 mmm 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。 注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1n-1n−1 名小朋友，而该题是全部出圈。 输入格式： 输入两个整数 n,mn,mn,m。 输出格式： 输出一行 nnn 个整数，按顺序输出每个出圈人的编号。 数据范围与说明： 1≤m,n≤1001 \le m, n \le 1001≤m,n≤100 输入输出样例 #1 输入： 110 3 输出： 13 6 9 2 7 1 8 5 10 4 代码 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;int main(){ int n,m; scanf("%d %d",&n,&m); queue<int>...