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

---

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

问题描述

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

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

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

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

任务

有 $2n$ 个人在玩“石头剪刀布”游戏。他们排成两排，每排 $n$ 个人。 每个人在每一局游戏都使用固定策略，即对于第 $i ~ (i \in {1, 2})$ 排的第 $j ~ (0 \le j < n)$ 个人， 用一个整数 $a_{ij}$ 表示他的策略，其中 0 表示只出石头，1 表示只出剪刀，2 表示只出布。

现在有 $q$ 个询问，每个询问给定三个整数 $x, y, l ~ (0 \le x,y < n, 1 \le l \le n - \max (x,y))$ ， 问将第一排的第 $x \sim x + l - 1$ 个人和第二排的第 $y \sim y + l - 1$ 个人比赛之后，第一排有多少个人会赢。

上文中“比赛”的意思是，对于所有整数 $i$ 满足 $0 \le i < l$，让第一排的第 $x + i$ 个人和第二排的第 $y + i$ 个人进行“石头剪刀布”游戏。

“石头剪刀布”游戏的规则是石头赢剪刀，剪刀赢布，布赢石头，除这三种情况以外都不算赢。

数据和询问中，每一排人的下标都是从 0 开始的，即“第 $x (0 \le x < n)$ 个人”表示的是这一排从左到右数的第 $x + 1$ 个人。

接口

void solve(int n, int q, char *s1, char *s2, int *q_x, int *q_y, int *q_len, unsigned *ans);

其中长度为 n 的字符串 s1, s2 存放了每个人的策略（012 中的一个），长度为 q 的数组 q_x, q_y, q_len 分别存放了各个询问的 $x, y, l$ 参数。你需要将各个询问的结果依次存入数组 ans 中。

数据范围

本题共两个测试点：

• 对于第一个测试点，$n = q = 1000$
• 对于第二个测试点，$n = q = 300000$

提示和说明

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

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

---

---