【WC2017】挑战-任务3 排行榜


时间限制: 3 s
空间限制: 2097152 KB

问题描述

你和同学们找了三道题目用来练习。

这次练习的目标是写出能在时间限制里通过尽量大规模数据的代码。

同学们纷纷写出了优秀的代码。现在,他们向你发起了挑战,他们对每个问题都设置了若干个测试数据,这是他们能通过的最大规模的测试数据。现在,他们想看一看你写的代码究竟能超过多少同学的代码,通过多大规模的测试数据。

本题中仅有一个任务,对应一道题和相应的若干个测试点,你需要设计一个能通过尽量多测试点的程序。

任务

我们称一个合法的括号串为:只由左括号和右括号构成,两种括号的数量相等,且任意一个前缀的左括号数量不少于右括号数量的串。 现在给定一个由()?构成的串,问有多少种不同的方案,使得将每个?都替换成一个括号之后,该串变成一个合法的括号串。 两种方案不同,当且仅当至少有一个位置的?被替换成了不同的括号。

我们给出一些括号串的例子:()()()是合法的,(((())()))是合法的,((((是不合法的,())(是不合法的。

对于输入数据(???,答案为2,有(())()()两种方案。 对于输入数据)???,答案为0,因为不可能有合法的括号串以右括号开头。

接口

unsigned solve(int n, char *s);

其中 n 表示字符串长度,s 为给定的字符串。该函数的返回值是一个整数,表示不同的方案数,模 $2 ^ {32}$。

数据范围

本题共四个测试点:

提示和说明

本题在32位计算机上运行。

对于所有语言都打开 -O2 编译开关。


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2020-11-29 01:08:27 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用