【题目描述】
小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：
1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；
2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。
【输入】
输入第一行包含两个整数n，k（k+1≤n）。
第二行包含n
很套路的一道题，做过无限之环来看这道题还是十分好想的因为我比较菜，考试的时候就没能想出来。按照套路，把格子黑白染色，然后考虑图的特点，到一个地方一定拐弯。并且，对于一条回路来说，正向和反向的贡献都是一样的。接下来，我们指定黑、白格子的流向，考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了，我们规定黑格子横进竖出，白格子横出竖进。这样我们把问题抽象成一张图，对于每一个格子可以选择从进向自己连边，自己向出连边，相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件，一个点只能经过一条流量，也就是出入度都是1，想到限制出入度便想到了最小路劲覆盖的模型。于是，初步的构图便完成了。
Description在Byteland一共有n个城市，编号依次为1到n，它们之间计划修建n(n-1)/2条单向道路，对于任意两个不同的点i和 j，在它们之间有且仅有一条单向道路，方向要么是i到j，要么是j到i。换句话说，这是一个n个点的竞赛图。Byte asar居住在1号城市，他希望从1号城市出发，沿着单向道路不重复地访问一些城市，使得访问的城市数尽可能多。 请写一个程序，帮助Byteasar计算有多少种道路修建方式，使得从1号点出发的最长简单路径经过点数恰好为k，由 于答案可能很大，请对P取模输出 Input第一行包含两个正整数n,P，表示点数和模数。 2≤P≤1e9,N<=200
Description在Byteland 一共有n 座城市，编号依次为1 到n，这些城市之间通过m 条单向公路连接。对于两座不同的城市a 和 b，如果a 能通过这些单向道路直接或间接到达b，且b 也能如此到达a，那么它们就会被认为是一对友好城市。Byt eland 的交通系统十分特殊，第i 天只有编号在[li, ri] 的单向公路允许通行，请写一个程序，计算每天友好城 市的对数。 注意：(a, b) 与(b, a) 没有区别。 Input第一行包含三个正整数n, m, q，分别表示城市的个数、单向公路的条数以及询问的天数。 接下来m 行，每行两个正整数ui, vi，表示一条从城
Description在Byteland一共有n个城市，编号依次为1到n，它们之间计划修建m条双向道路，其中修建第i条道路的费用为ci。B yteasar作为Byteland公路建设项目的总工程师，他决定选定一个区间[l,r]，仅使用编号在该区间内的道路。他希 望选择一些道路去修建，使得连通块的个数尽量少，同时，他不喜欢修建多余的道路，因此每个连通块都可以看成 一棵树的结构。为了选出最佳的区间， Byteasar会不断选择 q个区间，请写一个程序，帮助 Byteasar计算每个区 间内修建公路的最小总费用。 Input第一行包含三个正整数n; m; q，表示城市数、道路数和询问数
Description在 Byteland一共开着 n家商店，编号依次为 1到 n，其中编号为1到 m的商店有日消费量上限，第 i家商店的日消 费量上限为wi。Byteasar每次购物的过程是这样的：依次经过每家商店，然后购买非负整数价格的商品，并在结账 的时候在账本上写上在这家商店消费了多少钱。当然，他在这家商店也可以什么都不买，然后在账本上写上一个0 。这一天， Byteasar日常完成了一次购物，但是他不慎遗失了他的账本。他只记得自己这一天一共消费了多少钱 ，请写一个程序，帮助 Byteasar计算有多少种可能的账单。 Input第一行包含三个正整数
DescriptionByteasar 组建了一支舰队！他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图，其中有些位置是“ .”，表示这一格是海水，可以通过；有些位置是“#”，表示这一格是礁石，不可以通过；有些位置是“o”，表 示这一格目前有一艘舰，且舰离开这一格之后，这一格将变为“.”。这些“o” 表示Byteasar 的舰队，他们每天 可以往上下左右中的一个方向移动一格，但不能有任何一艘舰驶出地图。特别地，Byteasar 对阵形有所研究，所 以他不希望在航行的过程中改变阵形，即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以 航行无限长的时间，每当一艘
【题目描述】兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。 【输入】两行两个字符串，分别代表S和T 【输出】第一行一个正整数k，表示T在S中出现了几次 接下来k行正整数，分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出，S下标从0开始。 【输入样例】bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab
a?aba?abba 【输出样例】
Description T国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。 在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。 辛运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。 Input 输入的第一行包含整数N。 接下来N行，每行N个实数，第i+l行，列的数G[i][j]表示城市i与j
【题目描述】给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节点的颜色为c[i]。如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。 每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序，快速回答这些询问。 【输入】第一行包含一个正整数T(1<=T<=500)，表示测试数据的组数。 每组数据中，第
Rockdu's Blog