A
题目描述
有一个长为 n\ (1\le n \le 1000)n (1≤n≤1000) 的序列,序列上的元素两两不同。你需要用最少的操作步数翻转这个序列。
每次操作你需要给出三个数 i,j,k(1\le i\le j < k \le n)i,j,k(1≤i≤j<k≤n),交换序列中下标属于 [i,j][i,j] 的元素与下标属于 [j+1,k][j+1,k] 的元素。例如:对于长为 77 的序列 {1,2,3,4,5,6,7}1,2,3,4,5,6,7,进行操作 i=2,j=4,k=6i=2,j=4,k=6 后序列会变为 {1,5,6,2,3,4,7}1,5,6,2,3,4,7。
给定 nn,你需要输出最少的操作步数,并输出每一步的具体操作。保证对于所有输入的 nn,均存在至少一个有限步内的合法操作。
输入
一行,一个整数 nn。
输出
第一行一个非负整数 mm,表示最少的操作步数。
接下来 mm 行,每行三个整数 i,j,ki,j,k,表示进行题目中描述的操作。
要求 1\le i,j,k \le n,i\le j < k1≤i,j,k≤n,i≤j<k。
你的输出必须保证从上到下执行这 mm 次操作后,整个序列被翻转。
样例输入1
复制
3样例输出1
复制
2 1 1 3 1 1 2提示
假设这个序列初始为 {1,2,3}1,2,3。
第一步: i=1,j=1,k=3i=1,j=1,k=3,交换 [1,1][1,1] 与 [2,3][2,3] 得到序列 {2,3,1}2,3,1;
第二步: i=1,j=1,k=2i=1,j=1,k=2,交换 [1,1][1,1] 与 [2,2][2,2] 得到序列 {3,2,1}3,2,1。
可以证明最少需要两步才能翻转长为 33 的序列。
#todo
B
题目描述
你有一个长度为 n\ (2 \le n\le 10^6)n (2≤n≤106) 的 01 序列,你可以执行如下操作若干遍:
每次操作可以选择一个正整数 ii,满足 1\le i\le n-k+11≤i≤n−k+1,然后选中 [i,i+k-1][i,i+k−1] 这个长度为 k\ (2 \le k\le n)k (2≤k≤n) 的区间,设这个区间当前的数的最大值为 xx,然后将这个区间中所有的数变成 xx。
一个操作序列 i_1,i_2,\cdots,i_mi1,i2,⋯,im 是好的当且仅当依次进行这些操作后,整个序列的数都变成 11。
你需要给出一个好的操作序列,使得这个操作序列的长度最小,且满足此情况下,操作序列的字典序最小。
输入
第一行一个整数 TT(1\le T \le 10^51≤T≤105),表示数据组数。
对于每组数据:第一行两个整数 n,kn,k。
第二行一个长度为 nn 的01字符串,表示这个序列。数据保证序列中至少有一个 11 和一个 00。
数据保证 \sum n \le 10^6∑n≤106。
输出
对于每组数据,输出两行:第一行一个整数 mm,表示最短的操作次数。
第二行 mm 个整数,表示这个操作序列,中间用空格分隔开。
样例输入1
复制
2 5 3 00010 6 4 100001样例输出1
复制
2 3 1 2 1 2
//todo
C
题目描述
我们可以对数字进行一些有趣的游戏,比如,把数字全部切开又能变成多少?
你现在随意地写下了一个数字 n\ (1\leq n<10^{10})n (1≤n<1010),你现在可以任意多次从任意位置切开这个数字,随后将切开的数字加起来,得到一个结果。
你现在想知道所有可能的切法结果的和是多少。
输入
输入一行一个整数 nn,表示一开始写下的数字。
输出
输出一行一个整数,表示算式结果的和。
样例输入1
复制
125样例输出1
复制
176提示
对于样例给出的数字 125125,有以下几种切法的可能:
- 125125
- 1 + 25 = 261+25=26
- 12 + 5 = 1712+5=17
- 1 + 2 + 5 = 81+2+5=8
故算式结果的和为 125 + 26 + 17 + 8 = 176125+26+17+8=176。
"""
CUT
这道题采用dfs按切割长度搜出来每一种的切割方案
"""
n=input()
ls=[] #作为dfs里的迭代变量,因为会随着递归而改变
bc=[] #用来保存数据
def dfs(s):
if len(s)<1:
bc.append(ls.copy()) #在python里赋值会让两个变量指向同一个内存地址,所以如果采取赋值的操作,bc会因ls改变而改变
return
if len(s)==1:
ls.append(s)
bc.append(ls.copy()) #回溯最重要的一点,怎么来的怎么回去,在line22进行dfs(5)之前,此时的ls=['1','2'],在dfs(5),的时候会因为len(s)==1而改变为ls=['1','2','5'],所以要进行删除操作
ls.pop()
return
for i in range(1,len(s)+1):
ls.append(s[0:i])
dfs(s[i:len(s)])
ls.pop()
dfs(n)
ans=0
#最后将bc保存的值相加
for i in bc:
for j in i:
ans+=int(j)
print(ans)
D
题目描述
作为一个居家小能手,你深知收纳之道。
至少,同一种东西不要放在一起,因为同样的东西放在一起容易分不出来……。
现在有 n\ (1\leq n\leq1000)n (1≤n≤1000) 个盒子,你现在有 k\ (2\leq k\leq1000)k (2≤k≤1000) 种物品,每种物品的数量有无限个。你现在要在每个盒子里都放一个物品,同时,你不想相邻的位置上摆同样的东西。
想请问有多少种摆放方式可以满足你的要求。
输入
输入一行两个整数 nn、kk,表示盒子的数量和物品种类的数量。
输出
输出一行一个整数,表示方案数,数据保证答案在 int 范围内。
样例输入1
复制
3 2样例输出1
复制
2样例输入2
复制
1 8样例输出2
复制
8提示
对于第一个样例,我们假设两种物品分别为 A 和 B,则可行的方案有且仅有 2 种:
- ABA
- BAB
/*
Diff
这题排列组合,可以通过规律找到排列组合的公式,也可以dfs
1.公式
第一个盒子有k种选取方式,因为不可以与上一个盒子内的东西相同,所以有k-1种,之后的盒子也是如此
所以有k*(k-1)*……*(k-1)中间为(n-1)个(k-1)
即k*(k-1)**(n-1)
2.dfs
搜索每一个物品的分支
例如
A
/ \
B C
/\ /\
C A A B
BCD以此类推
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, k, ans;
void dfs(int u, int cnt)
{
if (cnt == n) // 当数量==n时回溯
{
ans++;
return;
}
for (int i = 1; i <= k; i++)
{
if (i != u) // 只有下一件物品与上一件不同时才往下一层递归
dfs(i, cnt + 1);
}
}
int main()
{
cin >> n >> k;
// 搜索每一个物品的分支
for (int i = 1; i <= k; i++)
dfs(i, 1);
cout << ans << endl;
}
E
题目描述
人类的本质是复读机,就是说,人类,人类的本质,是一些东西……人类的本质是什么?人类的本质是复读,人类的本质是复读机。
给定一个字符串 S\ (|S| \leqslant 10^6)S (∣S∣⩽106),如果其中某一个子串是 SS 的前缀,那么我们就说存在一次复读。
想请问一共有多少次复读。
输入
一行一个字符串 SS。
输出
一行一个整数,表示复读次数。
样例输入1
复制
aaba样例输出1
复制
6样例输入2
复制
niconiconi样例输出2
复制
18提示
对于第一个样例,复读的片段分别为:
[1, 1]:\ a[1,1]: a
[1, 2]:\ aa[1,2]: aa
[1, 3]:\ aab[1,3]: aab
[1, 4]:\ aaba[1,4]: aaba
[2, 2]:\ a[2,2]: a
[4, 4]:\ a[4,4]: a
"""
EchoN
可以采取kmp,也可以采取双指针
"""
s = input()
res = len(s)
#因为要求前缀,那么aaba也就是从开始一直到结尾,从长度为1到len(s),都是aaba的前缀
# [1, 1]:a
# [1, 2]:aa
# [1, 3]:aab
# [1, 4]:aaba
#下面这个操作是为了求字符串中间是否存在有相同的前缀
#以niconiconi为例
#在i==4即s[4]=n之前while一直处于不成立状态,当i==4时,n==s[start],所以res+1,i也+1,这是为了继续匹配看后面还有多少相同的前缀,
# 当不再匹配的时候,for从此时的i继续进行循环,因为之前的情况都已排查好了,所以继续往后搜就可以了
for i in range(1, len(s)):
start = 0 #start表示前缀的末尾,初始为0
while i<=len(s)-1 and s[i] == s[start]:
res += 1
i += 1
start += 1
print(res)
F
题目描述
不同的人对于不同的教育方法的接受程度是不一样的,不同的树对于不同的肥料的吸收程度也是不一样的。路边现在种着一排的树,作为新时代新青年的你当然有义务来做些什么,你的手里提着各式各样的化肥。“怎么样才能够成为一个优秀的农民呢?”年纪轻轻的你已经立下了成为农民的远大志向。“这些树,要好好施肥才能茁壮成长啊。”
路边有 n\ (2 \leqslant n \leqslant 5 \times 10^3)n (2⩽n⩽5×103) 棵树,编号从 1 到 n,其中第 ii 棵树和第 i + 1i+1 棵树之间的距离是 A_{i}\ (1 \leqslant A_{i} \leqslant 10^9)Ai (1⩽Ai⩽109)。现在手上有 m\ (1 \leqslant m \leqslant 200)m (1⩽m⩽200) 袋肥料,对第 ii 棵树使用第 jj 袋肥料可以获得 B_{i, j}\ (1 \leqslant B_{i, j} \leqslant 10^9)Bi,j (1⩽ Bi,j⩽109) 的收益。每一袋肥料只能用在一棵树上,但是一棵树可以用很多袋肥料。
现在定义满意度为得到的收益减去走过的距离,即 \sum B - \sum A∑B−∑A,如果你可以从任何一棵树开始走,请问你能得到的最大满意度为多少?
需要注意:
1. 你可以按照任意顺序使用化肥,可以先某棵树使用第1、3、5袋化肥,再前往另一棵树使用第2、4袋化肥
2. 你可以在树与树之间任意走动,即可任意往返
输入
第一行两个整数 nn、mm,表示树的数量和肥料的数量。
接下来一行 n - 1n−1 个整数 A_{1}, A_{2}, \dots A_{n - 1}A1,A2,…An−1,表示树之间的距离。
接下来 nn 行,每行 mm 个整数 B_{i, j}Bi,j,表示每袋肥料的收益。
输出
输出一行一个整数,表示最大满意度。
样例输入1
复制
3 4 1 4 2 2 5 1 1 3 3 2 2 2 5 1样例输出1
复制
11样例输入2
复制
5 3 1 2 3 4 10 1 1 1 1 1 1 10 1 1 1 1 1 1 10样例输出2
复制
20提示
对于第一个样例,最大满意度的策略如下:
从第 1 棵树出发,使用第 1 和第 3 袋肥料,获得满意度 B_{1, 1} + B_{1, 3} = 2 + 5 = 7B1,1+B1,3=2+5=7
走到第 2 棵树,使用第 2 和第 4 袋肥料,获得满意度 B_{2, 2} + B_{2, 4} - A_{1} = 3 + 2 - 1 = 4B2,2+B2,4−A1=3+2−1=4
最终总共的满意度为 7 + 4 = 117+4=11
//todo
G
题目描述
有一个长为n\ (1\le n \le 10^5)n (1≤n≤105)的正整数序列,第ii个数为a_i\ (2\le a_i \le 10^8)ai (2≤ai≤108)。你在这个序列上进行q\ (1\le q \le 10^5)q (1≤q≤105)轮单人游戏,每轮游戏之间相互独立。
在一轮游戏中,你有两个棋子,初始放在序列的第xx个位置和第yy个位置\ (1\le x,y \le n) (1≤x,y≤n);棋子有权值,初始分别为a_xax和a_yay。你的目标是让这两个棋子上的权值不互质。每一步,你可以选择一枚棋子,将其移动到序列上相邻的一个位置,即从第ii个位置移动到第i-1i−1或第i+1i+1个位置,同时这个棋子上的权值会乘上a_{i-1}ai−1或a_{i+1}ai+1。注意,第11个位置只能移动到第22个位置,第nn个位置只能移动到第n-1n−1个位置。
对于这qq轮游戏,请输出每轮游戏达成目标的最小操作步数。
输入
第一行,两个正整数n,qn,q,分别表示序列长度和询问次数。
第二行,nn个正整数,第ii个数表示a_iai的值。
接下来qq行,每行两个正整数x,yx,y,表示一轮游戏的初始状态。
输出
qq行,每行一个整数,第ii行的整数表示第ii次询问的答案。
样例输入1
复制
6 4 2 9 5 7 4 3 4 1 2 6 3 4 5 2样例输出1
复制
1 0 1 1
//todo
H
题目描述
一个图称之为“房子”当且仅当这个图是这样的:
有一个 n\ (5\le n\le 10^5)n (5≤n≤105) 个点 m\ (5\le m\le 10^5)m (5≤m≤105) 条边的无向图,小L想找到 55 个不同的点,并满足这 55 个点能构成一个房子。但对于这 55 个点,下方的四元环必须是“纯四元环”。也就是说,不能出现以下几种情况:
需要注意的是,以下情况是合法的,因为下方的四元环不相邻的两个点对间没有边相连:
具体地,设这 55 个互不相同的点为 u_1,u_2,u_3,u_4,u_5u1,u2,u3,u4,u5,小L 想找到满足 u_1 < u_2u1<u2 且 (u_1,u_2),(u_1,u_3),(u_2,u_3),(u_1,u_4),(u_4,u_5),(u_5,u_2)(u1,u2),(u1,u3),(u2,u3),(u1,u4),(u4,u5),(u5,u2) 间有边相连,但 (u_1,u_5)(u1,u5) 和 (u_2,u_4)(u2,u4) 间不存在边相连的, (u_1,u_2,u_3,u_4,u_5)(u1,u2,u3,u4,u5) 五元组的方案数。
输入
第一行一个整数 TT,表示数据组数。
对于每组数据:第一行两个整数 n,mn,m ,表示无向图的点数和边数。
第 2\sim (m+1)2∼(m+1) 行,每行两个整数 x,yx,y(1\le x, y \le n, x\neq y1≤x,y≤n,x=y),表示无向图中的一条边。
保证无向图不存在重边或自环。保证 1\le \sum n,\sum m\le 10^51≤∑n,∑m≤105。
输出
一行一个整数,表示方案数对 998244353998244353 取模后的结果。
样例输入1
复制
5 6 1 2 1 3 2 3 1 4 4 5 2 5样例输出1
复制
1样例输入2
复制
5 8 1 2 1 3 2 3 1 4 4 5 2 5 1 5 2 4样例输出2
复制
0提示
对于样例1,(1,2,3,4,5)(1,2,3,4,5) 满足条件。
//todo
I
题目描述
作为一个离家千里的大学生,夜深时你总会思念你的家人。
为了科学研究深夜思念的规律,你记录了这一周内每天的思念值 a_i\ (|a_i| \leq 100)ai (∣ai∣≤100),你想知道这一周内你有多思念家人。如果你的思念值之和严格大于0,则代表思念家人,反之则不思念。
在思念时请输出'IMissYou!',并给出总思念值,反之则单独输出'OvO'。(输出时均不包含单引号)
输入
第一行七个正整数 a_iai,意义如上所述。
输出
一行或两行,表示答案。
样例输入1
复制
5 5 5 5 5 -2 -2样例输出1
复制
IMissYou! 21样例输入2
复制
5 5 5 5 5 -20 -20样例输出2
复制
OvO提示
- 样例1:数值总和大于0,输出'IMissYou!'及数值。
- 样例2:数值总和不大于0,输出'OvO'。
a = list(map(int, input().split()))
s = sum(a)
if s > 0:
print("IMissYou!")
print(s)
else:
print("0v0")
J
题目描述
很多人一些话翻来覆去说得没有任何营养,有用信息就一点点……如果可以不用废话文学,请不要使用废话文学。
给定一个原始文本字符串 S\ (|S|\leq 3\times 10^5)S (∣S∣≤3×105) 和一个有用信息字符串 T\ (|T|\leq 200)T (∣T∣≤200),现在可以对 SS 进行精简操作,具体来说,就是可以将 SS 的开头和结尾分别去掉一段,使得剩下的字符串 S'S′ 中包含有有用信息 TT。
请问有多少种精简 SS 的方式?
注意:“S'S′包含TT”指的是TT是S'S′的子序列,如'aacbac'包含'abc'。
输入
第一行一个字符串 SS,表示原始的文本。
第二行一个字符串 TT,表示有用的信息。
输出
输出一行一个整数,表示精简 SS 的方案数。
样例输入1
复制
abcabcabc cba样例输出1
复制
9提示
精简 SS 的 9 种方案分别为:
开头除去 0 个,结尾除去 0 个:abcabcabc
开头除去 0 个,结尾除去 1 个:abcabcab
开头除去 0 个,结尾除去 2 个:abcabca
开头除去 1 个,结尾除去 0 个:bcabcabc
开头除去 1 个,结尾除去 1 个:bcabcab
开头除去 1 个,结尾除去 2 个:bcabca
开头除去 2 个,结尾除去 0 个:cabcabc
开头除去 2 个,结尾除去 1 个:cabcab文章来源:https://www.toymoban.com/news/detail-474353.html
开头除去 2 个,结尾除去 2 个:cabca文章来源地址https://www.toymoban.com/news/detail-474353.html
//todo
到了这里,关于2023年度第四届全国大学生算法设计与编程挑战赛(春季赛)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!