版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [LOJ 2286] 「WC2017」挑战" categories:
知名毒瘤卡常题. 别去做, 浪费时间
<!-- more -->你和同学们找了三道题目用来练习.
这次练习的目标是写出能在时间限制里通过尽量大规模数据的代码.
同学们纷纷写出了优秀的代码. 现在, 他们向你发起了挑战, 他们对每个问题都设置了若干个测试数据, 这是他们能通过的最大规模的测试数据. 现在, 他们想看一看你写的代码究竟能超过多少同学的代码, 通过多大规模的测试数据.
本题分为 $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,a1,…,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,b1,⋯,b{q-1}$ 中）, 然后调用 output_arr(b, q * 4) 即可.
对于任务 3: 输出一个整数, 表示不同的方案数除以 $2^{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=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$ |
基数排序, 桶要开小些以便卡入 L1 Cache
直接 $O(nq)$ 暴力, 使用 popcount 指令和循环展开卡常
$O(n^2)$ DP, 依旧是用循环展开卡常