Processing math: 100%

分类： 难度

YZOJ P2021 [APIO2014]sequence

YZOJ P2021 [APIO2014]sequence

时间限制：2000MS      内存限制：131072KB

难度： 5.7

  • 题目描述

给定一个长度为 N 的非负整数序列 a ，现要把它分割成 k+1 个连续非空的子序列。

每次分割可以选择一段剩余长度超过 1 的序列，并在其中选择一个位置，把它分割成两个连续非空的子序列。这样做可以得到一些 Bonus，为分割出的两个新序列中元素和的乘积。

现要找到一种方案，使得经过 k 次分割后，能得到的 Bonus 最多。

  • 输入格式

第一行包含两个整数 n,  k ；

第二行包含 n 个非负整数，表示序列 a 。

  • 输出格式

第一行包含一个整数，为最大 Bonus 。

第二行包含 k 个 1 到 n-1 的整数，表示最优方案。其中第 i 个数 x_i 表示在该方案中，进行第 i 次操作时，应该选择第 x_i 个数后面的位置，并将这个数所在的序列分成两部分。

如果有多个最优方案，输出其中任意一种即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

数据满足 2 \leq n \leq 100000，1 \leq k \leq min\{n-1,200\} 。

 

 

 …

YZOJ P3754 Gab数列

YZOJ P3754 Gab数列

时间限制：2000MS      内存限制：131072KB

难度： 4.5

  • 题目描述

给定数列 a_1,a_2,\cdots,a_n，定义数列 b_1,b_2,\cdots,b_m 为 Gab数列 当且仅当它满足：

1，\forall 1\le i\le m 满足 b_i\in\mathbf{N^*} 且 1\le b_i\le n

2，\sum_\limits{i=1}^{m}b_i\le k

求 \sum_\limits{i=1}^{m}a_{b_i} 的最大值。

  • 输入格式

第一行三个整数 n，m 和 k 。

第二行 n 个整数 a_i 。

  • 输出格式

输出仅一行，为最大值。

  • 样例输入

  • 样例输出

  • 样例说明

对应的 Gab数列 可以为 \{1,5,5,1,1,1\} 。

  • 数据范围

对于 15\% 的数据，n,m\le 8，k\le 50；

对于 40\% 的数据，n,m,k\le 200；

对于另外 5\% 的数据，满足 m=k；

对于另外 5\% 的数据，对于 1\le i\le j\le n，a_i\ge a_j；

对于 100\% 的数据，n\le 3000，k\le 8000，m\le 1000，1\le a_i\le 10^9，m\le k。

 

 

 …

YZOJ P2417 [FJWC2016][CF79-D]翻转硬币

YZOJ P2417 [FJWC2016][CF79-D]翻转硬币

时间限制：1000MS      内存限制：131072KB

难度： 6.0

  • 题目描述

n 枚硬币正面朝上摆成一排，给定 a_1, a_2, \cdots, a_m，每次操作可以任意选择一个 a_i，并翻转连续 a_i 个硬币。

要求经过最少次数的操作，使得仅第 x_1, x_2, \cdots, x_k 枚硬币反面朝上，输出最少次数。

  • 输入格式

第一行三个整数 n、k、m 。

第二行 k 个整数表示需要反面朝上的硬币位置，从 1 编号。

第三行 m 个整数表示 a_1, a_2, \cdots, a_m 。

  • 输出格式

一个整数表示答案，若无解，则输出 -1 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 30\% 的数据，n, m \leq 10 。 

对于 60\% 的数据，m \leq 20 。 

对于 100\% 的数据，1 \leq n \leq 10000，1 \leq k \leq 10，1 \leq m \leq 100，1 \leq a_i \leq n 。

 

 

 

Source: CF79-D…

YZOJ P2697 画圆

YZOJ P2697 画圆

时间限制：1000MS      内存限制：131072KB

难度： 5.1

  • 题目描述

在初中数学课上，Alkri 学习了圆的相关知识，他对与圆有关的问题更加感兴趣了。

Alkri 想在平面直角坐标系的第一象限中依次画 n 个与两坐标轴均相切的圆，其中，第 1 个圆的半径为 r，之后的每个圆都比上一个圆大，且与上一个圆相切，也就是说，对所有整数 2 \leq i \leq n，第 i 个圆的半径大于第 i-1 个圆的半径且与第 i-1个圆相切。

例如当 n=3 时，三个圆 C_1, C_2, C_3 如下图所示（由于 C_3 比较大，未画完整）：

现在，Alkri 很好奇：第 n 个圆的半径 R 到底有多大？他知道 R 不一定是整数（真聪明！），并且可能非常大，所以只需要你保留 R 的整数部分（向下取整）的末尾 p 位数字即可。

  • 输入格式

输入仅一行，包含三个整数 n，r，p，意义如题目所述。

  • 输出格式

输出仅一行一个整数，表示第 n 个圆的半径 R 的整数部分的末尾 p 位。注意当 R 的整数部分实际位数超过 p 时需要输满 p 位（即需要保留前导0），如果实际位数不满 p 位则不用补前导 0 。

  • 输入样例

  • 输出样例

  • 样例说明

第 10 个圆的半径整数部分为 38808989，要求输出整数部分的末尾 5 位数，因此输出 08989 。注意保留前导 0 。

  • 数据规模与约定

 

 

 …

YZOJ P3314 计算器

YZOJ P3314 计算器

时间限制：1000MS      内存限制：524288KB

出题人：zzx

难度： 3.6

  • 题目描述

你打算设计一个简单的计算器，支持计算简单的表达式。

为了简单起见，所有运算涉及的数均为整数（可以是负数），运算包含 +（加）、 -（减）、 *（乘）三种。计算时，按照先乘后加减的顺序计算，同级运算从左到右进行。表达式中可能有括号，应先计算括号内的结果，括号可能有嵌套。

形式化地，表达式的格式如下：（不含 <、 >）

< 表达式 > ：  < 运算数 1>< 运算符 1>< 运算数 2>< 运算符 2> \cdots < 运算符 k-1>< 运算数 k>（ k 为正整数）

其中，运算数可以是整数，也可以是 (< 表达式 >) 或 -(< 表达式 >) 的形式，即包含在括号内的表达式。运算符为 +、 -、 * 之一。保证任意两个 – 不相邻。

请你编写计算器的程序，计算给定的表达式的结果。

  • 输入格式

输入包含一个字符串 s，表示待计算的表达式，保证表达式符合格式，没有空格。

  • 输出格式

输出一个整数，表示计算结果。当计算结果不为 0 时，要求最高位非 0。

  • 样例输入

  • 样例输出

  • 数据规模与约定

因为是水题，所以没有具体的数据范围

1 \leq \left| s \right| \leq 10^4

 

 

 …

YZOJ P2319 宇宙图书馆

YZOJ P2319 宇宙图书馆

时间限制：1000MS      内存限制：131072KB

难度： 3.4

  • 题目描述

宇宙图书馆（Universal Library）是一个规模巨大的图书馆，该图书馆收集各个星球出版的大量系列图书。为了统一时间，宇宙图书馆的每本书的出版年份以 “宇宙年” 为单位来记录。当然，尽管图书馆可以存非常多的书，但书不能无休止地增加，因此管理员会定期剔除出版年份小于某个数的所有书。

由于书的数量多，无法手工统计，你需要编写一个图书管理系统，来管理宇宙图书馆的图书记录。

  • 输入格式

第一行为一个正整数 N，为该系统设定的出版年份上限（单位：宇宙年，之后涉及的所有出版年份均为 1 到 N 之间的正整数。

之后，每行一个合法的命令，命令有以下五种：

Add t x：添加一套共 x 本书（x 为正整数），这一套书的出版年份均为 t（单位：宇宙年）；

Remove t：删除所有出版年份小于 t （单位：宇宙年）的书，并输出被删除的书的数量；

Count a b：统计出版年份（单位：宇宙年）在 a, b 之间（含 a, b，保证 a \leq b ）的书的数量，并输出；

List x：将所有书按出版年份从大到小（也就是从新到旧）顺序列出，但由于输出可能较多，这里只要求输出列表中给定的第 x 本书的出版年份（如果不存在，输出 No）；

Quit：退出系统，结束程序。

  • 输出格式

对每个 Remove、Count、List 命令，输出一行答案。…

YZOJ P3669 [USACO2008 Mar]土地购买

YZOJ P3669 [USACO2008 Mar]土地购买

时间限制：1000MS 内存限制：262144KB

难度：6.0 （自评）

  • 题目描述

农夫 John 准备扩大他的农场，他正在考虑 N （1 \leq N \leq 1,000,000） 块长方形的土地。

每块土地的长宽满足 (1 \leq 宽 \leq 1,000,000， 1 \leq 长 \leq 1,000,000）。每块土地的价格是它的面积，但 FJ 可以同时购买多块土地。

这些土地的价格是它们最大的长乘以它们最大的宽，但是土地的长宽不能交换。如果 FJ 买一块 3 \times 5 的地和一块 5 \times 3 的地，则他需要付 5 \times 5=25。

FJ 希望买下所有的土地，但是他发现分组来买这些土地可以节省经费。他需要你帮助他求出最小的经费。

  • 输入格式

输入文件的第 1 行一个数 N， 表示土地块数。第 2 行至第 N+1 行，每行包含两个数，表示第 i 块土地的长和宽。

  • 输出格式

最小的可行费用。

  • 样例输入

  • 样例输出

 

 

 …

YZOJ P3129 [校内训练20170627]跳格子

YZOJ P3129 [校内训练20170627]跳格子

时间限制：1000MS 内存限制：524288KB

难度：7.0

  • 题目描述

在一个花园里有一排 n 个格子，这些格子编号为 1 到 n 。袋鼠喜欢在花园的格子上跳跃。

袋鼠的跳跃方式是这样的：一开始，袋鼠位于 s 号格子上，接着它会选择一个尚未经过的格子上跳跃，经过 n-1 次跳跃后，所有格子都被经过了一次，袋鼠的跳跃将结束。袋鼠总是会在 t 号格子结束跳跃。

由于袋鼠中了病毒，所以如果上一步往前跳，那么这一步必须往后跳；反之，若上一步往后跳，那么这一步往前跳。

请问袋鼠有多少种跳跃的方案呢？

形式化地，你需要求出有多少个 1 到 n 的排列 p_1, p_2, \cdots, p_n，满足：

1， p_1=s ，p_n=t；

2， 对任意 2 \leq i \leq n-1，或者 (p_i-1<p_i) \land (p_i+1<p_i) ，或者 (p_i-1>p_i) \land (p_i+1>p_i) 。

  • 输入格式

输入共一行，包含三个正整数 n, s, t 。

  • 输出格式

输出共一行，包含一个整数，表示跳跃的方案数对 1,000,000,007 取模的结果。

  • 样例输入【包含两组样例】

  • 样例输出

  • 样例 1 说明

从 2 号格子到 3 号格子的跳跃方案有两种，一种是 2,1,4,3，一种是 2,4,1,3 。

  • 数据规模与约定

 

 

 …

[CF868-F] Yet Another Minimization Problem

[CF868-F] Yet Another Minimization Problem

时间限制：1000MS 内存限制：262144KB

难度：6.0

  • 题目描述

有 n 个正整数构成序列 a ，定义一个区间 [l, r] 的代价为 满足 l \leq i, j \leq r 并使得 a_i=a_j 的无序对 [i, j] 的数量。

现要把 a 分成 k 个互不相交且不为空的连续的区间，求出在所有分法中，分出区间的最小代价和是多少。

  • 输入格式

第一行，两个正整数 n, k 。

第二行，序列 a ，共 n 个元素，用一个空格隔开。

  • 输出格式

一个整数，表示在所有分法中，分出区间的最小代价和。

  • 样例输入

  • 样例输出

  • 样例说明

一种可能的分法为 [1], [1, 3], [3, 3, 2, 1] 。

第一个区间的代价为 0 ，第二个区间的代价为 0 ，第三个区间的代价为 1 ，最小代价和为 1 。

（其他样例见原题

  • 数据范围

对于 10\% 的数据，2 \leq n \leq 20 。

对于 40\% 的数据，2 \leq n \leq 1000 。

对于 100\% 的数据，2 \leq n \leq 10^5 ，2 \leq k \leq min\{20,n\} 。

保证 1 \leq a_i \leq n 。

 

 

 

Source: CF868-F …

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

时间限制：2000MS 内存限制：262144KB

难度：5.2

  • 题目描述

给定一个长度为 n 的非负整数序列 a 和一个正整数 m 。

现在有 q 组询问，每组询问给定两个正整数 l, r ，每次可以选择满足 l \leq i \leq r 的若干个 a_i （也可以一个都不选），使得这些 a_i 的和是 m 的非负整数倍，并输出满足条件的选择方案数对 10^9+7 取模后的余数。

  • 输入格式

第一行为两个正整数 n 和 m 。

第二行为序列 a ，共 n 个元素，用一个空格隔开。

第三行为询问数 q 。

接下来的 q 行，每一行都有两个正整数，分别为 l 和 r 。

  • 输出格式

共 q 行。

第 i 行为第 i 组询问的答案。

  • 样例输入

  • 样例输出

  • 样例说明

对于第一组询问 l=1, r=2 ，有 不选、选择 5, 1 ，共 2 种情况。

对于第二组询问 l=1, r=3 ，有 不选、选择 5, 1 、选择 \(5, …