网站建设哪个公司,江岸区建设局网站,怎么建商业网站,搜索引擎优化方法有哪些目录 2023年度第四届全国大学生算法设计与编程挑战赛#xff08;春季赛#xff09;1、A2、Bx3、Cut4、Diff5、EchoN6、Farmer7、GcdGame8、HouseSub9、IMissYou!10、Jargonless 2023年度第四届全国大学生算法设计与编程挑战赛#xff08;春季赛#xff09;
1、A
题目描述… 目录 2023年度第四届全国大学生算法设计与编程挑战赛春季赛1、A2、Bx3、Cut4、Diff5、EchoN6、Farmer7、GcdGame8、HouseSub9、IMissYou!10、Jargonless 2023年度第四届全国大学生算法设计与编程挑战赛春季赛
1、A
题目描述
有一个长为n(1≤n≤1000) 的序列序列上的元素两两不同。你需要用最少的操作步数翻转这个序列。
每次操作你需要给出三个数 i,j,k(1≤i≤jk≤n)交换序列中下标属于 [[i,j] 的元素与下标属于[j1,k] 的元素。例如对于长为 7 的序列 1,2,3,4,5,6,7进行操作i2,j4,k6 后序列会变为 1,5,6,2,3,4,7。
给定 n你需要输出最少的操作步数并输出每一步的具体操作。保证对于所有输入的 n均存在至少一个有限步内的合法操作。
输入
一行一个整数 n。
3输出
2
1 1 3
1 1 2第一行一个非负整数 m表示最少的操作步数。
接下来 m 行每行三个整数 i,j,k表示进行题目中描述的操作。
要求 1≤i,j,k≤n,i≤jk。
你的输出必须保证从上到下执行这 m* 次操作后整个序列被翻转。
代码
#todo2、Bx
题目描述
你有一个长度为 n (2≤n≤106) 的 01 序列你可以执行如下操作若干遍
每次操作可以选择一个正整数 i满足 1≤i≤n−k1然后选中[i,ik−1] 这个长度为k (2≤k≤n) 的区间设这个区间当前的数的最大值为 x*然后将这个区间中所有的数变成 x。
一个操作序列 i1,i2,⋯,im 是好的当且仅当依次进行这些操作后整个序列的数都变成 1。
你需要给出一个好的操作序列使得这个操作序列的长度最小且满足此情况下操作序列的字典序最小。
输入
第一行一个整数 T1≤T≤105表示数据组数。
对于每组数据第一行两个整数n,k。
第二行一个长度为 n 的01字符串表示这个序列。数据保证序列中至少有一个 1和一个 0。
数据保证 ∑n≤106。
2
5 3
00010
6 4
100001输出
2
3 1
2
1 2对于每组数据输出两行第一行一个整数 m表示最短的操作次数。
第二行 m 个整数表示这个操作序列中间用空格分隔开。
代码
#todo3、Cut
题目描述
我们可以对数字进行一些有趣的游戏比如把数字全部切开又能变成多少
你现在随意地写下了一个数字n (1≤n1010)你现在可以任意多次从任意位置切开这个数字随后将切开的数字加起来得到一个结果。
你现在想知道所有可能的切法结果的和是多少。
输入
输入一行一个整数 n表示一开始写下的数字。
125输出
176对于样例给出的数字 125有以下几种切法的可能
12512526125171258
故算式结果的和为 12526178176。
代码
s input()li []
lis []
#简单的回溯
def dfs(s):if len(s) 1:lis.append(li.copy())returnif len(s) 1:li.append(s)lis.append(li.copy())li.pop()returnfor i in range(1, len(s)1):li.append(s[0:i])dfs(s[i:len(s)])li.pop()dfs(s)
res 0
for i in lis:for j in i:res int(j)
print(res)4、Diff
题目描述
作为一个居家小能手你深知收纳之道。
至少同一种东西不要放在一起因为同样的东西放在一起容易分不出来……。
现在有n (1≤n≤1000) 个盒子你现在有 k (2≤k≤1000) 种物品每种物品的数量有无限个。你现在要在每个盒子里都放一个物品同时你不想相邻的位置上摆同样的东西。
想请问有多少种摆放方式可以满足你的要求。
输入
输入一行两个整数 n、k表示盒子的数量和物品种类的数量。
3 2输出
2输出一行一个整数表示方案数数据保证答案在 int 范围内。
代码
n, m map(int, input().split())#简单的数学问题
res 1
res * m
for i in range(n-1):res * (m-1)print(res)5、EchoN
题目描述
人类的本质是复读机就是说人类人类的本质是一些东西……人类的本质是什么人类的本质是复读人类的本质是复读机。
给定一个字符串 S (∣S∣⩽106)如果其中某一个子串是 S 的前缀那么我们就说存在一次复读。
想请问一共有多少次复读。
输入
一行一个字符串 S。
aaba输出
6一行一个整数表示复读次数。
代码
s input()res len(s)
for i in range(1, len(s)):start 0while ilen(s)-1 and s[i] s[start]:res 1i 1start 1
print(res)6、Farmer
题目描述
不同的人对于不同的教育方法的接受程度是不一样的不同的树对于不同的肥料的吸收程度也是不一样的。路边现在种着一排的树作为新时代新青年的你当然有义务来做些什么你的手里提着各式各样的化肥。“怎么样才能够成为一个优秀的农民呢”年纪轻轻的你已经立下了成为农民的远大志向。“这些树要好好施肥才能茁壮成长啊。”
路边有 n (2⩽n⩽5×103) 棵树编号从 1 到 n其中第 i 棵树和第 i1 棵树之间的距离是 Ai (1⩽Ai⩽109)。现在手上有 m (1⩽m⩽200) 袋肥料对第 i棵树使用第 j 袋肥料可以获得 Bi,j(1⩽ Bi,j⩽109) 的收益。每一袋肥料只能用在一棵树上但是一棵树可以用很多袋肥料。
现在定义满意度为得到的收益减去走过的距离即 ∑B−∑A如果你可以从任何一棵树开始走请问你能得到的最大满意度为多少
需要注意:
1. 你可以按照任意顺序使用化肥可以先某棵树使用第1、3、5袋化肥再前往另一棵树使用第2、4袋化肥
2. 你可以在树与树之间任意走动即可任意往返
输入
第一行两个整数 n、m表示树的数量和肥料的数量。
接下来一行n−1 个整数 A1,A2,…An−1表示树之间的距离。
接下来 n行每行 m 个整数Bij表示每袋肥料的收益。
3 4
1 4
2 2 5 1
1 3 3 2
2 2 5 1输出
11输出一行一个整数表示最大满意度。
代码
#todo7、GcdGame
题目描述
有一个长为n (1≤n≤105)的正整数序列第i个数为ai (2≤ai≤108)。你在这个序列上进行q (1≤q≤105)轮单人游戏每轮游戏之间相互独立。
在一轮游戏中你有两个棋子初始放在序列的第x个位置和第y个位置(1≤x,y≤n)棋子有权值初始分别为ax和ay。你的目标是让这两个棋子上的权值不互质。每一步你可以选择一枚棋子将其移动到序列上相邻的一个位置即从第i个位置移动到第i−1或第i1个位置同时这个棋子上的权值会乘上ai−1或ai1。注意第1个位置只能移动到第2个位置第n个位置只能移动到第n−1个位置。
对于这q轮游戏请输出每轮游戏达成目标的最小操作步数。
输入
第一行两个正整数n,q分别表示序列长度和询问次数。
第二行n个正整数第i个数表示ai的值。
接下来q行每行两个正整数x,y表示一轮游戏的初始状态。
6 4
2 9 5 7 4 3
4 1
2 6
3 4
5 2 输出
1
0
1
1q行每行一个整数第i行的整数表示第i次询问的答案。
代码
#todo8、HouseSub
题目描述
一个图称之为“房子”当且仅当这个图是这样的 有一个 n (5≤n≤105) 个点 m (5≤m≤105) 条边的无向图小L想找到 5 个不同的点并满足这 5 个点能构成一个房子。但对于这 5 个点下方的四元环必须是“纯四元环”。也就是说不能出现以下几种情况 需要注意的是以下情况是合法的因为下方的四元环不相邻的两个点对间没有边相连 具体地设这 5 个互不相同的点为u1,u2,u3,u4,u5小L 想找到满足 u1u2 且(u1,u2),(u1,u3),(u2,u3),(u1,u4),(u4,u5),(u5,u2) 间有边相连但 (u1,u5) 和(u2,u4) 间不存在边相连的(u1,u2,u3,u4,u5) 五元组的方案数。
输入
第一行一个整数 T表示数据组数。
对于每组数据第一行两个整数n,m 表示无向图的点数和边数。
第2∼(m1) 行每行两个整数 x,y1≤x,y≤n,x!y表示无向图中的一条边。
保证无向图不存在重边或自环。保证 1≤∑n,∑m≤105。
5 6
1 2
1 3
2 3
1 4
4 5
2 5输出
1一行一个整数表示方案数对 998244353998244353 取模后的结果。
代码
#todo9、IMissYou!
题目描述
作为一个离家千里的大学生夜深时你总会思念你的家人。
为了科学研究深夜思念的规律你记录了这一周内每天的思念值ai (∣ai∣≤100)你想知道这一周内你有多思念家人。如果你的思念值之和严格大于0则代表思念家人反之则不思念。
在思念时请输出’IMissYou!‘并给出总思念值反之则单独输出’OvO’。输出时均不包含单引号。
输入
第一行七个正整数 ai意义如上所述。
5 5 5 5 5 -2 -2输出
IMissYou!
21一行或两行表示答案。
代码
li input().split()sum1 0
for i in li:sum1 int(i)if sum1 0:print(IMissYou!)print(sum1)
else:print(OvO)10、Jargonless
题目描述
很多人一些话翻来覆去说得没有任何营养有用信息就一点点……如果可以不用废话文学请不要使用废话文学。
给定一个原始文本字符串 S (∣S∣≤3×105) 和一个有用信息字符串 T (∣T∣≤200)现在可以对 S 进行精简操作具体来说就是可以将 S 的开头和结尾分别去掉一段使得剩下的字符串 ′S′ 中包含有有用信息 T*。
请问有多少种精简 S 的方式
注意′S′包含T指的是T*是′S′的子序列如’aacbac’包含’abc’。
输入
第一行一个字符串 S*表示原始的文本。
第二行一个字符串 T*表示有用的信息。
abcabcabc
cba输出
9输出一行一个整数表示精简 S 的方案数。
代码
s input()
t input()def conTains(s, t):index1 0for i in s:if index1 len(t) and t[index1] i:index1 1if index1 len(t):return Trueelse:return Falseres 0
l 0
r 0while conTains(s[l:], t):r 1res 1while conTains(s[l:len(s) - r], t):# print(fleft:{l}, right:{r})res 1r 1l 1print(res)
