#P4604. [WC2017] 挑战

[WC2017] 挑战

题目背景

滥用本题评测将被封号。洛谷不保证此类毒瘤题的评测结果准确性。

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

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

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

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

题目描述

任务一

给定 nn3232 位无符号整数,将它们从小到大排序。

任务二

2n2n 个人在玩 「石头剪刀布」 游戏。他们排成两排,每排 nn 个人。每个人在每一局游戏都使用固定策略,即对于第 i(i1,2)i (i \in 1, 2) 排的第 j(0j<n)j (0 \leq j < n) 个人,用一个整数 aija_{ij}​​ 表示他的策略,其中 00 表示只出石头,11 表示只出剪刀,22 表示只出布。

现在有 qq 个询问,每个询问给定三个整数 x,y,l(0x,y<n,1lnmax(x,y))x,y,l(0\leq x,y<n,1\leq l\leq n-max(x,y)), 问将第一排的第 xx+l1x∼x+l-1 个人和第二排的第 yy+l1y∼y+l-1 个人比赛之后,第一排有多少个人会赢。

上文中 「比赛」 的意思是,对于所有整数 ii 满足 0i<l0\leq i<l,让第一排的第 x+ix+i 个人和 第二排的第 y+iy+i 个人进行 「石头剪刀布」 游戏。

任务三

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

输入格式

此题提供了模板程序。选手可以在此基础上编写自己的程序,模板程序详见下文数据范围与提示。

第一行一个整数task_id(1task_id3) task\_id(1\leq task\_id\leq3),表示任务编号。接下来是每个具体任务的输入内容。

在输入的同一行中,相邻的两个整数会被一个空格隔开。

对于任务一:一行,两个整数 n,sn,s。令 $a_0=next\_integer(s),a_i=next\_integer(a_{i-1}),1\leq i<n$,则 a0,a1,,an1a_0,a_1,…,a_{n-1} 即为需要排序的 nn 个整数。

对于任务二:第一行两个整数 n,qn,q。第二行一个仅包含 0,1,20, 1, 2 的长度为 nn 的字符串,第 ii 个字符所代表的整数表示第一排第 ii 个人的策略(即 a1ia_{1i}​​)。第三行格式同第二行,表示第二排各个人的策略。

对于任务三:第一行一个整数 nn,表示给定的串的长度。第二行一个字符串,即为给定的串。

输出格式

对于任务1:令 bb 为已经排好序的数组,调用 output_arr(b, n * 4) 即可。

对于任务2:将每个询问的答案依次存入 3232 位无符号整数数组 bb 中(即,存入 b0,b1,,bq1b_0,b_1,⋯,b_{q-1} 中),然后调用 output_arr(b, q * 4) 即可。

对于任务3:输出一个整数,表示不同的方案数除以 2322^{32}​​ 得到的余数。

1
100000 2017012501
4275990336
2
6 6
200100
200211
5 1 3
2 0 1
2 0 3
2 0 2
2 3 4
0 1 3
3349208141
3
4
(???
2
3
4
)???
0

提示

数据范围与提示

任务编号 分值 测试点编号 数据范围与约定 时间限制
1 5 1 n=100000n=100000 3s
19 2 n=108n=10^8 4s
11 3 n=2×108n=2\times10^8 6s
2 7 4 n=q=1000n=q=1000 3s
23 5 n=q=300000n=q=300000
3 9 6 n=1000n=1000
5 7 n=120000n=120000
7 8 n=225000n=225000
14 9 n=266666n=266666

模板程序

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.