题解 - [LOJ 2286] 「WC2017」挑战

发表于 更新于 分类于 ， 本文字数： 1.3k 阅读时长 ≈ 5 分钟

知名毒瘤卡常题。别去做，浪费时间

题目链接

原始题面

题目背景

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

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

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

本题分为 \(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
2
1
100000 2017012501

输出样例 #1

1
4275990336

输入样例 #2

1
2
3
4
5
6
7
8
9
10
2
6 6
200100
200211
5 1 3
2 0 1
2 0 3
2 0 2
2 3 4
0 1 3

输出样例 #2

1
3349208141

输入样例 #3

1
2
3
3
4
(???

输出样例 #3

1
2

输入样例 #4

1
2
3
3
4
)???

输出样例 #4

1
0

说明

数据范围与提示

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

模板程序

C++ 模板

Show code

templ.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <string.h>
#include <algorithm>

using u32 = uint32_t;
using u64 = uint64_t;

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 Sorting

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 Game

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);
}
}  // namespace Parentheses

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 模板

Show code

templ.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define bool int
#define true 1
#define false 0

using u32 = uint32_t;
using u64 = uint64_t;

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 模板

Show code

templ.pasview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
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.

解题思路

任务一

基数排序，桶要开小些以便卡入 L1 Cache

任务二

直接 \(O(nq)\) 暴力，使用 popcount 指令和循环展开卡常

任务三

\(O(n^2)\) DP, 依旧是用循环展开卡常

代码参考

Show code

LibreOJ_2286view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <algorithm>
#include <iostream>
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
#define _next(x) (((x ^= x << 13) ^= x >> 17) ^= x << 5)
#define _expanded_rep(len, repp, expressions) \
  {                                           \
    repp = len >> 3;                          \
    while (repp--) {                          \
      { expressions }                         \
      { expressions }                         \
      { expressions }                         \
      { expressions }                         \
      { expressions }                         \
      { expressions }                         \
      { expressions }                         \
      { expressions }                         \
    }                                         \
    switch (len & 7) {                        \
      case 7: {                               \
        expressions                           \
      }                                       \
      case 6: {                               \
        expressions                           \
      }                                       \
      case 5: {                               \
        expressions                           \
      }                                       \
      case 4: {                               \
        expressions                           \
      }                                       \
      case 3: {                               \
        expressions                           \
      }                                       \
      case 2: {                               \
        expressions                           \
      }                                       \
      case 1: {                               \
        expressions                           \
      }                                       \
    }                                         \
  }
void output_arr(u32 *a, u32 &&size) {
  u32 ret = size;
  for (u32 x = 23333333, *_ = a + (size >> 2), *i = a; i < _; ++i) {
    ret ^= *i + x;
    _next(x);
  }
  cout << ret << '\n';
}
namespace task1 {
using data_type = u32 *;
using data_type2 = u32[256];
data_type2 cnt0, cnt8, cnt16, cnt24;
data_type a, b;
u32 n, seed;
void main() {
  cin >> n >> seed;
  a = (data_type)malloc(800000000);
  b = (data_type)malloc(800000000);
  for (u32 *_ = a + n, *i = a; i < _; ++i) {
    *i = _next(seed);
    ++cnt0[seed & 255];
    ++cnt8[seed >> 8 & 255];
    ++cnt16[seed >> 16 & 255];
    ++cnt24[seed >> 24 & 255];
  }
  for (u32 i = 1; i < 256; ++i) {
    cnt0[i] += cnt0[i - 1];
    cnt8[i] += cnt8[i - 1];
    cnt16[i] += cnt16[i - 1];
    cnt24[i] += cnt24[i - 1];
  }
  for (u32 *i = a + n; --i >= a;) b[--cnt0[*i & 255]] = *i;
  for (u32 *i = b + n; --i >= b;) a[--cnt8[*i >> 8 & 255]] = *i;
  for (u32 *i = a + n; --i >= a;) b[--cnt16[*i >> 16 & 255]] = *i;
  for (u32 *i = b + n; --i >= b;) a[--cnt24[*i >> 24 & 255]] = *i;
  output_arr(a, n << 2);
  free(a);
  free(b);
}
}  // namespace task1
namespace task2 {
#define _popcntll __builtin_popcountll
using data_type = i64[64][14063];
using str_type = char *;
using query_type = i32 *;
data_type f1, f2;
void set(data_type &f, u32 &&idx) {
  if (idx < 64)
    for (u32 i = 0; i <= idx; ++i) *f[i] |= 1ull << idx - i;
  else
    for (u32 i = 0, j; i < 64; ++i)
      f[i][(idx - i) >> 6] |= 1ull << ((idx - i) & 63);
}
str_type s1, s2;
query_type q_x, q_y, q_len;
void main() {
  u32 n, q;
  cin >> n >> q;
  s1 = (str_type)malloc(n + 1);
  s2 = (str_type)malloc(n + 1);
  cin >> s1 >> s2;
  q_x = (query_type)malloc(q << 2);
  q_y = (query_type)malloc(q << 2);
  q_len = (query_type)malloc(q << 2);
  for (u32 i = 0; i < q; ++i) cin >> q_x[i] >> q_y[i] >> q_len[i];
  u32 *anss = new u32[q];
  for (u32 idx = 0, i = 0; i < n; ++i, idx += 3) set(f1, idx + s1[i] - '0');
  for (u32 idx = 0, i = 0; i < n; ++i, idx += 3)
    set(f2, idx + s2[i] - '1' + 3 * (s2[i] == '0'));
  i64 *_f1, *_f2;
  for (u32 i = 0, len, repp, ans; i < q; ++i) {
    q_x[i] *= 3;
    q_y[i] *= 3;
    q_len[i] *= 3;
    len = q_len[i] >> 6;
    repp = len >> 3;
    ans = 0;
    _f1 = task2::f1[q_x[i] & 63] + (q_x[i] >> 6);
    _f2 = task2::f2[q_y[i] & 63] + (q_y[i] >> 6);
    _expanded_rep(len, repp, ans += _popcntll(*_f1++ & *_f2++););
    anss[i] = ans + _popcntll(*_f1 & *_f2 & (1ull << (q_len[i] & 63)) - 1);
  }
  output_arr(anss, q << 2);
  free(s1);
  free(s2);
  free(q_x);
  free(q_y);
  free(q_len);
}
#undef _popcntll
}  // namespace task2
namespace task3 {
using str_type = char *;
u32 _[266666 << 1 | 1], *f = _ + 266666;
u32 n;
str_type s;
u32 solve() {
  *f = 1;
  for (u32 i = 0, m, *f0, *f1, repp; i < n; ++i) switch (s[i]) {
      case '(':
        if (i & 1) *--f = 0;
        break;
      case ')': f += i & 1 ^ 1; break;
      case '?':
        m = (min(i, n - i) >> 1) + 1;
        if (i & 1) {
          *--f = 0;
          ++m;
        }
        f1 = (f0 = f) + 1;
        _expanded_rep(m, repp, *f0 += *f1; f0 = f1++;);
    }
  return *f;
}
void main() {
  cin >> n;
  s = (str_type)malloc(n + 1);
  cin >> s;
  cout << solve() << '\n';
  free(s);
}
}  // namespace task3
void (* const _main[4])(void) = {
  nullptr, task1::main, task2::main, task3::main};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  i32 task_id;
  cin >> task_id;
  return _main[task_id](), 0;
}