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 命令,输出一行答案。

  • 样例输入


Read the rest

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, …

YZOJ P2202 Legend VII – Ornament

YZOJ P2202 Legend VII – Ornament

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

难度:\(5.0\)

  • 题目描述

  • 输入格式

第一行有两个整数 \(N\) 和 \(Q\),表示商店有 \(N\) 个装饰品,一共有 \(Q\) 个询问。

第二行有 \(N\) 对整数,每 \(i\) 对整数 \(p_i, b_i\) 表示第 \(i\) 个装饰品的价格和好看度。

接下来 \(Q\) 行,每行两个整数 \(a, c\),分别描述 \(Q\) 个询问。

  • 输出格式

对于每个询问输出一行,一个整数表示最大好看度。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据,\(N \leq 100, Q \leq 1000\) 。

对于 \(100\%\) 的数据,\(N \leq 1000, Q \leq 100000, 1 \leq a \leq N, c \leq 1000\) 。

 

 

 …