分类： 数据结构

YZOJ P3361 [校内训练20171117]数点问题

YZOJ P3361 [校内训练20171117]数点问题

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

出题人：zzx      难度：\(6.0\)

  • 题目描述

\(k\) 维空间内有两个点集 \(A=\{X_1,X_2,\ldots,X_m\}\)，\(B=\{Y_1,Y_2,\ldots,Y_n\}\)，每个点的坐标是一个 \(k\) 元组 \((x_1,x_2,\ldots,x_k)\)。我们称点 \(X(x_1,x_2,\ldots,x_k)\) 控制点 \(Y(y_1,y_2,\ldots,y_k)\) 当且仅当 \(\forall 1\le i\le k,x_i>y_i\)，记为 \(X>Y\)。数点问题是要求计算点 \(X_i\) 能控制 \(B\) 中的点数 \(c_i\)，即 \(c_i=\left| \{Y \in B\ |\ X_i > Y\} \right|\)。

  • 编程任务

对于给定的点集 \(A\) 和 \(B\)，求出对于所有 \(1\le i\le m\) 的 \(c_i\) 的值。

  • 输入格式

第一行有三个正整数\(m\)、\(n\) 和 \(k\)，分别表示集合 \(A\) 和 \(B\) 的基数及维数。接下来的 \(m+n\) 行依次给出点 \(X_1 , X_2 ,\ldots, X_m ,Y_1 ,Y_2 ,\ldots,Y_n\)，每个点的坐标用一行 \(k\) 个整数 \(x_1 , x_2 ,\ldots, x_k\) 描述，所有坐标在 \(int\) 范围内。

  • 输出格式

将计算出的 \(c_1 ,c_2 ,\ldots,c_m\) 依次输出到文件中，每个 \(c_i\) 输出 \(1\) 行。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于数据点 \(1\)，\(n,m\le 200,000\)，\(k=1\)…

YZOJ P3791 餐馆

YZOJ P3791 餐馆

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

难度：\(6.0\)

  • 题目描述

在一条东西向的街道上有 \(n\) 个餐馆，从西向东编号为 \(1\) 至 \(n\)，第 \(i\) 个餐馆和第 \(i+1\) 个餐馆的距离为 \(a_i\) 。

吃货小W喜欢到这条街道的餐馆里吃饭。现在，小W得到了 \(m\) 张餐票，每张餐票可以用于在街道上的任一餐馆里吃一餐。在第 \(i\) 个餐馆中，使用第 \(j\) 张餐票吃饭，可以获得的美味度为 \(b_{i,j}\) 。注意，每张餐票最多用一次，但在同一餐馆内可以使用任意多张餐票。

小W打算用完这 \(m\) 张餐票。他可以选择任一餐馆作为起点，每次吃饭时，可以选择一个餐馆，然后从当前位置（上次吃饭的地点，如果不存在则为起点）出发前往该餐馆并用任意一张未用过的餐票吃一餐，直到吃完 \(m\) 餐为止。小W希望最大化每次吃饭的美味度之和减去路上经过的总路程的值。

  • 输入格式

输入第一行包含两个正整数 \(n,m\) 。

第二行包含 \(n-1\) 个正整数 \(a_1,a_2,\cdots,a_{n-1}\) 。

接下来 \(n\) 行，每行包含 \(m\) 个正整数，其中第 \(i\) 行第 \(j\) 个数为 \(b_{i,j}\) 。

  • 输出格式

输出一行一个整数，表示所求的最大值。

  • 样例输入

  • 样例输出

  • 样例说明

最优方案如下：以餐馆 \(1\) 为起点，在餐馆 \(1\) 使用第 \(1\) 张餐票、第 \(3\) 张餐票，然后前往餐馆 \(2\) 使用第 \(2\) 张餐票、第 \(4\) 张餐票。

  • 数据规模与约定

对于所有数据，\(nm \leq 10^6\)，\(n \geq 2\)，\(a_i, b_{i, j} \leq 10^9\) 。

 

 

 

Source：ARC067 F – Yakiniku …

YZOJ P3367 魔术帽游戏

YZOJ P3367 魔术帽游戏

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

难度：\(6.0\)           出题人：zzx

  • 题目描述

有 \(n\) 顶外形相同的魔术帽和一个魔术球，每次游戏开始前，魔术帽会被倒扣放置排成一排，这些魔术帽从左到右依次编号为 \(1, 2, \cdots , n\) 。

每一局游戏，魔术球会被放在其中一顶魔术帽底下，然后进行若干次交换，每次交换时可以选出两顶魔术帽，交换它们的位置。整个过程对于小朋友们而言都是可见的。交换结束后，小朋友们可以打开魔术帽，正确找到魔术球则游戏胜利。

为了进行多局游戏，现有一个长度为 \(m\) 的操作序列 \((a_1,b_1), (a_2,b_2), \cdots ,(a_m,b_m)\)，其中 \((a_i,b_i)\) 表示反转 \(a_i\) 号和 \(b_i\) 号魔术帽之间的魔术帽的顺序（如原来魔术帽从左到右为 \(a,b,c,d,e,f,g\)，则操作 \((3,6)\) 进行后顺序变为 \(a,b,f,e,d,c,g\) 。之后，小朋友们会玩 \(q\) 局游戏。其中，第 \(j\) 轮游戏，魔术球会被放在 \(x_j\) 号魔术帽下，然后进行操作序列中 \([l_j,r_j]\) 这个片段，即依次进行反转操作 \((a_{l_j},b_{l_j}),(a_{l_j+1},b_{l_j+1}), \cdots ,(a_{r_j},b_{r_j})\) 。请求出每次游戏反转操作结束时，魔术球位于在哪一顶魔术帽下。注意：这里的魔术帽编号始终是按照位置从左到右编号的，即每次交换魔术帽之后，所有魔术帽会按照从左到右的顺序重新编号为 \(1,2,\cdots,n\) 。

  • 输入格式

第一行有三个整数 \(n,m,q\)，其中 \(n\) 代表魔术帽的数量，\(m\) 代表操作序列的长度，\(q\) 代表游戏次数。

接下来 \(m\) 行，其中第 \(i\) 行两个整数 \(a_i,b_i\)，表示操作序列的第 \(i\) 项。接下来 \(q\) 行，其中第 \(j\) 行三个正整数 \(x_j,l_j,r_j\)，表示第 \(j\) 局游戏。保证 \(1 \leq a_i \leq b_i \leq n\)，\(1 \leq x_j \leq n\)，\(1 \leq l_j \leq r_j \leq m\) 。

  • 输出格式

输出 \(q\) 行，每行一个整数，第 \(j\) 行的整数表示第 \(j\) 局游戏的交换结束后，魔术球所在的魔术帽编号。…

YZOJ P3392 越野赛车问题

YZOJ P3392 越野赛车问题

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

难度： \(6.0\)

  • 问题描述

某山上一共有 \(n\) 个广场，编号依次为 \(1\) 到 \(n\)，这些广场之间通过 \(n-1\) 条双向车道直接或间接地连接在一起。对于每条车道 \(i\)，可以用四个正整数 \(u_i, v_i, l_i, r_i\) 描述，表示车道连接广场 \(u_i\) 和 \(v_i\)，其速度承受区间为 \([l_i, r_i]\)，即汽车必须以不小于 \(l_i\) 且不大于 \(r_i\) 的速度经过车道 \(i\) 。

现计划进行 \(m\) 次训练，每次选择某山上的一条简单路径，然后在这条路径上行驶，且每次训练时的车速都是固定的。现在有在 m 次训练中分别计划使用的车速，要求一条合法的路径（车速在所有车道的速度承受区间的交集内），使得路径上经过的车道数最大。

  • 数据输入

输入文件的第一行包含两个正整数 \(n, m\)，表示广场数和训练次数。接下来 \(n-1\) 行，每行四个正整数 \(u_i, v_i, l_i, r_i ( \leq n)\)，描述所有车道。最后 \(m\) 行，每行一个正整数 \(v (\leq n)\) ，表示每次训练是的车速。

  • 结果输出

输出 \(m\) 行，输出每次训练时的行驶路径经过的最大车道数。

  • 样例输入

  • 样例输出

…

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