分类： 贪心

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 P4258 [FJWC2019]原样输出

YZOJ P4258 [FJWC2019]原样输出

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

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

  • 题目描述

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

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

它没法输出换行符了。

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

比如 orzxxxxx 可能会变成 rzxx、orz、x 或者空串。

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

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

  • 输入格式

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

接下来 \(n\) 行，表示输入文件的内容。保证这 \(n\) 行中每行的每个字符是 A、C、G、T 四种字符中的一种。

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

  • 输出格式

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

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

  • 样例输入

…

YZOJ P3385 [校内训练20171201]笔名分配问题

YZOJ P3385 [校内训练20171201]笔名分配问题

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

难度：\(5.5\)

  • 题目描述

班里有 \(n\) 个同学。老师为他们选了 \(n\) 个笔名。现在要把这些笔名分配给每一个同学， 每一个同学分配到一个笔名，每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为 \(a\)，真名为 \(b\)，则他们之间的相关度为 \(lcp(a,b)\)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。

对于两个字符串 \(a,b\)（从 \(1\) 开始标号），定义 \(a,b\) 的最长公共前缀 \(lcp(a,b)\) 为最大的非负整数 \(k\)，使得 \(k\le |a|, k\le |b|\)，且对所有 \(i=1,2,\ldots,k\)，\(a_i = b_i\) 。

给出一种分配笔名的方案，使得匹配质量最大。

  • 输入格式

第 \(1\) 行有 \(1\) 个整数 \(n\)，表示班级中同学的数目。接下来 \(n\) 行，表示每一个同学的真名。最后 \(n\) 行是老师已经安排好的笔名。每行的名称仅由小写字母组成。

  • 输出格式

将分配笔名的方案输出到文件中。第一行输出一个数，表示最大匹配质量。接下来 \(n\) 行，每行两个数 \(a,b\)，表示把编号为 \(b\) 的笔名分配给编号为 \(a\) 的同学。同学和笔名均按输入顺序从 \(1\) 至 \(n\) 编号。若方案不唯一，任意输出一种即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于所有测试点，\(n \leq 100000\)，输入串总长 \(\leq 800000\) 。

 

 

 …

[FJWC2019 Day3] 签到题

[FJWC2019 Day3] 签到题

时间限制： 1000ms               内存限制：256MB

难度： \(4.5\)

  • 题目描述

作为一道签到题，自然只能包含最基本的算法。本题的任务很简单，给定一个长度为 \(n\) 的序列 \(a\)，你要将其排序。

由于出题人很菜，不会排序算法，他决定自己编一个。他想找到一个数 \(x\)，使得序列中的所有数字都异或上 \(x\) 后序列恰好按从小到大排列。

顺带，这个序列会被进行若干次修改，每次修改后你需要回答当前是否存在一个 \(x\) 满足序列中数字异或上 \(x\) 后按从小到大排列，如果有，请你给出最小的 \(x\) 。

  • 输入格式

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

第二行 \(n\) 个非负整数，表示序列 \(a\) 。

第三行一个非负整数 \(q\) ，表示修改次数。

接下来 \(q\) 行，每行一个正整数 \(x\) 和一个非负整数 \(y\)，表示将序列中第 \(x\) 个元素修改为 \(y\) 。

  • 输出格式

输出 \(q+1\) 行，每行一个整数，第一行表示一开始最小的合法 \(x\) ，之后 \(q\) 行依次表示每次修改后最小的合法 \(x\)，如果不存在则这一行输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(20\%\) 的数据，\(n,m \le 500\)，所有数字不超过 \(2^9\) ​​。

对于 \(50\%\) 的数据，\(n,m \le 1000\) 。

对于 \(100\%\) 的数据，\(n,m \le {10}^6\)​​，所有数字不超过 \(2^{30}\) ​​。

 

 

YZOJ P4263…