3月12笔试

目录

1. 第一题
   1. 解答
2. 第二题
   1. 解答
3. 第三题
   1. 解答（没全过，46%）
4. 第四题
5. 第五题

第一题

2020春招 技术综合试卷在线笔试

编程题|20.0分1/5

双行道

时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

有一个2n的网格，有一个人位于(1,1)的位置，即左上角，他希望从左上角走到右下角，即(2,n)的位置。在每一次，他可以进行三种操作中的一种：1． 向右走一格，即从(x,y)到(x,y+1);2． 向上右方走一格，即，如果他在(2,y)的位置可以走到(1,y+1);3． 向下右方走一格，即，如果他在(1,y)的位置可以走到(2,y+1); 问题当然不会这么简单，在这2n的格子中，有一部分格子上有障碍物，他不能停在障碍物上，当然也不能走出网格，请问他有多少种不同的路线可以到达(2,n)。

输入

输入第一行仅包含一个正整数n，表示网格的长度。(1<=n<=50)

接下来有2行,每行有n个字符，“X”代表障碍物，“.”代表可以停留。

输出

如果没有可以到达的路线则输出-1，否则输出方案数量。

样例输入

5
..X.X
XX...

样例输出

2

规则

请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果
点击“调试”亦可保存代码
编程题可以使用本地编译器，此页面不记录跳出次数

解答

import functools
n = int(input())
mp = [input() for _ in range(2)]


@functools.lru_cache()
def dfs(i, j):
    global cnt
    if j == n-1:
        return 1
    a = 0
    if mp[0][j+1] == '.':
        a += dfs(0, j+1)
    if mp[1][j+1] == '.':
        a += dfs(1, j+1)
    return a
cnt = dfs(0, 0)
if cnt == 0:
    print(-1)
else:
    print(cnt)

错误解法：刚开始看成是走法种数，但实际上是路线种数。

dp = [[0] * n, [0] * n]
dp[0][0] = 1
if mp[0][0] == '.':
    for i in range(1, n):
        c = 0
        if mp[0][i-1] == '.':
            c += dp[0][i-1]
        if mp[1][i-1] == '.':
            c += dp[1][i-1]
        if c == 0: break
        if mp[0][i] == '.':
            dp[0][i] = c
        if mp[1][i] == '.':
            dp[1][i] = c
    if dp[1][-1] > 0:
        print(dp[1][-1])
    else:
        print('-1')
else:
    print('-1')

第二题

2020春招 技术综合试卷在线笔试

编程题|20分2/5

最好一样

时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 131072KB；其他语言 655360KB

题目描述：

给出一个序列包含n个正整数的序列A，然后给出一个正整数x，你可以对序列进行任意次操作的，每次操作你可以选择序列中的一个数字，让其与x做按位或运算。你的目的是让这个序列中的众数出现的次数最多。请问众数最多出现多少次。

输入

输入第一行仅包含两个正整数n和x，表示给出的序列的长度和给定的正整数。(1<=n<=100000,1<=x<=1000)

接下来一行有n个正整数，即这个序列，中间用空格隔开。(1<=a_i<=1000)

输出

输出仅包含一个正整数，表示众数最多出现的次数。

样例输入

5 2
3 1 3 2 5

样例输出

3

提示

样例解释
例如如果序列中所有数字都不修改时，众数为3，3出现的次数为2，如果我们把两个3都做如题操作，序列会变为1，1，1，2，5，此时众数为1，出现次数为3，所以我们选择后者方案，输出众数出现的次数，即3。

规则

请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果
点击“调试”亦可保存代码
编程题可以使用本地编译器，此页面不记录跳出次数

解答

n, x = [int(v) for v in input().split()]
import collections
cnt = collections.Counter()
#l = [3, 1, 3, 2, 5]
l = [int(v) for v in input().split()]
for v in l:
    cnt[v]+= 1
    vv = v | x
    #print(v, vv)
    if vv != v:
        cnt[vv] += 1
ll = list(cnt.values())
ll.sort(reverse=True)
print(ll[0])

题目样例有错

第三题

2020春招 技术综合试卷在线笔试

编程题|20.0分3/5

整除的数组

时间限制：C/C++语言 3000MS；其他语言 5000MS
内存限制：C/C++语言 131072KB；其他语言 655360KB

题目描述：

小美曾经有一个特殊的数组，这个数组的长度为n。但是她在打恐怖游戏的时候被吓得忘记了这个数组长什么样了。不过她还记得这个数组满足一些条件。首先这个数组的每个数的范围都在L和R之间。包括端点。除此之外，这个数组满足数组中的所有元素的和是k的倍数。但是这样的数组太多了，小美想知道有多少个这样的数组。你只需要告诉她在模1e9+7意义下的答案就行了。

输入

一行四个整数n,k,L,R

（1≤n≤1e5 1≤k≤10 1≤L≤R≤1e9）

输出

输出一个数表示满足条件的数组的个数。

样例输入

9 1 1 3

样例输出

19683

规则

请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果
点击“调试”亦可保存代码
编程题可以使用本地编译器，此页面不记录跳出次数

解答（没全过，46%）

# 9 1 1 3
n,k,L,R = [int(v) for v in input().split()]
MOD = int(1e9+7)

# print((L-1)//k,R//k)
mod = [(R // k - (L-1) // k)% MOD] * k
# print(((L-1) // k)*k,L)
for i in range(((L-1) // k)*k,L):
    mod[i%k] -= 1
# print((R // k)*k,R+1)
for i in range((R // k)*k,R+1):
    mod[i%k] += 1
for i in range(len(mod)):
    mod[i] = mod[i] % MOD

d = mod
#print(mod)
for i in range(n-1):
    #print(d)
    dd= [0] * k
    for j in range(k):
        for l in range(k):
            dd[(j+l)%k] += (d[j] * mod[l]) % MOD
    d = dd
print(d[0])

第四题

2020春招 技术综合试卷在线笔试

编程题|20.0分4/5

物资采购

时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 131072KB；其他语言 655360KB

题目描述：

某公司要建厂投产一种产品，已知该产品共需要k种不同的原材料才能生产，而在这个工厂周围有n个可供建厂的地址，同时这n个位置都生产该产品所需k种原材料中的一种，在这n个位置间存在一些通行的道路，我们可以视这些道路的长度都为1，保证这些位置之间两两都是连通的。很显然工厂面临一个很严峻的问题，就是原料采集，我们定义采集一种原材料的花费为工厂所在位置到最近的一个该材料的采集点的距离，在一个位置建厂的成本为k种原材料的采集花费之和。请你对每一个位置都求出其建厂的花费。

输入

输入第一行有三个正整数n,m,k，分别代表可供选择的建厂地址数量，编号为从1到n，这些地址之间的道路数量，生产所需的原材料数量，编号为1到k。(1<=n,m,<=50000,1<=k<=100)

输入第二行包含n个正整数，第 i 个正整数a_i表示第i个地址是第a_i种原料的采集点。(1<=a_i<=k)

接下来有m行，每行有两个正整数 u，v，表示u号位置和v号位置之间有一条连接的路径，可能存在重边或自环（如样例所示）。

输出

输出包含 n 行，每行一个正整数，第 i 行表示第个位置的建厂成本。

样例输入

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

样例输出

3 3 3 2 3

规则

请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果
点击“调试”亦可保存代码
编程题可以使用本地编译器，此页面不记录跳出次数

第五题

2020春招 技术综合试卷在线笔试

编程题|20.0分5/5

小仓的射击练习1

时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

小仓酷爱射击运动。今天的小仓会进行N轮射击，已知第i次射击，她击中靶心的概率是a[i] -1 。小仓想知道N轮射击后，偏离靶心次数为 0 ,1 ,2 次的概率分别是多少。

输入

第一行一个数N，代表射击轮数。

第二行 N个数a[i]，第 i个数为a[i]。

1≤N≤100,000

1≤a[i]<998244353

输出

不难证明答案可以表示成一个最简分数 p \ q -1*。

你需要输出三个p \ q -1* 对 998244353取模后的结果，以此来表示偏离靶心次数为 0 , 1 , 2时的概率。

其中q-1是q 在模意义下的逆元，满足q-1\ q* = 1 mod 998244353。

例如1/4, 可以写成748683265，原因是4 * 748683265 % 998244353 = 1,也有且仅有x = 748683265，1 <= x < 998244353满足乘积等于1

样例输入

2
2 2

样例输出

748683265 499122177 748683265

规则

请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果
点击“调试”亦可保存代码
编程题可以使用本地编译器，此页面不记录跳出次数