分类： 树形

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\)

 

 

 …