[CF868-F] Yet Another Minimization Problem

[CF868-F] Yet Another Minimization Problem

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

难度:\(6.0\)

  • 题目描述

有 \(n\) 个正整数构成序列 \(a\) ,定义一个区间 \([l, r]\) 的代价为 满足 \(l \leq i, j \leq r\) 并使得 \(a_i=a_j\) 的无序对 \([i, j]\) 的数量。

现要把 \(a\) 分成 \(k\) 个互不相交且不为空的连续的区间,求出在所有分法中,分出区间的最小代价和是多少。

  • 输入格式

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

第二行,序列 \(a\) ,共 \(n\) 个元素,用一个空格隔开。

  • 输出格式

一个整数,表示在所有分法中,分出区间的最小代价和。

  • 样例输入

  • 样例输出

  • 样例说明

一种可能的分法为 \([1], [1, 3], [3, 3, 2, 1]\) 。

第一个区间的代价为 \(0\) ,第二个区间的代价为 \(0\) ,第三个区间的代价为 \(1\) ,最小代价和为 \(1\) 。

(其他样例见原题

  • 数据范围

对于 \(10\%\) 的数据,\(2 \leq n \leq 20\) 。

对于 \(40\%\) 的数据,\(2 \leq n \leq 1000\) 。

对于 \(100\%\) 的数据,\(2 \leq n \leq 10^5\) ,\(2 \leq k \leq min\{20,n\}\) 。

保证 \(1 \leq a_i \leq n\) 。

 

 

 

\(Source\): CF868-F

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

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

难度:\(5.2\)

  • 题目描述

给定一个长度为 \(n\) 的非负整数序列 \(a\) 和一个正整数 \(m\) 。

现在有 \(q\) 组询问,每组询问给定两个正整数 \(l, r\) ,每次可以选择满足 \(l \leq i \leq r\) 的若干个 \(a_i\) (也可以一个都不选),使得这些 \(a_i\) 的和是 \(m\) 的非负整数倍,并输出满足条件的选择方案数对 \(10^9+7\) 取模后的余数。

  • 输入格式

第一行为两个正整数 \(n\) 和 \(m\) 。

第二行为序列 \(a\) ,共 \(n\) 个元素,用一个空格隔开。

第三行为询问数 \(q\) 。

接下来的 \(q\) 行,每一行都有两个正整数,分别为 \(l\) 和 \(r\) 。

  • 输出格式

共 \(q\) 行。

第 \(i\) 行为第 \(i\) 组询问的答案。

  • 样例输入

  • 样例输出

  • 样例说明

对于第一组询问 \(l=1, r=2\) ,有 不选、选择 \(5, 1\) ,共 \(2\) 种情况。

对于第二组询问 \(l=1, r=3\) ,有 不选、选择 \(5, 1\) 、选择 \(5, …

YZOJ P2202 Legend VII – Ornament

YZOJ P2202 Legend VII – Ornament

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

难度:\(5.0\)

  • 题目描述

  • 输入格式

第一行有两个整数 \(N\) 和 \(Q\),表示商店有 \(N\) 个装饰品,一共有 \(Q\) 个询问。

第二行有 \(N\) 对整数,每 \(i\) 对整数 \(p_i, b_i\) 表示第 \(i\) 个装饰品的价格和好看度。

接下来 \(Q\) 行,每行两个整数 \(a, c\),分别描述 \(Q\) 个询问。

  • 输出格式

对于每个询问输出一行,一个整数表示最大好看度。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据,\(N \leq 100, Q \leq 1000\) 。

对于 \(100\%\) 的数据,\(N \leq 1000, Q \leq 100000, 1 \leq a \leq N, c \leq 1000\) 。

 

 

 …

YZOJ P2384 Naive – DP II

YZOJ P2384 Naive – DP II

时间限制:2000MS 内存限制:768KB

难度:\(5.0\) 出题人:lightning

  • 题目描述

请注意不寻常空间限制

由于空间的限制,无法直接给出每个位置的金币数量,所以需要用一种新的方法来得到金币的数量——定义长度为 \(P\) 的数组 \(P\) 和长度为 \(T\) 的数组 \(T\),棋盘 \((i,j)\) 上的金币数量为 \((P_i+T_j) \bmod Mod\) 。

  • 输入格式

第一行输入三个整数,\(P\)、\(T\)、\(Mod\) 。

第二行输入 \(P\) 个整数,表示数组 \(P\) 。

第三行输入 \(T\) 个整数,表示数组 \(T\) 。

  • 输出格式

输出包括两行——

第一行输出一个整数表示获得的最多的金币数。

第二行输出方案,方案用一个只包含 \(P\) 和 \(T\) 的字符串表示,\(P\) 表示向下、\(T\) 表示向右。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据,\(P, T \leq 100\) 。

对于 \(100\%\) 的数据,\(P, T \leq 5000,Mod \leq 100000\) 。

 

 

 …

YZOJ P3782 [校内训练20180619]组合数问题

YZOJ P3782 [校内训练20180619]组合数问题

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

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

  • 题目描述

  • 输入格式

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

接下来 \(n\) 行,第 \(i\) 行两个正整数 \(a_i, b_i\),表示一个数对 \((a_i, b_i)\) 。

  • 输出格式

一行一个整数,表示所求式子的值。

  • 样例输入

  • 样例输出

  • 样例说明

  • 数据规模与约定

保证 \(2 \leq n \leq 200,000\) , \(1 \leq b_i \leq a_i \leq 2000\) 。

 

 

 …

YZOJ P1800 质数生成器

[NOIP2015四校联训Day8]质数生成器

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

  • 题目描述

生成给定范围内的所有质数。

  • 输入格式

有多组数据。

输入数据第一行是一个整数\(T(T\leq10)\),表示测试数据的组数。

接下来\(T\)行,每行有两整数\(m, n\),表示要求生成质数的范围是\([m, n] (1 \leq m \leq n \leq 10^9, n-m \leq 10^6)\)

  • 输出格式

对于每一组测试数据,输出所有在\([m, n]\)中的质数\(p\),一行一个。

不同测试数据之间用一个空行分隔。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于\(30\%\)的数据,\(m < n \leq 10^3\);

对于\(50\%\)的数据,\(m < n \leq 10^6 且 n-m \leq 10^3\);

对于\(100\%\)的数据,\(m < n \leq 10^9 且 n-m \leq 10^6\);…

BZOJ 1041 (YZOJ 3460) 圆规问题

圆规问题

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

  • 问题描述

小 C 有一个圆规,他经常用圆规在纸上作图。

有一天,小 C 准备在一个单位网格纸上作一个圆。他以某个格点为圆心,作了一个半径为 \(R\) 的圆。接着,他将圆经过的所有格子涂成黑色。注意:只有圆经过了一个格子的内部才能涂黑,只经过格子的边界不涂黑。小 C 的问题是:对于给定的半径为 \(R\) 的圆,共有多少个格子被涂黑?

这是一个 \(R=10\)的实例:

左图为小 C 作的圆,右图是将圆经过的格子涂黑后的图。可以看出,\(R=10\)时,共有 68 个格子被涂黑。

给定\(N\),计算被涂黑的格子数目。

  • 输入格式

输入文件包含一个整数\(R\),\(1 \leq R \leq 2,000,000,000\)

  • 输出格式

将被涂黑的格子数目输出到文件中。

  • 样例输入

  • 样例输出


YZOJ T1860-P2 Find

Find

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

  • 题目描述

我们定义两种操作

操作1的格式 :I 字符串 \(S\),加入 1 个字符串 \(S\)。

操作2的格式 :F 字符串\(S\),查找字符串\(S\)是否在当前寻找前已经出现过

注释:同一个字符串可能多次被插入和查找,字符串长度\(\left|S\right|≤20\),字符集为小写英文字母。

  • 输入格式

第一行,指令个数\(N\)。

接下来\(N\)行,每行一个指令。

  • 输出格式

对于每次查找,找到输出 ‘YES’,没找到输出 ‘NO’ 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(40\%\) 的数据 \(N≤5000\)

对于 \(100\%\) 的数据 \(N≤150000\)

 


YZOJ T1860-P1 Trie树

Trie树

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

  • 题目描述

给定N个01串,对于每一个01串,你需要判断:

1.如果它之前出现过,则输出之前最后出现的位置,否则

2.如果它是之前出现的某一01串的前缀,则输出0,否则

3.输出-1

  • 输入格式

第一行一个数N

接下来N行每行一个01串

  • 输出格式

共N行,每行一个数,见题目描述

  • 样例输入

  • 样例输出

  • 数据规模与约定

0<=N<=10000,01串长度不超过100,文件大小不超过1M,并保证数据的梯度

 …