YZOJ P2905 [PA2014]Druzyny

YZOJ P2905 [PA2014]Druzyny

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

难度:\(8.0\)

  • 题目描述

在之前的某次校内训练中,zzx 出了一道神奇的题目:给出 \(n\) 个人,要求将所有人分成若干个组,第 \(i\) 个人所在的组的人数必须在 \([l_i, r_i]\) 之间,判断是否存在可行解。

OI组的神犇们决定把这题改造一下:

dick32165401:改成只有编号连续的的一段才可以分一组。

runzhe2000:判定可行解可能会被爆搜水过,最大化分的组数就不那么容易水过了。

E.Space:不仅要最大化组数,还要求出最大化组数的方案数。

ct:数据范围就出100万好了。

于是这题就被这么造好了。

  • 输入格式

第一行 \(n\),\(1 \leq n \leq 1000000\) 。

接下来 \(n\) 行,每行 \(l_i,r_i\),\(1 \leq l_i \leq r_i \leq 1000000\) 。

  • 输出格式

若不存在合法的方案,仅输出一行 \(-1\) 。

否则输出一行两个整数,分别表示组数的最大值和组数取最大值的方案数模 \(10^9+7\) 。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 3711

膜拜上方所有dalao %%%%%%%%%%%%%%%%%%

像我这种菜鸡看到这种神仙题只会爆零QAQ…

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 P3384 [校内训练20171201]括号替换问题

YZOJ P3384 [校内训练20171201]括号替换问题

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

难度:\(5.0\)

  • 问题描述

这里有一个关于合法的括号序列的问题。如果插入“+” 和 “1” 到一个括号序列,我们能得到一个正确的数学表达式,我们就认为这个括号序列是合法的。例如,序列 “(())()”, “()” 和 “(()(()))” 是合法的,但是 “)(“, “(()” 和 “(()))(” 是不合法的。我们有一个仅由 “(”,“)” 和 “?” 组成的括号序列,你必须将 “?” 替换成括号,从而得到一个合法的括号序列。

对于给定仅由 “(”,“)” 和 “?” 组成的括号序列,你需要将 “?” 替换成括号,得到一个合法的括号序列,同时需要使得代价之和最小。

  • 数据输入

文件有多个测试实例(\(\leq 5\))。每个实例的第一行有 \(1\) 个正整数 \(n\),(\(1 \leq n \leq 100000\)),表示括号序列的长度为 \(n\)。第二行是一个长度为 \(n\) 的字符串,表示输入的括号序列,字符串仅由 “(”,“)” 和 “?” 组成。接下来 \(m\) 行,\(m\) 是字符串中 “?” 的个数,每一行包含两个整数 \(a_i\) 和 \(b_i\)(\(1 \leq a_i,b_i \leq 1000000\)),\(a_i\) 是将第 \(i\) 个 “?” 替换成左括号的代价,\(b_i\) 是将第 \(i\) 个 “?” 替换成右括号的代价。文件的最后一行有一个 \(0\) 表示结束。

  • 结果输出

将计算出的每个测试实例的答案依次输出到文件中。每个测试实例第一行输出一个整数,表示最小代价和。如果不存在合法方案,输出 \(-1\)。如果存在合法方案,第二行输出替换后的括号序列。若有多种替换方案的代价之和最小,可以输出任意一种。…

YZOJ P3897 Sevenk Love Oimaster

YZOJ P3897 Sevenk Love Oimaster

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

难度:\(7.5\)

  • 题目描述

有 \(n\) 个大串和 \(q\) 个询问,每次给出一个字符串 \(s\) 询问在多少个大串中出现过。

  • 输入格式

输入的第一行有两个整数分别代表 \(n\) 和 \(q\) 。

接下来的 \(n\) 行,分别给出题中所述的 n个只包含小写字母的字符串。

再接下来的 \(q\) 行,每行给出一个询问只包含小写字母的字符串。

  • 输出格式

对于每一个询问,输出一行答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(n \leq 10000, q \leq 60000\) 。

原串总长度 \(\leq 100000\) 。

询问串总长度 \(\leq 360000\) 。

 

 

 

Source: BZOJ 2780 && SPOJ 8093…

YZOJ P3750 [校内训练20180529]字符串的频度

YZOJ P3750 [校内训练20180529]字符串的频度

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

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

  • 题目描述

给定字符串 \(s\) 。你需要回答 \(n\) 个询问,第 \(i\) 个询问给出一个正整数 \(k_i\) 和一个字符串 \(m_i\),请求出 \(s\) 的所有子串 \(t\) 中,满足 \(m_i\) 在 \(t\) 中出现至少 \(k_i\) 次的字符串 \(t\) 的长度的最小值。

一个字符串的子串是该字符串中的连续一段字符。

保证任意两个询问的 \(m_i\) 不相同。

  • 输入格式

第一行包含一个字符串 \(s\)(\(1 \leq \left|s\right| \leq 10^5\))。

第二行包含一个正整数 \(n\)(\(1 \leq n \leq 10^5\))。

接下来 \(n\) 行,每行一个正整数 \(k_i\)(\(1 \leq k_i \leq \left|s\right|\))和一个非空字符串 \(m_i\),表示第 \(i\) 个询问。

所有字符串仅包含小写英文字母,且所有询问字符串的总长度不超过 \(10^5\) 。

  • 输出格式

对于每个字符串输出一行表示答案。

如果 \(m_i\) 在 \(s\) 中出现次数小于 \(k_i\),输出 \(-1\) 。…

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…

YZOJ P3933 [Baltic2004]sequence

YZOJ P3933 [Baltic2004]sequence

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

难度:\(6.0\)

  • 题目描述

给定一个序列 \(t_1,t_2,\cdots,t_n\),求一个递增序列 \(z_1<z_2<\cdots<z_n\),使得 \(R=\sum\limits_{i=1}^{n}{\left|t_i-z_i\right|}\) 的值最小。

本题中,我们只需要求出这个最小的 \(R\) 值。

  • 输入格式

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

第二行到第 \(n+1\) 行,每行一个整数,第 \(k+1\) 行为 \(t_k\)

  • 输出格式

一个整数 \(R\)

  • 样例输入

  • 样例输出

  • 样例说明

所求的 \(z\) 序列为 \(6,7,8,13,14,15,18\),\(R=13\)

  • 数据规模与约定

对于 \(100\%\) 的数据,\(1 \leq n \leq 10^6\),\(1 \leq t_i \leq 2\times 10^9\) 。

 

 

Source: BZOJ 1367…

[校内训练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}\) 。

 

 

 …