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 P3098 [JLOI2016]成绩比较

YZOJ P3098 [JLOI2016]成绩比较

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

难度:\(6.0\)

  • 题目描述

G系共有 \(n\) 位同学,\(m\) 门必修课。这 \(n\) 位同学的编号为 \(0\) 到 \(n-1\) 的整数,其中B神的编号为 \(0\) 号。

这 \(m\) 门必修课编号为 \(0\) 到 \(m-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。如果在门课上 A 获得的成绩均小于等于 B 获得的成绩,则称 A 被 B 碾压。

在B神的说法中,G系共有 \(k\) 位同学被他碾压(不包括他自己),而其他 \(n-k-1\) 位同学则没有被他碾压。D神查到了B神每门必修课的排名。这里的排名是指:如果B神某门课的排名为 \(R\),则表示有且仅有 \(R-1\) 位同学这门课的分数大于B神的分数,有且仅有 \(n-R\) 位同学这门课的分数小于等于B神(不包括他自己)。

我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足B神的说法,也能符合D神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

你不需要像D神那么厉害,你只需要计算出情况数模 \(10^9+7\) 的余数就可以了。

  • 输入格式

第一行包含三个正整数 \(n, m, k\),分别表示G系的同学数量(包括B神),必修课的数量和被B神碾压的同学数量。

第二行包含 \(m\) 个正整数,依次表示每门课的最高分 \(U_i\) 。

第三行包含 \(m\) 个正整数,依次表示B神在每门课上的排名 \(R_i\) 。保证 \(1 \leq R_i \leq n\)。

数据保证至少有 \(1\) 种情况使得B神说的话成立。\(n \leq 100, m \leq 100, U_i \leq 10^9\) 。

  • 输出格式

输出仅包括一行一个整数,表示成绩情况数对 \(10^9+7\) 取模的结果。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据,\(n, m \leq 20\),\(U_i \leq 100\);

对于 \(100\%\) 的数据,\(n,m \leq 100\),\(U_i \leq 10^9\),\(1 \leq R_i \leq n\),\(0 \leq k < n\) …

YZOJ P3033 背包

YZOJ P3033 背包

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

出题人:chj2001             难度:\(5.4\)

  • 题目描述

存在 \(n\) 种物品,其中第 \(i\) 种物品的价值为 \(a_i\) ,最多可以用 \(b_i\) 件,求从这些物品中选取若干件(不能为 \(0\) 件),得到的总价值为 \(9\) 的倍数的方案。

需要分别计算每种物品中,每件之间有区别的方案数和没有区别的方案数。

(即每种物品按照 \(1,2,3, \cdots ,b_i\) 编号的方案数和不编号的方案数。)

  • 输入格式

第一行输入一个数 \(n\) 。

接下来 \(n\) 行,每行两个数 \(a_i, b_i\) 。

  • 输出格式

输出共两行,每行各包括一个数,分别表示对于每种物品视为不同的时的方案数和视为相同的时的方案数。有的时候方案数可能很大,你需要将它对 \(10^9+7\) 取模。

方案数均不考虑顺序,如 \(2, 3, 4\) 和 \(4, 3, 2\) 是同一种方案。

如果无法做到则输出 \(0\) 。

  • 样例输入

  • 样例输出

  • 样例说明

不考虑同种物品之间的区别,一共有 \(2\) 种不同的方案凑出 \(9\) 的倍数,即 \(3, 2, 2, 2\) 和 \(3, 3, 3\) 。

考虑同种和果子的区别时,一共有 \(C_3^1 \times C_3^3 = 3\) 种不同的方案凑出 \(3, 2, 2, 2\),\(C_3^3=1\) 种方案凑出 \(3, 3, 3\),因此总共有 \(4\) 种方案。

  • 数据规模与约定

对于 \(40\%\) 的数据,\(n \le 1000 , a_i \le 100 , b_i \le 100\) 。

对于 \(100\%\) 的数据,\(1 \le n \le 10^5 , 1 \le a_i \le 90000 , 1 \le b_i \le …

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 P2049 [FJOI2013]相似基因序列问题

YZOJ P2049 [FJOI2013]相似基因序列问题

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

难度:\(6.0\)

  • 题目描述

给定 \(2\) 个长度分别为 \(m\) 和 \(n\) 的 DNA 序列 \(X\) 和 \(Y\),以及一个长度为 \(p\) 的模式子序列 \(P\)。带有子序列包含约束的最长公共子序列问题就是要找出 \(X\) 和 \(Y\) 带有包含子序列 \(P\) 约束的最长公共子序列的长度。

例如,如果给定的 DNA 序列 \(X\) 和 \(Y\) 分别为 X=AATGCCTAGGCY=CGATCTGGAC,模式子序列 P=GTAC,则子序列 ATCTGGC 是 \(X\) 和 \(Y\) 的一个无约束的最长公共子序列,而包含 \(P\) 为其子序列的最长公共子序列是 GCTAC

  • 输入格式

第一行中给出正整数 \(m,n,p\),分别表示给定序列 \(X\) 和 \(Y\) 以及模式子序列 \(P\) 的长度。\(m,n,p<300\) 。

接下来的 \(3\) 行分别给出序列 \(X\) 和 \(Y\) 以及模式子序列 \(P\) 。

  • 输出格式

将计算出的 \(X\) 和 \(Y\) 带有包含子序列 \(P\) 约束的最长公共子序列的长度输出。如果 \(X\) 和 \(Y\) 不存在包含子序列 \(P\) 的公共子序列,则输出 \(-1\)。

  • 样例输入

  • 样例输出

 

 

 …

YZOJ P2443 回文子序列

YZOJ P2443 回文子序列

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

难度:\(5.0\)

  • 题目描述

求一个字符串的回文子序列个数。

如果 \(p_1p_2 \cdots p_m\) 满足 \(1 \leq p_1<p_2<\cdots<p_m \leq n\),则称 \(a_{p_1}a_{p_2}\cdots a_{p_m}\) 是序列 \(a_1a_2\cdots a_n\) 的一个子序列。

如果对于所有 \(1 \leq i \leq n\) 都满足 \(a_i=a_n-i+1\),则 \(a\) 是一个回文串。空串也是回文串。

  • 输入格式

一个字符串

  • 输出格式

回文子序列个数 \(\mod 10^9+7\)

  • 样例输入

  • 样例输出

  • 样例说明

样例中所有回文子序列按照字典序如下:

“”(空串)、”a”、”aa”、”aka”、”f”、”ff”、”k”、”kak”、”kk”、”t”

  • 数据规模与约定

对于 \(100\%\) 的数据,\(n \leq 5000\) 。

字符串中仅包含小写字母。

 

 

 …

YZOJ P3847 [2018省队集训]Ernd

YZOJ P3847 [2018省队集训]Ernd

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

难度:\(8.0\)

  • 题目描述

给定一个长度为 \(n\) 且仅包含小写英文字母的字符串 \(S\)。你有一个字符串 \(T\),初始为空串。

你可以进行 \(n\) 次操作,每次操作你可以在 \(T\) 的前端或末尾加入一个任意字母。记第 \(i\) 次操作后 \(T\) 在 \(S\) 中的出现次数为 \(f_i\),你需要最大化 \(ans=\sum\limits_i f_i\) 。

  • 输入格式

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

第二行一个长度为 \(n\) 的字符串 \(S\) 。

  • 输出格式

一行一个整数,表示 \(ans\) 的最大值。

  • 样例输入

  • 样例输出

  • 数据规模与约定

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

 

 

 …

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

浅谈斜率优化——截距优化

浅谈斜率优化——截距优化

最近(两个月前)学习了斜率优化 —— 一种优化 1D1D 动态规划转移方程的高效方法,在较高难度的比赛中是一种十分常见的 DP 优化手段。鉴于我之前(一年前)也稍微接触过一点相关方面的知识,但是完全没有搞懂(太菜了),最近(两个月前)再配合 orzCJK学长 提出的截距优化的思想理念才对于斜率优化问题有了深刻的见解,故在这里对 orzCJK学长 的 斜率优化_截距优化!.pdf 进行详细的解释说明。

 

首先,1D1D 指的是状态数 \(O(n)\) 转移 \(O(n)\) 的动态规划方程。在满足一些条件的情况下,斜率优化可以将转移的 \(O(n)\) 优化至 \(O(logn)\) 甚至可以到 \(O(1)\) 。这样时间复杂度就由 \(O(n^2)\) 变为 \(O(nlogn)\) 甚至是 \(O(n)\) ,可见斜率优化的高效性。

如果有一个 DP 方程的某个状态为 \(f_i\) ,如果能推导出类似于 \(f_i=c_i + \min\limits_{j<i \land \cdots}{\{a_j + w_i \cdot b_j\}}\) ,那么这个转移方程就可以使用斜率优化进行优化。

然而普通的转移方程并没有什么特殊的地方,使用经典的方法(我也不会)略显繁琐,所以现在我们要赋予它以几何意义。(时刻注意,这个转移方程的意义是对于一个 \(i\) 在 \(j < i\) 范围内寻找 \(j\) 使 \(a_j + w_i \cdot b_j\))最小。)

换一下变量名,设 \(y_j=a_j, k_i=-w_i, x_j=b_j\) ,那么这样需要最小化的式子就变为 \(\underbrace{a_j}_{y_j} – \underbrace{-w_i}_{k_i} \cdot \underbrace{b_j}_{x_j}\) 。这不就是截距 \(b = y – kx\) 吗?!!也就是说,要最小化的就是一条过 \(\left(x_j, y_j\right)\)斜率为 \(k_i\) 的直线的截距

换句话说,把所有对于当前 \(i\) 可转移的 \(j\) 都表示为二维平面上的一个点 \(p_j=\left(x_j, y_j\right)\) ,我们需要做的就是在所有这样的点中,找到一个点,使经过它且斜率为 \(k_i\) 的直线的截距最小!这也是为什么斜率优化就是截距优化的原因,它其实优化的是截距!

现在想象一条斜率固定的直线从下往上平移,当它第一次经过某个点 \(p_j\) 时,这时的截距肯定取到最小值。那么这个点 \(p_j\) 在什么地方呢?显然,它会在所有 \(p\) 组成的下凸壳上。

那么现在只要维护这个下凸壳,每次在上面找点使得截距最小,拿来更新 …

[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…