YZOJ P4258 [FJWC2019]原样输出

YZOJ P4258 [FJWC2019]原样输出

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

出题人:E.Space        难度:\(7.0\)

  • 题目描述

它会把输入按行读入,原封不动地复制到输出中去。

但是在一次更新以后,它的程序出了一些问题。

它没法输出换行符了。

并且,读入的时候,总会莫名其妙地随机漏掉开头和结尾的若干个字符,甚至整行都会漏掉。

比如 orzxxxxx 可能会变成 rzxxorzx 或者空串。

现在你找到一份输入文件丢给它,你想知道它的输出可能有多少种情况,以及每种情况分别是什么。

由于你找到的输入文件全部来自之前的福建省选,所以所有的输入文件每行只可能包含 ACGT 四种字符。

  • 输入格式

第一行一个正整数 \(n\),表示(题面中)输入文件的行数。

接下来 \(n\) 行,表示输入文件的内容。保证这 \(n\) 行中每行的每个字符是 ACGT 四种字符中的一种。

接下来一个整数 \(k, (0 \leq k \leq 1)\),具体含义详见输出格式。

  • 输出格式

若 \(k=0\),你需要输出一行,表示输出的可能情况个数模 \(10^9+7\) 的结果。

若 \(k=1\),你需要按照字典序从小到大输出所有可能的输出情况,一行一个字符串,最后一行输出输出的可能情况个数模 \(10^9+7\) 的结果。

  • 样例输入


YZOJ P3754 Gab数列

YZOJ P3754 Gab数列

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

难度: \(4.5\)

  • 题目描述

给定数列 \(a_1,a_2,\cdots,a_n\),定义数列 \(b_1,b_2,\cdots,b_m\) 为 Gab数列 当且仅当它满足:

1,\(\forall 1\le i\le m\) 满足 \(b_i\in\mathbf{N^*}\) 且 \(1\le b_i\le n\)

2,\(\sum_\limits{i=1}^{m}b_i\le k\)

求 \(\sum_\limits{i=1}^{m}a_{b_i}\) 的最大值。

  • 输入格式

第一行三个整数 \(n\),\(m\) 和 \(k\) 。

第二行 \(n\) 个整数 \(a_i\) 。

  • 输出格式

输出仅一行,为最大值。

  • 样例输入

  • 样例输出

  • 样例说明

对应的 Gab数列 可以为 \(\{1,5,5,1,1,1\}\) 。

  • 数据范围

对于 \(15\%\) 的数据,\(n,m\le 8\),\(k\le 50\);

对于 \(40\%\) 的数据,\(n,m,k\le 200\);

对于另外 \(5\%\) 的数据,满足 \(m=k\);

对于另外 \(5\%\) 的数据,对于 \(1\le i\le j\le n\),\(a_i\ge a_j\);

对于 \(100\%\) 的数据,\(n\le 3000\),\(k\le 8000\),\(m\le 1000\),\(1\le a_i\le 10^9\),\(m\le k\)。

 

 

 …