【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 中。

数据范围

本题共两个测试点:

提示和说明

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

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


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2020-11-29 00:16:50 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用