[WC2017] 挑战

题目背景

## 滥用本题评测将被封号。洛谷不保证此类毒瘤题的评测结果准确性。 你和同学们找了三道题目用来练习。 这次练习的目标是写出能在时间限制里通过尽量大规模数据的代码。 同学们纷纷写出了优秀的代码。现在,他们向你发起了挑战,他们对每个问题都设置了若干个测试数据,这是他们能通过的最大规模的测试数据。现在,他们想看一看你写的代码究竟能超过多少同学的代码,通过多大规模的测试数据。 本题分为 $3$ 个任务,每个任务对应一道题和相应的若干个测试点,你需要对于每个任务,设计一个能通过尽量多测试点的程序。

题目描述

## 任务一 给定 $n$ 个 $32$ 位无符号整数,将它们从小到大排序。 ## 任务二 有 $2n$ 个人在玩 「石头剪刀布」 游戏。他们排成两排,每排 $n$ 个人。每个人在每一局游戏都使用固定策略,即对于第 $i (i \in 1, 2)$ 排的第 $j (0 \leq j < n)$ 个人,用一个整数 $a_{ij}$​​ 表示他的策略,其中 $0$ 表示只出石头,$1$ 表示只出剪刀,$2$ 表示只出布。 现在有 $q$ 个询问,每个询问给定三个整数 $x,y,l(0\leq x,y<n,1\leq l\leq n-max(x,y))$, 问将第一排的第 $x∼x+l-1$ 个人和第二排的第 $y∼y+l-1$ 个人比赛之后,第一排有多少个人会赢。 上文中 「比赛」 的意思是,对于所有整数 $i$ 满足 $0\leq i<l$,让第一排的第 $x+i$ 个人和 第二排的第 $y+i$ 个人进行 「石头剪刀布」 游戏。 ## 任务三 我们称一个合法的括号串为:只由左括号和右括号构成,两种括号的数量相等, 且任意一个前缀的左括号数量不少于右括号数量的串。现在给定一个由 ```(```,```)``` 和```?``` 构成的串,问有多少种不同的方案,使得将每个 ```?``` 都替换成一个括号之后,该串变成一 个合法的括号串。两种方案不同,当且仅当至少有一个位置的 ```?``` 被替换成了不同的括号。

输入输出格式

输入格式


此题提供了模板程序。选手可以在此基础上编写自己的程序,模板程序详见下文数据范围与提示。 第一行一个整数$ task\_id(1\leq task\_id\leq3)$,表示任务编号。接下来是每个具体任务的输入内容。 在输入的同一行中,相邻的两个整数会被一个空格隔开。 对于任务一:一行,两个整数 $n,s$。令 $a_0=next\_integer(s),a_i=next\_integer(a_{i-1}),1\leq i<n$,则 $a_0,a_1,…,a_{n-1}$ 即为需要排序的 $n$ 个整数。 对于任务二:第一行两个整数 $n,q$。第二行一个仅包含 $0, 1, 2$ 的长度为 $n$ 的字符串,第 $i$ 个字符所代表的整数表示第一排第 $i$ 个人的策略(即 $a_{1i}$​​)。第三行格式同第二行,表示第二排各个人的策略。 对于任务三:第一行一个整数 $n$,表示给定的串的长度。第二行一个字符串,即为给定的串。

输出格式


对于任务1:令 $b$ 为已经排好序的数组,调用 ```output_arr(b, n * 4)``` 即可。 对于任务2:将每个询问的答案依次存入 $32$ 位无符号整数数组 $b$ 中(即,存入 $b_0,b_1,⋯,b_{q-1}$ 中),然后调用 ```output_arr(b, q * 4)``` 即可。 对于任务3:输出一个整数,表示不同的方案数除以 $2^{32}$​​ 得到的余数。

输入输出样例

输入样例 #1

1
100000 2017012501

输出样例 #1

4275990336

输入样例 #2

2
6 6
200100
200211
5 1 3
2 0 1
2 0 3
2 0 2
2 3 4
0 1 3

输出样例 #2

3349208141

输入样例 #3

3
4
(???

输出样例 #3

2

输入样例 #4

3
4
)???

输出样例 #4

0

说明

## 数据范围与提示 | 任务编号 | 分值 | 测试点编号 | 数据范围与约定 | 时间限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | 5 | 1 | $n=100000$ | 3s | | 1 | 19 | 2 | $n=10^8$ | 4s | | 1 | 11 | 3 | $n=2\times10^8$ | 6s | | 2 | 7 | 4 | $n=q=1000$ | 3s | | 2 | 23 | 5 | $n=q=300000$ | 3s | | 3 | 9 | 6 | $n=1000$ | 3s | | 3 | 5 | 7 | $n=120000$ | 3s | | 3 | 7 | 8 | $n=225000$ | 3s | | 3 | 14 | 9 | $n=266666$ | 3s | ## 模板程序 ### C++模板 ``` #include <stdio.h> #include <string.h> #include <algorithm> typedef unsigned int u32; typedef unsigned long long u64; inline u32 next_integer(u32 x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } bool output_arr(void *a, u32 size) { if (size % 4) { return puts("-1"), 0; } u32 blocks = size / 4; u32 *A = (u32 *)a; u32 ret = size; u32 x = 23333333; for (u32 i = 0; i < blocks; i++) { ret = ret ^ (A[i] + x); x ^= x << 13; x ^= x >> 17; x ^= x << 5; } return printf("%u\n", ret), 1; } // ===== header ====== namespace Sorting { void init_data(u32 *a, int n, u32 seed) { for (int i = 0; i < n; i++) { seed = next_integer(seed); a[i] = seed; } } void main() { int n; u32 seed; scanf("%d%u", &n, &seed); u32 *a = new u32[n]; init_data(a, n, seed); // sort(a, n); output_arr(a, n * sizeof(u32)); } } namespace Game { void main() { int n, q; scanf("%d%d", &n, &q); char *s1 = new char[n + 1]; char *s2 = new char[n + 1]; scanf("%s%s", s1, s2); u32 *anss = new u32[q]; int *q_x = new int[q]; int *q_y = new int[q]; int *q_len = new int[q]; for (int i = 0; i < q; i++) { scanf("%d%d%d", q_x + i, q_y + i, q_len + i); } // solve(n, q, s1, s2, q_x, q_y, q_len, anss); output_arr(anss, q * sizeof(u32)); } } namespace Parentheses { void main() { int n; scanf("%d", &n); char *s = new char[n + 1]; scanf("%s", s); u32 ans; // ans = solve(n, s); printf("%u\n", ans); } } int main() { int task_id; scanf("%d", &task_id); switch (task_id) { case 1: Sorting::main(); break; case 2: Game::main(); break; case 3: Parentheses::main(); break; } return 0; } ``` ### C模板 ``` #include <stdio.h> #include <stdlib.h> #include <string.h> #define bool int #define true 1 #define false 0 typedef unsigned int u32; typedef unsigned long long u64; inline u32 next_integer(u32 x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } bool output_arr(void *a, u32 size) { if (size % 4) { return puts("-1"), 0; } u32 blocks = size / 4; u32 *A = (u32 *)a; u32 ret = size; u32 x = 23333333; u32 i; for (i = 0; i < blocks; i++) { ret = ret ^ (A[i] + x); x ^= x << 13; x ^= x >> 17; x ^= x << 5; } return printf("%u\n", ret), 1; } // ===== header ====== void Sorting_main() { int n; u32 seed; scanf("%d%u", &n, &seed); u32 *a = malloc(n * sizeof(u32)); int i; for (i = 0; i < n; i++) { seed = next_integer(seed); a[i] = seed; } // sort(a, n); output_arr(a, n * sizeof(u32)); } void Game_main() { int n, q; scanf("%d%d", &n, &q); char *s1 = malloc((n + 1) * sizeof(char)); char *s2 = malloc((n + 1) * sizeof(char)); scanf("%s%s", s1, s2); u32 *anss = malloc(q * sizeof(u32)); int *q_x = malloc(q * sizeof(int)); int *q_y = malloc(q * sizeof(int)); int *q_len = malloc(q * sizeof(int)); int i; for (i = 0; i < q; i++) { scanf("%d%d%d", q_x + i, q_y + i, q_len + i); } // solve(n, q, s1, s2, q_x, q_y, q_len, anss); output_arr(anss, q * sizeof(u32)); } void Parentheses_main() { int n; scanf("%d", &n); char *s = malloc((n + 1) * sizeof(char)); scanf("%s", s); u32 ans; // ans = solve(n, s); printf("%u\n", ans); } int main() { int task_id; scanf("%d", &task_id); switch (task_id) { case 1: Sorting_main(); break; case 2: Game_main(); break; case 3: Parentheses_main(); break; } return 0; } ``` ### Pascal模板 ``` type u32 = dword; u64 = qword; u32_p = ^u32; u64_p = ^u64; longint_p = ^longint; function next_integer(x : u32) : u32; inline; begin x := x xor (x << 13); x := x xor (x >> 17); x := x xor (x << 5); exit(x); end; function output_arr(a_in : pointer; size : u32) : boolean; var blocks : u32; a, a_ed : u32_p; ret, x : u32; begin if size mod 4 <> 0 then begin writeln(-1); exit(false); end; blocks := size div 4; ret := size; a := a_in; a_ed := a + blocks; x := 23333333; while a < a_ed do begin ret := ret xor (a[0] + x); x := x xor (x << 13); x := x xor (x >> 17); x := x xor (x << 5); inc(a); end; writeln(ret); exit(true); end; // ====== header ====== procedure init_data(a : u32_p; n : longint; seed : u32); var a_ed : u32_p; begin a_ed := a + n; while a < a_ed do begin seed := next_integer(seed); a[0] := seed; inc(a); end; end; procedure Sorting_main(); var n : longint; seed : u32; a : u32_p; i : u32; begin read(n, seed); a := Getmem(n * sizeof(u32)); init_data(a, n, seed); // sort(a, n); output_arr(a, n * sizeof(u32)); end; procedure Game_main(); var n, q : longint; s1, s2 : ansistring; anss : u32_p; q_x, q_y, q_len : longint_p; i : longint; begin readln(n, q); readln(s1); readln(s2); anss := Getmem(q * sizeof(u32)); q_x := Getmem(q * sizeof(longint)); q_y := Getmem(q * sizeof(longint)); q_len := Getmem(q * sizeof(longint)); for i := 0 to q - 1 do begin read(q_x[i], q_y[i], q_len[i]); end; // solve(n, q, s1, s2, q_x, q_y, q_len, anss); output_arr(anss, q * sizeof(u32)); end; procedure Parentheses_main(); var n : longint; s : ansistring; ans : u32; begin read(n); read(s); // ans := solve(n, s); writeln(ans); end; var task_id : longint; begin read(task_id); if task_id = 1 then begin Sorting_main(); end else if task_id = 2 then begin Game_main(); end else if task_id = 3 then begin Parentheses_main(); end; close(input); close(output); end. ```