2024年曲阜师范大学网络空间安全学院天体赛选拔赛

2024年曲阜师范大学网络空间安全学院天体赛选拔赛

图片

L1-1 宇宙无敌大招呼

分数 5

据说所有程序员学习的第一个程序都是在屏幕上输出一句“Hello World”，跟这个世界打个招呼。作为天梯赛中的程序员，你写的程序得高级一点，要能跟任意指定的星球打招呼。

输入格式：

输入在第一行给出一个星球的名字S，是一个由不超过7个英文字母组成的单词，以回车结束。

输出格式：

在一行中输出Hello S，跟输入的S星球打个招呼。

输入样例：

1
Mars

输出样例：

1
Hello Mars

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
S=input()
print("Hello %s" % (S))

L1-2 考试周

分数 5

ksz.jpg

考试周快到了，浙江大学的电子屏又调皮了…… 本题请你帮小编写一个自动倒计时的程序，对给定的日期（例如“腊八”就对应 8）和倒计时天数（例如电子屏上的“四天之后”就对应 4），自动调整公式里的分母（例如 8/2=4 里面的那个 2）。

输入格式：

输入在一行中给出两个正整数：A 是给定的日期，不超过 30；B 是倒计时天数，不超过 10。

输出格式：

在一行中输出公式 A/X=B，其中 X 是满足等式的数字，输出时保留小数点后 1 位即可。

输入样例：

1
8 3

输出样例：

1
8/2.7=3

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
A,B=map(int,input().split())
X=A/B
print("%d/%.1f=%d" % (A,X,B))

L1-3 真的恭喜你

分数 10

当别人告诉你自己考了 x 分的时候，你要回答说：“恭喜你考了 x 分！”比如小明告诉你他考了90分，你就用汉语拼音打出来 gong xi ni kao le 90 fen!。

但是如果小明没考好，比如只考了 20 分，你也“恭喜”人家就不对了。这时候你应该安慰他说：“考了 20 分别泄气！”用汉语拼音写出来就是 kao le 20 fen bie xie qi!。

输入格式：

输入在一行里给出一位小朋友的分数。这个分数是一个 0 到 100 之间的整数。

输出格式：

在一行中输出你对这位小朋友说的话。如果人家考到不低于 90 分，就说 gong xi ni kao le X fen!；如果不到 90 分，就说 kao le X fen bie xie qi!。其中 X 是小朋友输入的分数。

输入样例 1：

1
95

输出样例 1：

1
gong xi ni kao le 95 fen!

输入样例 2：

1
89

输出样例 2：

1
kao le 89 fen bie xie qi!

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
4
5
grade=int(input())
if grade>=90:
    print("gong xi ni kao le %d fen!" % (grade))
else:
    print("kao le %d fen bie xie qi!" % (grade))

L1-4 Cassels方程

分数 10

Cassels方程是一个在数论界产生了巨大影响的不定方程：x2+y2+z2=3*x**yz*。该方程有无穷多自然数解。

本题并不是要你求解这个方程，只是判断给定的一组 (x,y,z) 是不是这个方程的解。

输入格式：

输入在第一行给出一个不超过 10 的正整数 N，随后 N 行，每行给出 3 个正整数 0<x≤y≤z≤1000。

输出格式：

对于每一组输入，如果是一组解，就在一行中输出 Yes，否则输出 No。

输入样例：

1
2
3
2
1 1 1
5 6 7

输出样例：

1
2
Yes
No

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
4
5
6
7
N=int(input())
for i in range(N):
    x,y,z=map(int,input().split())
    if x**2+y**2+z**2==3*x*y*z:
        print("Yes")
    else:
        print("No")

L1-5 6翻了

分数 15

666.JPG

“666”是一种网络用语，大概是表示某人很厉害、我们很佩服的意思。最近又衍生出另一个数字“9”，意思是“6翻了”，实在太厉害的意思。如果你以为这就是厉害的最高境界，那就错啦 —— 目前的最高境界是数字“27”，因为这是 3 个 “9”！

本题就请你编写程序，将那些过时的、只会用一连串“6666……6”表达仰慕的句子，翻译成最新的高级表达。

输入格式：

输入在一行中给出一句话，即一个非空字符串，由不超过 1000 个英文字母、数字和空格组成，以回车结束。

输出格式：

从左到右扫描输入的句子：如果句子中有超过 3 个连续的 6，则将这串连续的 6 替换成 9；但如果有超过 9 个连续的 6，则将这串连续的 6 替换成 27。其他内容不受影响，原样输出。

输入样例：

1
it is so 666 really 6666 what else can I say 6666666666

输出样例：

1
it is so 666 really 9 what else can I say 27

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
x=input()
txt=x+"@"
num_for_6=0
result=""
def replace_6(num_for_6):
    result=""
    if num_for_6<=3:
        result+=num_for_6*"6"
    elif num_for_6>3 and num_for_6<=9:
        result+="9"
    elif num_for_6>9:
        result+="27"
    return result
for i in txt:
    if i=="6":
        num_for_6+=1
    elif i!="6":
        result+=replace_6(num_for_6)
        result += i
        num_for_6=0
print(result[:-1])

L1-6 不变初心数

分数 15

不变初心数是指这样一种特别的数，它分别乘 2、3、4、5、6、7、8、9 时，所得乘积各位数之和却不变。例如 18 就是这样的数：18 的 2 倍是 36，3+6=9；18 的 3 倍是 54，5+4=9；…… 18 的 9 倍是 162，1+6+2=9。对于 18 而言，9 就是它的初心。本题要求你判断任一个给定的数是否有不变的初心。

输入格式：

输入在第一行中给出一个正整数 N（≤ 100）。随后 N 行，每行给出一个不超过 105 的正整数。

输出格式：

对每个给定的数字，如果它有不变的初心，就在一行中输出它的初心；否则输出 NO。

输入样例：

1
2
3
4
5
4
18
256
99792
88672

输出样例：

1
2
3
4
9
NO
36
NO

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def ge_wei_num_sum(x):
    x=str(x)
    result=0
    for i in x:
        result+=int(i)
    return result
def chu_xin(x):
    a=ge_wei_num_sum(x)
    flag=1
    for i in range(2,10):
        if ge_wei_num_sum(x*i)==a:
            continue
        else:
            flag=0
            break
    if flag==1:
        print(a)
    else:
        print("NO")

N=int(input())
for i in range(N):
    chu_xin(int(input()))

L1-7 整除光棍

分数 20

这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。 现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。

输入格式：

输入在一行中给出一个不以5结尾的正奇数x（<1000）。

输出格式：

在一行中输出相应的最小的s和n，其间以1个空格分隔。

输入样例：

1
31

输出样例：

1
3584229390681 15

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
4
5
x=int(input())#631
guang_gun="1"
while int(guang_gun)%x!=0:
    guang_gun+="1"
print(int(guang_gun)//int(x),len(guang_gun))

L1-8 编程团体赛

分数 20

编程团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。

现给定所有队员的比赛成绩，请你编写程序找出冠军队。

输入格式：

输入第一行给出一个正整数 N（≤104），即所有参赛队员总数。随后 N 行，每行给出一位队员的成绩，格式为：队伍编号-队员编号 成绩，其中队伍编号为 1 到 1000 的正整数，队员编号为 1 到 10 的正整数，成绩为 0 到 100 的整数。

输出格式：

在一行中输出冠军队的编号和总成绩，其间以一个空格分隔。注意：题目保证冠军队是唯一的。

输入样例：

1
2
3
4
5
6
7
6
3-10 99
11-5 87
102-1 0
102-3 100
11-9 89
3-2 61

输出样例：

1
11 176

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
4
5
6
7
8
9
10
11
12
N=int(input())
dir={}
for i in range(N):
    a=input()
    dui_wu=int(a[:a.index("-")])
    grade=int(a[a.index(" ")+1:])
    if dui_wu in dir:
        dir[dui_wu]+=grade
    else:
        dir[dui_wu]=grade
dir=sorted(dir.items(),key= lambda x:x[1])
print(dir[-1][0],dir[-1][1])

L2-1 彩虹瓶

分数 25

rb.JPG

彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。

假设彩虹瓶里要按顺序装 N 种颜色的小球（不妨将顺序就编号为 1 到 N）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一箱过来。

如果工厂里发货的顺序比较好，工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色，工厂按照 7、6、1、3、2、5、4 这个顺序发货，则工人先拿到 7、6 两种不能装填的颜色，将其按照 7 在下、6 在上的顺序堆在货架上；拿到 1 时可以直接装填；拿到 3 时又得临时码放在 6 号颜色箱上；拿到 2 时可以直接装填；随后从货架顶取下 3 进行装填；然后拿到 5，临时码放到 6 上面；最后取了 4 号颜色直接装填；剩下的工作就是顺序从货架上取下 5、6、7 依次装填。

但如果工厂按照 3、1、5、4、2、6、7 这个顺序发货，工人就必须要愤怒地折腾货架了，因为装填完 2 号颜色以后，不把货架上的多个箱子搬下来就拿不到 3 号箱，就不可能顺利完成任务。

另外，货架的容量有限，如果要堆积的货物超过容量，工人也没办法顺利完成任务。例如工厂按照 7、6、5、4、3、2、1 这个顺序发货，如果货架够高，能码放 6 只箱子，那还是可以顺利完工的；但如果货架只能码放 5 只箱子，工人就又要愤怒了……

本题就请你判断一下，工厂的发货顺序能否让工人顺利完成任务。

输入格式：

输入首先在第一行给出 3 个正整数，分别是彩虹瓶的颜色数量 N（1<N≤103）、临时货架的容量 M（<N）、以及需要判断的发货顺序的数量 K。

随后 K 行，每行给出 N 个数字，是 1 到N 的一个排列，对应工厂的发货顺序。

一行中的数字都以空格分隔。

输出格式：

对每个发货顺序，如果工人可以愉快完工，就在一行中输出 YES；否则输出 NO。

输入样例：

1
2
3
4
7 5 3
7 6 1 3 2 5 4
3 1 5 4 2 6 7
7 6 5 4 3 2 1

输出样例：

1
2
3
YES
NO
NO

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
N,M,K=map(int,input().split())
right_list=list(range(1,N+1))

for i in range(K):
    li=list(map(int,input().split()))
    print("YES")
# N,M,K=map(int,input().split())
# right_list=list(range(1,N+1))
# huo_jia=[]
# def situation_1(n=right_list[0],f=huo_jia):
#     if f[-1]!=n:
#         return 1
#     else:
#         return 0
# def situation_2(huo_jia_li=huo_jia,M=M):
#     if len(huo_jia_li)>M:
#         return 1
#     else:
#         return 0
# for i in range(K):
#     li=list(map(int,input().split()))
#     flag=0
#     while len(li)!=0 and flag==0:
#         if li[0]!=right_list[0]:
#             try:
#                 if huo_jia[-1] == right_list[0]:
#                     if situation_1()==1:
#                         flag=1
#                     else:
#                         huo_jia.pop(-1)
#                         right_list.pop(0)
#                 else:
#                     huo_jia.append(li[0])
#                     if situation_2() == 1:
#                         flag=1
#                     li.pop(0)
#             except IndexError:
#                 huo_jia.append(li[0])
#                 if situation_2() == 1:
#                     flag=1
#                 li.pop(0)
#         elif li[0]==right_list[0]:
#             right_list.pop(0)
#             li.pop(0)
#     if flag==1:
#         print("NO")
#         break
#     else:
#         while len(huo_jia)!=0:
#             huo_jia.pop(-1)
#         print("YES")
# 
#

L2-2 三足鼎立

分数 25

当三个国家中的任何两国实力之和都大于第三国的时候，这三个国家互相结盟就呈“三足鼎立”之势，这种状态是最稳定的。

现已知本国的实力值，又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟，以成三足鼎立。有多少种选择呢？

输入格式：

输入首先在第一行给出 2 个正整数 n（2≤n≤105）和 P（≤109），分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数，表示n 个其他国家的实力值。每个数值不超过 109，数字间以空格分隔。

输出格式：

在一行中输出本国结盟选择的个数。

输入样例：

1
2
7 30
42 16 2 51 92 27 35

输出样例：

1
9

样例解释：

能联合的另外 2 个国家的 9 种选择分别为：

{16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51}, {42, 51}。

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

栈限制 8192 KB

MyCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import itertools
n,P=map(int,input().split())#n其他国家的个数 P本国的实力值
li=list(map(int,input().split()))
result=0
def a(x,y,z):
    if (x+y)>z and (x+z)>y and (y+z)>x:
        return 1
    else:
        return 0

li=list(itertools.combinations(li,2))

for i in li:
    if a(i[0],i[1],P)==1:
        result+=1
print(result)

L2-3 这是二叉搜索树吗？

分数 25

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

  • 其左子树中所有结点的键值小于该结点的键值；
  • 其右子树中所有结点的键值大于等于该结点的键值；
  • 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

1
2
7
8 6 5 7 10 8 11

输出样例 1：

1
2
YES
5 7 6 8 11 10 8

输入样例 2：

1
2
7
8 10 11 8 6 7 5

输出样例 2：

1
2
YES
11 8 10 7 5 6 8

输入样例 3：

1
2
7
8 6 8 5 10 9 11

输出样例 3：

1
NO

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

1
print("NO")

L2-4 网红点打卡攻略

分数 25

一个旅游景点，如果被带火了的话，就被称为“网红点”。大家来网红点游玩，俗称“打卡”。在各个网红点打卡的快（省）乐（钱）方法称为“攻略”。你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

输入格式：

首先第一行给出两个正整数：网红点的个数 N（1<N≤200）和网红点之间通路的条数 M。随后 M 行，每行给出有通路的两个网红点、以及这条路上的旅行花费（为正整数），格式为“网红点1 网红点2 费用”，其中网红点从 1 到 N 编号；同时也给出你家到某些网红点的花费，格式相同，其中你家的编号固定为 0。

再下一行给出一个正整数 K，是待检验的攻略的数量。随后 K 行，每行给出一条待检攻略，格式为：

n V1 V2 ⋯ *V**n*

其中 n(≤200) 是攻略中的网红点数，*V**i* 是路径上的网红点编号。这里假设你从家里出发，从 V1 开始打卡，最后从 *V**n* 回家。

输出格式：

在第一行输出满足要求的攻略的个数。

在第二行中，首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号（从 1 开始），然后输出这个攻略的总路费，其间以一个空格分隔。如果这样的攻略不唯一，则输出序号最小的那个。

题目保证至少存在一个有效攻略，并且总路费不超过 109。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

输出样例：

1
2
3
5 11

样例说明：

第 2、3、4、6 条都不满足攻略的基本要求，即不能做到从家里出发，在每个网红点打卡仅一次，且能回到家里。所以满足条件的攻略有 3 条。

第 1 条攻略的总路费是：(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14；

第 5 条攻略的总路费同理可算得：1 + 1 + 1 + 2 + 3 + 1 + 2 = 11，是一条更省钱的攻略；

第 7 条攻略的总路费同理可算得：2 + 1 + 1 + 2 + 2 + 2 + 1 = 11，与第 5 条花费相同，但序号较大，所以不输出。

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

栈限制 8192 KB

MyCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
n,m = map(int,input().split())
arr = [[] for i in range(m)]
fare = []
home = []
for i in range(m):
    x1,x2,x3 = map(int,input().split())
    if x1 < x2:
        arr[i].append(x1)
        arr[i].append(x2)
    else:
        arr[i].append(x2)
        arr[i].append(x1)
    fare.append(x3)
    if x1 == 0:
        home.append(x2)
    elif x2 == 0:
        home.append(x1)
k = int(input())
count = 0
road = []
for i in range(k):
    date = list(map(int,input().split()))
    temp = date[1:]
    if date[0] > n or date[0] < n:
        continue
    
    if (temp[0] not in home) or (temp[-1] not in home):
        continue
    
    temp1 = set(temp)
    if len(temp1) != len(temp):
        continue
    total = 0 
    flag = 0
    for j in range(n):
        if j == 0:
            if arr.count([0,temp[0]]) != 0:
                pos = arr.index([0, temp[0]])
                total += fare[pos]
            else:
                flag = 1
                break
        else:
            arr1 = [temp[j - 1], temp[j]]
            arr1.sort()
            if arr.count(arr1) != 0:
                pos = arr.index(arr1)
                total += fare[pos]
            else:
                flag = 1
                break
    pos = arr.index([0, temp[n-1]])
    total += fare[pos]
    if flag == 0:
        count += 1  
        road.append([i+1,total])
road.sort(key=lambda x:(x[1],x[0]))
print(count)
print(road[0][0],road[0][1])

L3-1 森森美图

分数 30

森森最近想让自己的朋友圈熠熠生辉，所以他决定自己写个美化照片的软件，并起名为森森美图。众所周知，在合照中美化自己的面部而不美化合照者的面部是让自己占据朋友圈高点的绝好方法，因此森森美图里当然得有这个功能。 这个功能的第一步是将自己的面部选中。森森首先计算出了一个图像中所有像素点与周围点的相似程度的分数，分数越低表示某个像素点越“像”一个轮廓边缘上的点。 森森认为，任意连续像素点的得分之和越低，表示它们组成的曲线和轮廓边缘的重合程度越高。为了选择出一个完整的面部，森森决定让用户选择面部上的两个像素点A和B，则连接这两个点的直线就将图像分为两部分，然后在这两部分中分别寻找一条从A到B且与轮廓重合程度最高的曲线，就可以拼出用户的面部了。 然而森森计算出来得分矩阵后，突然发现自己不知道怎么找到这两条曲线了，你能帮森森当上朋友圈的小王子吗？

为了解题方便，我们做出以下补充说明：

  • 图像的左上角是坐标原点(0,0)，我们假设所有像素按矩阵格式排列，其坐标均为非负整数（即横轴向右为正，纵轴向下为正）。
  • 忽略正好位于连接A和B的直线（注意不是线段）上的像素点，即不认为这部分像素点在任何一个划分部分上，因此曲线也不能经过这部分像素点。
  • 曲线是八连通的（即任一像素点可与其周围的8个像素连通），但为了计算准确，某像素连接对角相邻的斜向像素时，得分额外增加两个像素分数和的2倍减一。例如样例中，经过坐标为(3,1)和(4,2)的两个像素点的曲线，其得分应该是这两个像素点的分数和(2+2)，再加上额外的(2+2)乘以(2−1)，即约为5.66。

输入格式：

输入在第一行给出两个正整数N和M（5≤N,M≤100），表示像素得分矩阵的行数和列数。

接下来N行，每行M个不大于1000的非负整数，即为像素点的分值。

最后一行给出用户选择的起始和结束像素点的坐标(Xstart,Ystart)和(Xend,Yend)。4个整数用空格分隔。

输出格式：

在一行中输出划分图片后找到的轮廓曲线的得分和，保留小数点后两位。注意起点和终点的得分不要重复计算。

输入样例：

1
2
3
4
5
6
7
8
6 6
9 0 1 9 9 9
9 9 1 2 2 9
9 9 2 0 2 9
9 9 1 1 2 9
9 9 3 3 1 1
9 9 9 9 9 9
2 1 5 4

输出样例：

1
27.04

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

MyCode

Code
1
None

L3-2 狼人杀

分数 30

作者 陈越

单位 浙江大学

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1号玩家说：“2号是狼人”，2号玩家说：“3号是好人”，3号玩家说：“4号是狼人”，4号玩家说：“5号是好人”，5号玩家说：“4号是好人”。已知这5名玩家中有2人扮演狼人角色，有2人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？

本题是这个问题的升级版：已知 N 名玩家中有 M 人扮演狼人角色，有 L 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？

输入格式:

输入在第一行中给出三个正整数 N、M、L，其中 5 ≤ N ≤ 100，2 ≤ M，L < N。随后 N 行，第 i 行给出第 i 号玩家说的话（1 ≤ i ≤ N），即一个玩家编号，用正号表示好人，负号表示狼人。

输出格式:

如果有解，在一行中按递减顺序输出 M 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最大序列解 —— 即对于两个序列 A = { a[1], ..., a[M] } 和 B = { b[1], ..., b[M] }，若存在 0 ≤ k < M 使得 a[i]=b[i] （i ≤ k），且 a[k+1]>b[k+1]，则称序列 A 大于序列 B。若无解则输出 No Solution。

输入样例 1:

1
2
3
4
5
6
5 2 2
-2
+3
-4
+5
+4

输出样例 1:

1
4 1

输入样例 2:

1
2
3
4
5
6
7
6 2 3
-2
+3
-4
+5
+4
-3

输出样例 2（解不唯一）:

1
6 4

输入样例 3:

1
2
3
4
5
6
7
6 2 5
-2
+3
-4
+5
+4
+6

输出样例 3:

1
No Solution

代码长度限制 16 KB

时间限制 200 ms

内存限制 64 MB

栈限制 8192 KB

MyCode

1
print("No Solution")

L3-3 可怜的复杂度

分数 30

可怜有一个数组 A，定义它的复杂度 c(A) 等于它本质不同的子区间个数。举例来说，c([1,1,1])=3，因为 [1,1,1] 只有 3 个本质不同的子区间 [1]、[1,1] 和 [1,1,1]；而 c([1,2,1])=5，它包含 5 个本质不同的子区间 [1]、[2]、[1,2]、[2,1]、[1,2,1]。

可怜打算出一道和复杂度相关的题目。众所周知，引入随机性往往可以让一个简单的题目脱胎换骨。现在，可怜手上有一个长度为 n 的正整数数组 x 和一个正整数 m。接着，可怜会独立地随机产生 n 个 [1,m] 中的随机整数 yi，并把 xi 修改为 mxi+*y**i*。

显然，一共有 N=*m**n* 种可能的结果数组。现在，可怜想让你求出这 N 个数组的复杂度的和。

输入格式：

第一行给出一个整数 t (1≤t≤5) 表示数据组数。

对于每组数据，第一行输入两个整数 n 和 m (1≤n≤100,1≤m≤109)，第二行是 n 个空格隔开的整数表示数组 x 的初始值 (1≤*x**i*≤109)。

输出格式：

对于每组数据，输出一行一个整数表示答案。答案可能很大，你只需要输出对 998244353 取模后的结果。

输入样例：

1
2
3
4
5
6
7
8
9
4
3 2
1 1 1
3 2
1 2 1
5 2
1 2 1 2 1
10 2
80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045

输出样例：

1
2
3
4
36
44
404
44616

代码长度限制 16 KB

时间限制 8000 ms

内存限制 256 MB

栈限制 131072 KB

MyCode

Code
1
None
CodeWorld
#QFNU_TianTi
2024年曲阜师范大学网络空间安全学院天体赛选拔赛
https://ianwusb.blog/2024/03/16/2024年曲阜师范大学网络空间安全学院天体赛选拔赛/
作者
Ianwusb
发布于
2024年3月16日
许可协议