第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛（同步赛） - 部分题解

B - 小宝的幸运数组

原题面

描述

对于小宝来说，如果一个数组的总和能够整除他的幸运数字，就是他的幸运数组，而其他数组小宝都很讨厌。现在有一个长度为的数组，小宝想知道这个数组的子数组中，最长的幸运子数组有多长。
对于子数组的定义，如果可以通过从开头和从结束分别删除若干个（可以为零或全部，前后删除个数不必相同）元素来从数组获得数组，则称数组是数组的子数组。（子数组包含原数组，但不包含空串）

输入

多组输入。第一行包含一个整数()，表示有组测试数据。
每组测试数据包含两行，第一行包含两个整数和()，分别表示数组长度和小宝的幸运数字。第二行包含个空格分隔的整数()，为数组的元素。

输出

对于每组数据，输出和能被整除的最长子数组的长度。如果没有这样的子数组，则输出。

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
4 3 3 1 2 3 3 5 1 2 3 3 7 1 2 3 1 6 5	3 2 -1 -1

链接

https://ac.nowcoder.com/acm/contest/11746/B

题解

题意

求元素之和能被整除的最长子串（子数组）的长度。

思路

• 考虑数组的前缀和，表示前个元素之和。
• 若区间为的子数组元素之和能被整除，则，变形得。
• 在求算前缀和的同时记录每一次前缀和对取模的运算结果第一次出现的位置，若某一取模结果出现了两次及以上，则区间为（为该取模结果第一次出现的下标，为当前求算到的下标）的子数组为“幸运数组”。

时间复杂度

代码

T = int(input())
for t in range(T):
    n, k = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    pos = {(s := 0): 0}
    ans = -1
    for i in range(n):
        if (s := (s + a[i]) % k) in pos:
            ans = max(ans, i + 1 - pos[s])
        else:
            pos[s] = i + 1
    print(ans)

C - 上进的凡凡

原题面

描述

凡凡是一个上进的人，他的人生没有下坡路，他也讨厌带有“下坡路”的东西。
所以，对于凡凡来说，只有非降序的数组才是nice的（如：）；若数组元素个数为，也满足非降序，也是nice的。
现在有一个长度为的数组，凡凡想知道它的子数组中有多少个数组是nice的。
你能帮帮他吗？
对于子数组的定义，如果可以通过从开头和从结束分别删除若干个（可以为零或全部，前后删除个数不必相同）元素来从数组获得数组，则称数组是数组的子数组。（子数组包含原数组，但不包含空串）

输入

第一行输入一个整数()，表示数组的长度。
第二行包含个空格分隔的整数()，为数组的元素。

输出

输出给定数组的子数组中是nice数组的个数。（注意使用long long）

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
5 1 2 3 4 5	15

链接

https://ac.nowcoder.com/acm/contest/11746/C

题解

题意

求一个数组中首尾下标不同的不下降子串（子数组）的个数。

思路

• 记为数组中以第个元素作为不下降子串的结尾元素时，整个数组中不下降子串的个数。
• 设为某一不下降子串中从开头到当前下标的元素个数。
• 若（为当前下标），则将累加；否则令。之后令。
• 最后的答案为。

时间复杂度

代码

n = int(input())
a = [int(x) for x in input().split()]
b = [k := 1]
for i in range(1, len(a)):
    if a[i] < a[i - 1]:
        b.append(k := 1)
    else:
        b.append(k := k + 1)
print(sum(b))

D - Seek the Joker I

原题面

描述

长达数日的春日祭终于告一段落，作为巫女的朝野芳乃在打扫完神社本决定好好享受一下久违的宁静。然而守护了神刀数百年的丛雨难耐寂寞，希望芳乃能陪她一起玩扑克消解愁闷。
芳乃并不擅长市井的游戏，所以总是输多赢少。而昨日被芳乃的神乐舞深深吸引，以致一早就前来建实神社希望能再睹芳华的你碰巧听见了此事。尽管不知道为什么美丽的巫女要自言自语地为玩扑克而苦恼，但你毅然决然地毛遂自荐，希望能为芳乃一解眉间愁。
芳乃告诉了你丛雨准备了张扑克牌作为牌堆，每人每次至多从牌堆顶部抽张牌，至少抽张牌。牌堆底部的最后一张牌作为乌龟，抽中的将输掉这一轮比赛。芳乃想知道在你的帮助下，她和丛雨都采取积极策略时，她自己是否一定能获胜。作为被丛雨邀请的一方，每轮游戏都是芳乃先抽。
因为看不见丛雨而误认芳乃罹患精神分裂的你在不由感叹红颜薄命的同时，决定尽全力帮助芳乃完成她的委托。
声明：本题中的所有角色在剧情发生时均已超过18岁。

输入

第一行包含一个整数，表示共有组测试数据。
每组测试数据共一行，包含两个正整数和，分别表示牌堆中有张牌和每次抽取最多抽取张。
数据保证。

输出

对于每组测试数据给出一行结果。
如果芳乃必胜，则输出“yo xi no forever!”，
否则输出 “ma la se mi no.1!”。

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
4 1 1 23 2 6 4 114 514	ma la se mi no.1! yo xi no forever! ma la se mi no.1! yo xi no forever!

链接

https://ac.nowcoder.com/acm/contest/11746/D

题解

题意

巴什博弈。

思路

• 若为的倍数，则后手有必胜策略：在一个回合内保证与先手拿走的牌的总数为。
• 对于其余情况，后手无法保证出现只剩一张扑克牌的情况。

时间复杂度

代码

T = int(input())
for t in range(T):
    n, k = [int(x) for x in input().split()]
    if (n - 1) % (k + 1) == 0:
        print("ma la se mi no.1!")
    else:
        print("yo xi no forever!")

F - 成绩查询ing

原题面

描述

去年的新冠疫情爆发让众多大学生只能只能在家里上学，老师为了方便自己录入成绩和方便大家成绩查询，建立了一个录入和查询成绩的系统，能完成次两种不同的查询，输入查询次数，查询次，每次首先输入查询的模式，为时，输入同学的姓名，并依次输出同学的成绩(）， 学号（}，性别（），为时，输入成绩，输出有具体有哪些同学考到了这个分数，输出同学的，并要求按字典序输出，当没有同学为此分数时，则不输出。字典序，对于字符串，先按首字符排序，如果首字符相同，再按第二个字符排序，以此类推。

输入

第一行包含一个整数，表示系统中共有个人（）。 下面行分别输入个人的姓名，成绩（成绩在之间），性别（或分别表示男性、女性），学号。表示系统中成员的信息 输入查询次数()，接下来行完成次查询任务

输出

输出次查询的结果，当为时，输入同学的姓名，并在一行中依次输出同学的成绩(）， 学号（}，性别（），用空格间隔（注意行末无空格），为时，输入成绩，输出有具体有哪些同学考到了这个分数，输出同学的（每个输出一行，无空格），并要求按字典序输出，当没有同学为此分数时，则不输出。

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
5 N 28 2 7475 UN 83 2 27550 EXF 5 2 17298 OVYNH 51 2 14827 XNV 53 1 7591 2 1 XNV 2 27	53 7591 1

链接

https://ac.nowcoder.com/acm/contest/11746/F

题解

题意

用名字查询该学生的信息；或用成绩查询获得该成绩的所有学生的姓名。

思路

• 采用支持哈希的容器按姓名存储信息。
• 对于按成绩查询，可以先将所有姓名按字典序排序，再按成绩存储信息。

时间复杂度

代码

from collections import defaultdict

n = int(input())
hmc = list()
for i in range(n):
    xm, cj, xb, xh = input().split()
    hmc.append((xm, cj, xh, xb))
hmc.sort(key=lambda x: x[0])
q = [{xm: y for xm, *y in hmc}, defaultdict(list)]
for xm, cj, *_ in hmc:
    q[1][cj].append(xm)
m = int(input())
for i in range(m):
    t = int(input()) - 1
    s = input()
    if s in q[t]:
        print((" ", "\n")[t].join(q[t][s]))

H - 数羊

原题面

描述

憨憨小杨晚上睡不着觉，就开始数羊，她觉得一只一只数太慢了，突发奇想出了一种新的数羊方式，羊羊数量由两个整形变量和决定，计算方式如下:

$$\begin{cases}A\left(1,0\right)=2&\\A\left(0,m\right)=1&m\geq0\\A\left(n,0\right)=n+2&n\geq2\\A\left(n,m\right)=A\left(A\left(n,m-1\right),m-1\right)&n,m\geq1\end{cases}$$

现在给出和的值，请你帮小杨数数一共有多少只羊。

输入

多组输入。
第一行包含一个整数()，表示有组测试数据。
每组测试数据包含一行，包含两个整数()和().

输出

对每一组输入，在一行中输出的值,由于输出的结果可能会很大，答案对取模

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
3 3 0 3 1 3 2	5 6 8

链接

https://ac.nowcoder.com/acm/contest/11746/H

题解

题意

计算函数。

思路

• 由于较大，直接递归计算不可取。
• 观察到范围中的，又因为为整数，故只会取三个值。
• 引理：最终会化归为（）或（）的形式。
• 推论：由引理可知的结果是一个正整数。
• 若，则。
• 若，则。
  • 若，则左边最终会化归为的形式，故，即。故。
  • 若，则且，故为一个首项为、公差为的等差数列。故通项为（）。
  • 综上所述，（）。
• 若，则（），故为一个首项为、公比为的等比数列。故通项为（）。
• 综上所述，。

时间复杂度

代码

def fpower(a: int, b: int) -> int:
    ans = 1
    while b:
        if b & 1:
            ans = ans * a % 998244353
        a = a * a % 998244353
        b >>= 1
    return ans

T = int(input())
for t in range(T):
    n, m = [int(x) for x in input().split()]
    if m == 0:
        print(2 if n == 1 else n + 2)
    elif m == 1:
        print(2 * n)
    else:
        print(fpower(2, n))

I - 买花

原题面

描述

情人节马上要到了，阳阳想送出朵花给喜欢的妹妹，他打算提前开始买。但是，因为他有强迫症，所有的花要分天买（，即不能一天全买完）,第一天他可以买任意朵花，之后每一天买花的数量为前一天的两倍，（如若第一天买朵，第二天就要买朵，以此类推）。
现在离情人节还有天（），请你告诉阳阳，他能不能刚好买到朵花。

输入

多组输入。第一行一个正整数（)，表示数据组数。
接下来T行，每行一个正整数（)，表示预计买花的数量。

输出

每组数据输出一行，共行。
判断能否刚好买到朵花，可以则输出”YE5“，否则输出”N0“。

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
2 21 20	YE5 N0

链接

https://ac.nowcoder.com/acm/contest/11746/I

题解

题意

构造数列满足（）。求是否，使得。

思路

• 设，则通项为，前项之和为。
• 原问题可以转化为是否存在一个使得。
• 由于只会取得之间的整数，故可以预处理出所有后依次判断是否能被整除。
• 注意输出。

时间复杂度

代码

F = [(1 << i) - 1 for i in range(2, 16)]
for t in range(int(input())):
    n = int(input())
    for f in F:
        if n % f == 0:
            print("YE5")
            break
    else:
        print("N0")

J - 这是一题简单的模拟

原题面

描述

财务计划要从家里出发，去个城市出差，然后再回到家中，但个出差地点之间不一定都能通车，现在他要筛选出花费最少的路径，你能帮帮他吗？

输入

第一行为两个正整数和（，），分别表示有个出差地点和这些地点之间的条通路，其中出差地点用到编号，而财务的家所在城市用编号表示。
随后的行，每行给出通路连接的两个城市和这条通路上的花费，格式为：
```
城市A 城市B 花费
```
通路是双向的，且两个城市间最多有一条通路，不存在自环。保证所有花费大于。
再下一行给出一个正整数（），表示现在有K条推荐路径（注意：给出的路径不一定能通过或可能不满足财务的要求）。
接下来行每一行表示一个推荐路径，第一个整数表示途径的城市数，后面有()个整数()(表示途经的城市（不包括财务的家），如：

3 1 2 3

表示实际路径为。

输出

请你检验给出的条推荐路径，当它满足：

1. 给出的路径能实际通车，即路径中相邻城市存在通路；
2. 给出的路径恰好能都到达个出差城市一次，即不能漏掉某个城市，也不能重复到达。

则称这条路径是可行的。
对于给出的条推荐路径，请输出其中可行路径中最少的花费，若不存在可行路径，请输出”-1“。(题目保证花费和不超过int范围）

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
5 10 0 1 5 0 5 12 1 2 2 2 3 8 3 4 13 1 3 11 0 2 5 0 4 9 4 5 6 3 5 7 5 5 1 3 2 3 1 5 3 2 1 4 5 5 2 1 3 5 4 6 1 2 3 4 5 1 5 1 2 3 5 4	37

链接

https://ac.nowcoder.com/acm/contest/11746/J

题解

题意

在一张给定的无向图上，判断给定的一条路线是否可以从起点既不重复、又不遗漏地经过全部个点再回到起点。

思路

• 由于较小，可以使用邻接矩阵存图。
• 直接按照给定的路线模拟遍历即可。
• 用set（集合）可以达到不重复、不遗漏的需求。

时间复杂度

代码

n, m = [int(x) for x in input().split()]
dis = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
    u, v, cap = [int(x) for x in input().split()]
    dis[u][v] = dis[v][u] = cap
k = int(input())
ans = 0x7fffffff
for i in range(k):
    _, *a = [int(x) for x in input().split()]
    a.append(0)
    vis = set()
    cur = 0
    s = 0
    for x in a:
        if dis[cur][x] > 0 and x not in vis:
            s += dis[cur][x]
            vis.add(x)
            cur = x
        else:
            break
    else:
        if len(vis) == n + 1:
            ans = min(ans, s)
print(-1 if ans == 0x7fffffff else ans)

题外话

• 这题是2020年团体程序设计天梯赛进阶级第四题《网红点打卡攻略》的原题，只是换了个背景，最终要求算的内容比原题要简单一些。
• 题目数据存在问题：不考虑重复到达也可以AC。

K - 黑洞密码

原题面

描述

近些日子，某科学家接受到了来自外太空的神秘讯息，在经过了一段时间的研究后，科学家发现讯息是一个由字母和数字组成的字符串str，想要破译，需要通过一定的规则将字符串进行转换。规则如下：

1. 确定讯息的长度为；
2. 字符串中第的字母和第()的数字为一组，共组；
3. 每组的第个字符分别往后推每组第个数字个数 例：如第一个字母为a，第一个数字为，转换后变为d，’z‘之后是’B‘,’Z‘之后是’b‘;
4. 将每组内部字母的顺序颠倒；
5. 将四组字符合并就是最后的讯息。

输入

输入一个长度为的字符串

输出

输出转换后的密码

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
Zzc6Ltw2OD4yR640263W7G8G30HW9C71	RgCgJQwxJfYCDeQG

链接

https://ac.nowcoder.com/acm/contest/11746/K

题解

题意

• 将字符串中所有字母、数字按原字符串顺序分成两排。
• 字母和数字分别按顺序取四位为一组，各分为四组。
• 取第一组字母和第一组数字，第一个字母向后移动第一个数字位，第二个字母向后移动第二个数字位，……，以此类推，然后将得到的四个新字母颠倒顺序。
• 取第二组字母和第二组数字，重复上一步中的流程。
• 第三、四组字母和数组按上述流程重复。
• 将得到的四组新字母依次首尾拼接，得到答案并输出。

思路

按照题意模拟即可，但需要一些花时间来理解出题人的谜语。

时间复杂度

代码

def trans(c: str, k: int) -> str:
    y = (x := ord(c)) + k
    if x <= 90 and y > 90:
        y += 7
    elif x <= 122 and y > 122:
        y -= 57
    return chr(y)

s = input()
ds = list()
ls = list()
for c in s:
    if 48 <= ord(c) <= 57:
        ds.append(int(c))
    else:
        ls.append(c)
ans = ""
for i in range(0, 16, 4):
    ans += trans(ls[i + 3], ds[i + 3])\
         + trans(ls[i + 2], ds[i + 2])\
         + trans(ls[i + 1], ds[i + 1])\
         + trans(ls[i], ds[i])
print(ans)

L - 建立火车站

原题面

描述

新冠疫情，导致了各个城市之间物资输送的障碍。假设有个城市在一条直线上，为了物资能顺利抵达各个城市，可以在路线上建立最多个数为个暂时停靠站，由于火车在两个站台（城市也算站台）之间的距离越近，需要的总花费越少，因此我们需要让火车相邻两个站台之间的最大距离最小，求出距离,, ，所有城市坐标小于等于，且不存在负值。提醒： 城市坐标均为正整数，且停靠站只能建在整数坐标点上。

输入

第一行输入城市个数，可建立停靠站个数，
第二行输入个城市的坐标（不保证前一个城市坐标比后一个城市小）。

输出

输出

时空限制

• 时间限制：C/C++，其他语言
• 空间限制：C/C++，其他语言

样例

输入	输出
2 2 4 106	34

链接

https://ac.nowcoder.com/acm/contest/11746/L

题解

题意

数轴的正半轴上有一部分整数点已知，现需要在正半轴上添加一些整数点，使得相邻两点之间的最大距离最小。

思路

• 若已知相邻两点之间的最大距离为，则对于以任意两相邻已知点为左右端点的区间内，都可以计算出在保证在当前这一区间内添加若干个点后的相邻两点间的最大距离为的前提下，添加最少的点的数量。
• 即，在当前这一区间内距离左端点处添加点。
• 若从左往右遍历所有由相邻已知点构成的区间后添加的点的数量不超过给定的，则表示这个最大距离是可能的答案之一，并且最优答案不会超过。
• 故，该问题满足答案单调性，可以使用二分答案求解。

时间复杂度

代码

n, k = [int(x) for x in input().split()]
pos = sorted(int(x) for x in input().split())
l = 1
ans = r = 1000000000000

def check(itv: int) -> bool:
    cnt = 0
    for i in range(1, n):
        dis = pos[i] - pos[i - 1]
        cnt += dis // itv - (0 if dis % itv > 0 else 1)
    return cnt <= k

while l <= r:
    if check((mid := l + r >> 1)):
        r = (ans := mid) - 1
    else:
        l = mid + 1
print(ans)