分类： 算法

[FJWC2019 Day1] 全连

[FJWC2019 Day1] 全连

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

难度： \(4.5\)

  • 题目描述

给定两个长度为 \(n\) 的序列 \(a\) 和 \(t\)，可以在其中选择一些元素构成集合 \(S\) ，使得 \(\sum\limits_{i \in S}{a_i \times t_i}\) 最大。

同时，集合 \(S\) 还要满足 \(\forall i \in S, \forall j \in (i-t_i, i+t_i)\) ， \(j \notin S\) 。

  • 输入格式

第一行一个整数 \(n\) ；

第二行 \(n\) 个整数表示序列 \(t\) ；

第三行 \(n\) 个整数表示序列 \(a\) 。

  • 输出格式

一行一个整数，即答案。

  • 样例输入

  • 样例输出

  • 样例说明

\(S=\{1,3,5\}\)，答案 \(=2 \times 3 + 2 \times 2 + 2 \times 4 = 18\) 。

  • 数据规模与约定

保证 \(t_i \leq n\) ， \(a_i \leq 10^9\) ，\(1 \leq n \leq 10^6\) 。

 

 

YZOJ P4257, YZOJ P3993…

YZOJ P3840 [2018省队集训]序列

YZOJ P3840 [2018省队集训]序列

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

难度： \(8.0\)

  • 题目描述

给定一个长度为 \(n\) 的序列 \(x\) 。

你需要从序列中选出一些位置。对于第 \(i\) 个位置，如果它被选中，你会获得 \(x_i\) 的收益；否则找到最小的 \(j\) 使得第 \(j\) 个位置到第 \(i\) 个位置都没有被选中，你需要付出 \(i-j+1\) 的代价。

此外，你选出的位置必须满足 \(x_i\) 是单调不下降的。

最大化收益减去代价的结果。

  • 输入格式

第一行一个正整数 \(n\)，第二行 \(n\) 个整数 \(x_1\) ~ \(x_n\) 。

  • 输出格式

输出一行一个整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 样例 1 说明

选择第 \(1, 3, 5, 7\) 个位置，获得收益 \(1+2+3+4=10\) ，第 \(2, 4, 6\) 个位置的代价分别为 \(1, 1, 1\) ，收益减去代价为 \(10-3=7\) 。

  • 样例 2 输入

  • 样例 2 输出

  • 数据规模与约定

对于 \(5\%\) 的数据， \(1 \leq n \leq 5\) 。…

[CEOI2017]Building Bridges

[CEOI2017]Building Bridges

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

难度： \(7.2\)

  • 题目描述

有 \(n\) 根柱子依次排列，每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\) 。

现在想要建造若干座桥，如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间，那么需要 \((h_i-h_j)^2\) 的代价。
在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)​，注意 \(w_i\) 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个空格隔开的整数，依次表示 \(h_1, h_2, \cdots, h_n\) 。

第三行 \(n\) 个空格隔开的整数，依次表示 \(w_1, w_2, \cdots, w_n\) 。

  • 输出格式

输出一行一个整数表示最小代价，注意最小代价不一定是正数。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(30\%\) 的数据，有 \(1 \leq n \leq 1000\) ；

对于另外 \(40\%\) 的数据，有 \(\left| w_i \right| \leq 20\) ，保证存在一种最优方案，除了头尾两根柱子外，最多只保留两根柱子；

对于 \(100\%\) 的数据，有 \(2 \leq n \leq 10^5\)，\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。

数据来源 LOJ 2483 。

 

 

已搬至 YZOJ P4254 。…

[SDOI2012]任务安排

[SDOI2012]任务安排

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

难度： \(7.1\)

  • 题目描述

按顺序给定 \(N\) 个子任务，每个任务用时 \(t_i\) ，费用系数 \(f_i\)。

可以把连续的若干个（或一个）子任务合成为一个大任务，大任务的用时和费用系数分别为其中每个子任务的用时之和与费用系数之和。开始一个大任务之前需要准备时间 \(S\)，一个大任务的费用为他的 完成时刻 \(\times\) 费用系数 ，问按顺序执行完所有的大任务后，最小的费用和为多少。

形式化的，将 \(N\) 个任务划分成若干个块，每一组任务 \(M_i\) 花费代价 \((T+\sum{t_j}+S) \times \sum{f_j}\)，\(j \in M_i\)，\(T\) 为执行到这个任务之前花费的时间，求执行完所有任务的最小代价和。

  • 输入格式

第一行一个整数 \(N\) ；

而后 \(N\) 行中，第 \(i\) 行包含一个可能为负的整数 \(t_i\) 和一个非负整数 \(f_i\) 。

  • 输出格式

一个整数，表示最小的代价和。

  • 样例输入

  • 样例输出

  • 样例说明

如果分组方案是 \(\{1,2\}\)、\(\{3\}\)、\(\{4,5\}\)，则完成时间分别为 \(\{5,5,10,14,14\}\)，费用 \(C=\{15,10,30,42,56\}\)，总费用就是 \(153\) 。

  • 数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq N \leq 1000\) ；

对于另外 \(40\%\) 的数据， \(1 \leq N \leq 300000\) ；

对于前 \(60\%\) 的数据，\(0 \leq t_i \leq 2^8\) ；

对于后 \(40\%\) 的数据，\(1 \leq N \leq 100000\)，\(-2^8 \leq t_i \leq 2^8\) ；

对于 \(100\%\) 的数据， \(0 \leq S, f_i …

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