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

复制

21 1 31 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

复制

25 3000106 4100001

样例输出1

复制

23 121 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改变而改变returnif 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()returnfor 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这题排列组合，可以通过规律找到排列组合的公式，也可以dfs1.公式第一个盒子有k种选取方式，因为不可以与上一个盒子内的东西相同，所以有k-1种，之后的盒子也是如此所以有k*(k-1)*……*(k-1)中间为(n-1)个(k-1)即k*(k-1)**(n-1)2.dfs搜索每一个物品的分支例如A / \B C /\ /\CA ABBCD以此类推*/#include #include #include 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 > 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表示前缀的末尾，初始为0while i<=len(s)-1 and s[i] == s[start]:res += 1i += 1start += 1print(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 42 2 5 11 3 3 22 2 5 1

样例输出1

复制

11

样例输入2

复制

5 3 1 2 3 4 10 1 1 1 1 11 10 1 1 1 11 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 42 9 5 7 4 34 12 63 45 2

样例输出1

复制

1011
//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 61 21 32 31 44 52 5

样例输出1

复制

1

样例输入2

复制

5 81 21 32 31 44 52 51 52 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

复制

abcabcabccba

样例输出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

开头除去 2 个，结尾除去 2 个：cabca

//todo