2021年ECNU计科考研复试机试

本次机试共4题,不直接将分数计入成绩,仅在面试时用于参考。

前3题为中文题面,第4题英文题面。


A. 平衡三进制 II

[mathjax]

平衡三进制系统以\( 3 \)为基数,但其数码不是使用数字\(0 \)、\(1 \)和\( 2\),而是用数字\(-1 \)、\(0 \)和\(1 \)来表示一个数码。

下表给出平衡三进制数对应的十进制数,其中我们以\( 2\) 表示\( -1\) 。

平衡三进制十进制
\( 102 \)\(8 \)
\( 1120.22 \)\( 32 \frac{5}{9}\)
\( 2210.11\)\( -32 \frac{5}{9} \)

例如 \( 32 \frac{5}{9} = 1\times 3^3 + 1 \times 3^2 + (-1) \times 3^1 + (-1) \times 3^{-1} + (-1) \times 3^{-2} \)

一个十进制数转换为平衡三进制数的一种方法为:

  1. 先将该十进制数表示成普通的三进制数
    • 例如 \( 32 \frac{5}{9} = (1012.12)_3 \)
  2. 将得到的三数与全1序列按三进制记数系统的规则相加
    • 例如 \( 1012.12 + 1111.11 = 2201.00 \)
  3. 将第2步得到的序列与全1序列按位独立相减
    • \( 2201.00 - 1111.11 = 1,1,-1,0.-1,-1 \),其中将\(-1\)用\(2\)表示则为\(1120.22 \)

输入一个十进制数,请将其转换为对应的平衡三进制数

输入格式

在一行中输入两个十进制整数A,B,用一个空格分隔,这表示十进制数\( \frac{A}{B} \),本题数据保证 \( B\)是3的自然数次幂,即 \( B = 3^k ,k \in \mathbb{N} \)

数据量限制:

  • 对于\( 20\% \)的数据,\( 0 \leq A,B \leq 30 \)
  • 对于\( 50\% \)的数据,\( -30 \leq A \leq 30, 0 \leq B \leq 30 \)
  • 对于\( 70\% \)的数据,\( 0 \leq A,B \leq 10^9 \)
  • 对于\( 100\% \)的数据,\( 10^{-9} \leq A \leq 10^9, 0 \leq B \leq 10^9 \)

输出格式

在一行中输出对应的平衡三进制数,用2表示-1。三进制数应该取最简形式,即整数部分无前导0,小数点之后末尾没有多余的后缀0:

  • 01000 应输出 1000
  • 0.111100 应输出 0.1111

测试样例

组数InputOutput
Sample 18 1102
Sample 2293 91120.22
Sample 3-293 92210.11

B. 矩形个数

[mathjax]

在一个由 \(0\)、\(1\) 元素构成矩阵中,统计至少含有 \( k \)个 \(1\) 的矩形的个数(矩形边界平行于矩阵边界)。
注意:单个元素也算是一个矩形。

输入格式

第一行,有四个空格分隔的整数,\(r,c,n,k\) ( \(1 \leq r,c,n \leq 500, 1 \leq k \leq n\) ) 分别表示矩阵的行数,列数,矩阵中 \(1\) 的个数,和题意中给出的 \( k \)。

接下来 \( n \) 行,每行两个空格分隔的整数 \( x \) 和 \( y \),表示每个 \( 1 \) 所在的位置 ( \( 1\leq x_i \leq r, 1 \leq y_i \leq c \))

输出格式

输出1行1个数字,表示矩形的个数。

测试样例

Input

5 5 4 2
5 4
5 5
1 5
2 4

Output

41

C. 子序列

[mathjax]

给定一个长度为 \( n \) 的非负整数序列 \( a_1,a_2,a_3,\cdots , a_n \),求出和不小于\(S \)的连续子序列\( a_l,a_{l+1},\cdots,a_r (1\leq l \leq r \leq n)\)的最短长度,即满足\( \sum_{i=l}^r a_i \geq S \)的最短连续子序列长度。

由于序列可能很长,以生成的方式给出序列:给出序列的首项\( a_1\)和一个乘数\( b\),序列其余各项的值为 \( a_i = (b \cdot a_{i-1} ) \mod (10^9 + 7) (1 < i \leq n)\) 。

输入格式

第一行两个整数 \( n,S (3\leq n \leq 5 \times 10^7, 1\leq S \leq 10^18) \),代表序列长度以及序列和的限制。

第二行给出两个整数\( a_1, b (0 \leq a,b < 10^9 + 7) \) ,含义如题目描述。

  • 对于\( 10\% \)的数据,\(1 \leq n \leq 500\)
  • 对于\( 30\% \)的数据,\(1 \leq n \leq 10^4\)
  • 对于\( 65\% \)的数据,\(1 \leq n \leq 2\times 10^6\)
  • 对于\( 100\% \)的数据,\(3\leq n \leq 5 \times 10^7\)

输出格式

一行一个整数,代表满足要求的连续子序列的最短长度。如果和不小于 \(S\) 的连续序列不存在,输出 \(-1\)。

测试样例

样例1

Input

3 6
1 2

Output

2

Hint:实际序列为 \( 1,2,4 \)

样例2

Input

5 1743745293
714636908 681692770

Output

3

Hint:实际序列为 714636908, 948615497, 288206443, 85239381, 340225887。

样例3

Input

3 8
1 2

Output

-1

Hint:实际序列为 \( 1,2,4 \)


D. Weights II

[mathjax]

Merchants measured many commodities using weights and a two-pan balance. If you are using a limited set of weights, however, you can only measure certain quantities accurately. For example, suppose that you have only two weights: a 1-ounce weight and a 3-ounce weight. With these you can easily measure out 4 ounces, as shown in Figure1.

Figure 1

It is somewhat more interesting to discover that you can also measure out 2 ounces by shifting the 1-ounce weight to the other side, as shown in Figure2.

Figure 2

Write a program to determine whether it is possible to measure out the desired target amount with a given set of weights.

输入格式

First line contains a single integer \( t(t<1000 ) \)

The first line of each test case contains an integers \( n( 1\leq n \leq 100)\) – thesize of the given set of weights.

The second line of each test case contains \( n \)integers\( w_1,w_2,\cdots, w_n( 1\leq w_i \leq 10^4 )\)

The third line of each test case contains an integer\( q(1\leq q \leq 10^4 )\)– thenumber of queries.

The fourth line of each test cases contains distinct integers – the desired target amounts.

It’s guaranteed that the sum of all does not exceed \( 10^4\).

输出格式

For each test case, output a binary string ,\( s\) s.t. \(s_i=1 \) if it is possible measure out the desired target amount \( W_i\) with the given set of weights and \( s_i=0 \) otherwise.

测试样例

Input

3
2
1 3
6
1 2 3 4 5 6
2
1 4
6
1 2 3 4 5 6
3
3 5 9
18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Output

111100
101110
111111111011010010


Written by malic in All on 月 17 5月 2021. Tags: 程序设计