Processing math: 0%

分类： 树形

YZOJ P3706 [APIO2018]新家

YZOJ P3706 [APIO2018]新家

时间限制：5000MS      内存限制：1048576KB

难度：7.0

  • 题目描述

五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。

小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 n 个商店出现。第 i 个商店可 以使用四个整数 x_i , t_i , a_i , b_i 描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 q 个询问，每个询问用二元组 （坐标，时间）表示。第 i 对二元组用两个整数 l_i , y_i 描述，分别表示选择的地点 l_i 和年份 y_i 。

现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离 居住点最远的商店类型到居住点的距离。类型 t 的商店到居住点的距离定义为：在指定的年份，类型 t 的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 i 的商店在第 y 年在营业当且仅当 a_i \leq y \leq b_i 。注意，在某些年份中，可能在五福街上并非所有 k 种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 -1。

你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。

  • 输入格式

第一行包含三个整数 n,k 和 q ，分别表示商店的数量、商店类型的数量和（坐标，时间）二元组的数量（1 \le n, q \le 3 \times 10^5 , 1 \le k \le n）

接下来 n 行，每行包含四个整数 x_i , t_i , a_i 和 b_i 用于描述一家商店，意义如题面所述 （1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i）。

接下来 q 行，每行包含两个整数 l_i 和 y_i ，表示一组（坐标，时间）查询 （1 \le l_i , y_i \leq 10^8 ）。

  • 输出格式

输出一行，包含 q 个整数，依次表示对于 q 组（坐标，时间）询问求出的结果。…

YZOJ P1310 [省队训练][NOI模拟7]车的放置

YZOJ P1310 [省队训练][NOI模拟7]车的放置

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

难度：8.0

  • 题目描述

有 N 个 1 \times h[i] 的矩形小棋盘，底边边长为 1，在一条直线上拼成了一个畸形的棋盘。

高度 h[i] 给出，第 i 个矩形的高为 h[i]，例如 h = [3, 2, 4, 2] 的图形如下：

若两个车相互攻击仅当它们在同一列，或在同一行且在这一行它们之间棋盘格子都是存在的，例如上图中 a 与 b 是相互不攻击的，c 与 d，b 与 c 均为相互攻击的。

现在要在这棋盘上放置恰好 K 个相互不攻击的车，问有多少种方案。

  • 输入格式

输入第 1 行包括两个正整数 N，K，表示了棋盘的列数和放的车数。

第 2 行包含 N 个正整数，表示了棋盘每列的高度。

  • 输出格式

输出包括一个非负整数，表示有多少种放置的方案，输出答案 \mod 1000000007 后的结果即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 100\% 的数据，有 N \leq 500，K \leq 500，h[i]  \leq 1000000 。

 

 

 …

YZOJ P2358 [ZJOI 2012]Naive – Matrix

YZOJ P2358 [ZJOI 2012]Naive – Matrix

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

难度：7.0

  • 题目描述

给出一个 R \times C 的矩阵，上面有 N 个 0，其他的都是 1，现在给出这些 0 的位置，要求求出有多少个子矩阵包含至少一个 0 。

  • 输入格式

第一行输入三个整数 R、C、N 。

接下来 N 行，每行两个整数 x、y，表示 0 的坐标。

  • 输出格式

输出一个数表示子矩阵的个数。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 100\% 的数据，R, C \leq 40000，N \leq \min\{R \times C,100000\}，所有 0 的位置两两不同且随机生成。

 

 

 

Source: BZOJ 2658…

[校内训练20161216] T2 版本管理git

[校内训练20161216] T2 版本管理git

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

难度：7.0

  • 题目描述

在工程的开发中，我们常常用 Git 进行版本的管理。这个方式具体来说是这样的：刚开始只有一个版本 0，表示最初始的情况，也就是空的项目；接下来一个用户可以对某一个版本 p 的项目进行修改，得到一个新的版本 i。这样，一个工程就产生了许多不同的版本，而管理员可以选择一些优秀的，将其合并到主版本中。

F 公司有一个项目 U，这个项目由一个字符串构成。版本 0 为空串。有 n 个开发者按顺序对这个项目进行了修改，其中第 i 个开发者将第 p_i ( 0 \le p_i < i) 个版本的开头添加上一个字符 c_i (1 \le c_i \le m) 作为新的版本 i。

作为项目的总负责人，你希望对这些版本进行评价。对一个字符串 S，称串 S 是串 T 的超前缀，当且仅当串 S 是串 T^{*} 的前缀。 T^{*} 表示 T 重复无限次得到的一个无限长度的串，如若 T = abcd，则 T^{*} = abcdabcdabcd \cdots。我们称串 S 的 “kitty 长度” 为 l，当且仅当存在一个长度为 l 的串 T 使得 S 是 T 的超前缀，且不存在小于 l 的串 T’ 使得 S 是 T’ 的超前缀（定义空串的 kitty 长度为 0）。你需要做的就是对每一个版本求出其的 kitty 长度（设版本 i 的 kitty 长度为 kitty(i)）。

在实际运营中，有两种情况，我们用一个数 k \in \{0,1\} 表示。在 k = 0 的情况中， 你可以等候开发者进行所有修改后，再进行计算；但在 k = 1 的情况中，开发者希望能够实时得到自己修改得到的版本的 kitty 长度，你需要实时计算出每个版本的 kitty 长度。

  • 输入格式

第一行包含三个整数 n,m,k。

接下来 n 行，其中第 i 行包含两个整数 p^{′}_{i}; c^{′}_{i}，其中：

如果 k = 0 ，则 p_i = p^{′}_{i}，c_i = c^{′}_{i}；

如果 k = 1，则 \(p_i = p^{′}_{i} \oplus kitty(i …

YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙

YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙

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

难度：6.0

  • 题目描述

已知密匙与一个长度为 n 的字符串有关，字符串中的字符都来自于字符集 \{\text{‘a’..}\text{‘z’}, \text{‘?’}\}，每个 \text{‘?’} 的位置都要被填上一个小写字母，我们定义一个填好的串是合法的当且仅当它满足如下条件：

在输入的 m 次操作后与这个串操作之前的样子相比没有改变。

一次操作是翻转这个串的第 l_i 个字符到第 r_i 个字符。

求出字典序第 K 小的合法的能被填出的串，因为密码就是它。

  • 输入格式

第一行三个数 n,m,k 。

第二行一个长度为 n 的串。

接下来 m 行每行两个数 l_i 和 r_i 。

  • 输出格式

一个串，表示字典序第 K 小的合法的能被填出的串。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 100\% 的数据，保证 n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18} 。

 

 

 …

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 局游戏的交换结束后，魔术球所在的魔术帽编号。…

[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

 

 

 …