考试时长：180分钟 开始考试时间：2023-12-22 08:30:01 离考试结束时间：00:00:00

比赛说明

注意事项

1. 所有题目均不需要文件读写。
2. 代码最终在Linux操作系统下测评。
3. 时间内存限制

第1题 二进制整除

交换二进制数相邻两个位置的数字，需要花费1元的代价。

读入整数n以及n位二进制数(也许有前导0)，你需要依次回答n个独立的问题，第i个问题(1<=i<=n)是这样的：

假如要使得读入的二进制数是2^i的倍数，至少需要花费多少元的代价？如果不可能，则输出-1。

注意：每个问题都是独立的，不会相互影响，也就是说，每个问题只是假设，不会真的改变n位二进制数，纯粹是为了计算答案而已。

输入格式
第一行，一个整数n。1<=n<=100000。

第二行，n位二进制数，每位是0或1。

【提示】

60%的数据，n<=10。

输出格式
一行，共n个整数。

输入/输出例子1
输入：

5

10101

输出：

1 3 -1 -1 -1 

样例解释
无

作答区域

第2题 棋盘

有一个R行C列的棋盘，共有R×C个单元格子，每个单元格子都要放一个棋子，棋子只有黑色或者白色。

如果两个单元格子有公共边，那么称为相邻的格子。

如果一个棋盘满足所有相邻格子的棋子都是不同颜色，那么就称为“优美”棋盘;否则称为“普通”棋盘。

把棋盘上的一个黑色棋子变成一个白色棋子，需要耗费1个能量。

同理，把棋盘上的一个白色棋子变成一个黑色棋子，也需要耗费1个能量。

如果把一个“普通”棋盘变成“优美”棋盘，至少需要消耗D能量，那么该“普通”棋盘的代价就是D。

下面的“普通”棋盘的代价就是2，因为至少要消耗2个能量，才能变成“优美”棋盘

WBWBW

BWBWB

BBWWW

BWBWB

容易发现，代价是D的“普通”棋盘，可能有很多种。

求：总共有多少种不同的代价是D的“普通”棋盘？模1000000007。

输入格式
一行，3个整数，R,C,D。1<=R,C<=100, 0<=D<=100。

【提示】

60%的数据，1<=R,C,D<=10。

输出格式
一个整数。

输入/输出例子1
输入：

2 2 1

输出：

8

输入/输出例子2
输入：

9 4 15

输出：

135805043

样例解释
无

作答区域

第3题 步数

有一个二维网格，从上往下，行的编号从1至n，从左往右，列的编号是1至m。

第i行第j列的格子编号为(i,j)，如果 ai为 '@',表示格子(i,j)有障碍物，

如果ai为'.'则表示格子(i,j)可通行。

奶牛bessie当前在 格子(r1,c1)，它每一步可以选择往上、下、左、右四个方向之一走 1 至k 格，也就是每一步至少走1格，最多可以走k格。

任何时刻都不能进入障碍物格子，也不能走到网格外面，不能走出界。

问你最少需要多少步才能走到 格子(r2,c2) ，如果不能走到，输出 −1 。

输入格式
第一行，n,m,k。 1<=n,m,k<=1000000, n*m <= 1000000。

第二行，r1, c1, r2, c2。 1<=r1,r2<=n, 1<=c1,c2<=m。

接下来是n行m列的二维网格a1..n，其中ai是'@'或'.'。

【提示】

本题测试点数据较大，只有约10%的数据满足n*m<=100

输出格式
一个整数。

输入/输出例子1
输入：

3 5 2

3 2 3 4

.....

.@..@

..@..

输出：

5

输入/输出例子2
输入：

1 6 4

1 1 1 6

......

输出：

2

样例解释
无

作答区域

第4题 干草

有n袋干草，第i袋干草的重量是w[i]。奶牛bessie当前的快乐值是0，bessie希望它的快乐值至少要达到s。

如果奶牛吃掉第i袋干草，奶牛的快乐值会增加w[i]。

对于一袋干草来说，bessie要么整袋吃掉，要么不吃，不能吃这袋干草的一部分。

如果bessie当前的快乐值小于s，那么bessie必须要继续挑选干草吃。

bessie最近的感知功能不是很好，有一个延迟参数t。

如果t等于0，那么奶牛当前快乐值只要不小于s，那么它就不再吃干草了。

如果t是正整数，那么奶牛快乐值达到s以后，仍然要额外多吃t袋干草。

求奶牛bessie能吃到的干草的总重量的最大值是多少。
注意：有可能bessie吃完所有的干草后，快乐值仍然没达到s。

输入格式

第一行，三个整数: n, s, t。1<=n<=100, 1<=s<=10000, 0<=t<=100。

第二行，n个正整数，第i个整数是w[i]。 所有w[i]的总和不超过1000000000。

【提示】

有50%的数据，n<=10。

输出格式
一个整数。

输入/输出例子1
输入：

4 1234 0

10 20 30 40 

输出：

100

输入/输出例子2
输入：

3 100 0

100 100 100 

输出：

100

输入/输出例子3
输入：

5 101 2

100 100 100 100 100 

输出：

400

样例解释
无

作答区域

第5题 子网格

给出一个n行m列的二维网格a1...n，从上往下，行的编号从1至n，从左往右，列的编号是1至m，第i行第j列的数是ai。

有一个高度是r，宽度是s的长方形计算器。

每次你可以选择二维网格的某个格子(i,j)作为左上角，然后把计算器的左上角对准格子(i,j),覆盖下去，

计算器会自动计算出二维网格被覆盖区域的最大值，注意计算器的边要与二维网格的边平行，同时计算器不能超出二维网格。

二维网格被计算器覆盖的部分，称为二维网格的“子网格”。

现在的任务是：把计算器从二维网格的第1行第1列开始，从上往下，从左往右，每覆盖一次，就输出对应的“子网格”的最大值。

输入格式
第一行，n和m， 1<=n,m<=4000。

接下来是n行m列的二维网格，其中-10000<=ai<=10000。

最后一行是r和s。1<=r<=n, 1<=s<=m。

序号

满足性质

分值占比

1 n,m<=40, r=n, s=m    12%

2 n,m<=40           16%

3 n,m<=1000         26%

4 无特殊性质         46%

输出格式
共n-r+1行，每行输出m-s+1个数。

其中第i行第j列的数表示把计算器左上角对准二维网格第i行第j列格子，覆盖下去，计算器得到的最大值。

输入/输出例子1
输入：

3 3

1 1 2

2 3 4

4 3 2

3 3

输出：

4

输入/输出例子2
输入：

3 3

1 1 2

2 3 4

4 3 2

2 1

输出：

2 3 4

4 3 4

样例解释
第2个样例，计算器的覆盖过程如下，其中红色的数是最大值。

image.png

作答区域

第6题 排行榜

某次IOI总决赛比赛有3道题。第i题的分值是P[i]分。如果选手提交了第i题，那么选手该题可能的得分是1至P[i]分；如果选手不提交第i题，那么该选手第i题得分肯定是0分。现在比赛结束了，你很想看一下“排名榜”。“排名榜”按照选手的总分从高到低排序，每一个选手都有3列，第1列是该选手第1题的得分，第2列是该选手第2题的得分，第3列是该选手第3题的得分。本次总决赛很特殊，不进行网络直播，所以只有在总决赛现场的人才能看到“排名榜”。作为今年NOIP不到500分的选手，很显然，你不在总决赛现场。于是你打电话给在总决赛现场的朋友FJ。FJ不直接告诉你“排名榜”，而是按照“排名榜”从第1名到最后1名的顺序，给你一个N行3列的二维数组submit1..N，其中submiti要么是'Y'要么是'N'，表示第i个选手是否提交了第j题, 而且FJ还明确告诉你：所有选手的总分都不相同。那么，现在的问题是：有多少种不同的“排名榜”满足上述的题意？答案模1000000007。由于FJ可能忽悠你，所以当不存在方案满足题目的要求时，输出0。

输入格式
多组测试数据。

第一行，一个整数G，表示有G组测试数据。1 <G<=3。

每组测试数据格式如下：

1. 第一行，3个整数，分别是P[1],P[2],P[3]。25000<=P[1]<=30000， 45000<=P[2]<=60000, 90000<=P[3]<=110000。
2. 第二行，一个整数N。1 <= N <= 20。
3. 接下来是N行3列的二维矩阵。每个元素要么是'Y'，要么是'N'，
   submiti=‘Y’表示选手i提交了第j题。submiti=‘N’表示选手i没有提交第j题。

输出格式
共G行，每行一个整数。

输入/输出例子1
输入：

3

25000 50000 100000 

2

YNN

NNN

30000 60000 90000 

2

NYN

NYN

25000 45000 110000 

2

NNN

YYY

输出：

25000

799969993

0

样例解释
无

作答区域