一、实操题
1、Emiya家今天的饭
【题目描述】
Emiya 是个擅长做菜的高中生，他共掌握 n 种烹饪方法，且会使用 m 种主要食材做菜。为了方便叙述，我们对烹饪方法从 1~n 编号，对主要食材从 1 ~m 编号。
Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 ai,j 道不同的使用烹饪方法 i 和主要食材 j 的菜（1 ≤i≤n,1≤j≤m），这也意味着 Emiya 总共会做
道不同的菜。
Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 k 道菜的搭配方案而言：
（1）Emiya 不会让大家饿肚子，所以将做至少一道菜，即 k≥1
（2）Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同
（3）Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即
道菜）中被使用
这里的⌊x⌋ 为下取整函数，表示不超过 x 的最大整数。
这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。
Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数998,244,353 取模的结果。
【输入格式】
从文件meal.in中读入数据。
第 1 行两个用单个空格隔开的整数 n,m。
第 2 行至第 n+1 行，每行 m 个用单个空格隔开的整数，其中第 i + 1行的 m 个数依次为 ai,1,ai,2,⋯,ai,m。
【输出格式】
输出到文件meal.out中。
仅一行一个整数，表示所求方案数对 998,244,353 取模的结果。
【样例 1 输入】
2 3
1 0 1
0 1 1
【样例 1 输出】
3
【样例1解释】
由于在这个样例中，对于每组i，j，Emiya都最多只会做一道菜，因此我们直接通 过给出烹饪方法、主要食材的编号来描述一道菜。
符合要求的方案包括：
•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜
•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜
•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜
因此输出结果为3 mod 998,244,353 = 3。
需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材 在超过一半的菜中出现，这不满足Yazid的要求。
【样例2输入】
3 3
1 2 3
4 5 0
6 0 0
【样例2输出】
190
【样例2解释】
Emiya必须至少做2道菜。
做2道菜的符合要求的方案数为100。
做3道菜的符合要求的方案数为90。
因此符合要求的方案数为100 + 90 = 190。
【样例3输入】
5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
1 0 1 0 1
0 1 1 0 1
【样例3输出】
742
【数据范围】
对于所有测试点，保证 1 ≤n≤ 100, 1 ≤ m ≤ 2000, 0≤ai，j< 998,244,353。
参考答案：对于每个烹饪方法i，我们统计有多少种不同的主要食材j，使得Emiya会做ai,j道菜。对于每种烹饪方法i，我们考虑其对应的主要食材j的数量。如果数量小于等于⌊m/2⌋，我们可以选择做这道菜；否则，我们不能选择做这道菜。对于每种烹饪方法i，我们可以选择做这道菜或者不做这道菜，所以总共有2^n种选择方式。对于每种选择方式，我们可以根据Yazid的要求，统计有多少种不同的主要食材j被使用了超过⌊m/2⌋次。如果数量超过⌊m/2⌋，则这种选择方式不符合要求，否则符合要求。最后，我们将所有符合要求的选择方式的数量相加，即为最终答案。
解析：【喵呜刷题小喵解析】：
本题是一道组合计数问题，需要满足三个条件：
1. 至少做一道菜；
2. 每道菜的烹饪方法互不相同；
3. 每种主要食材至多在一半的菜中被使用。
我们可以按照以下步骤来求解：
1. 对于每个烹饪方法i，统计有多少种不同的主要食材j，使得Emiya会做ai,j道菜。
2. 对于每种烹饪方法i，我们可以选择做这道菜或者不做这道菜，所以总共有2^n种选择方式。
3. 对于每种选择方式，我们可以根据Yazid的要求，统计有多少种不同的主要食材j被使用了超过⌊m/2⌋次。如果数量超过⌊m/2⌋，则这种选择方式不符合要求，否则符合要求。
4. 最后，我们将所有符合要求的选择方式的数量相加，即为最终答案。
由于本题要求答案对998,244,353取模，因此在计算过程中需要注意取模运算。
本题可以通过动态规划或组合数学的方法来解决，具体实现方式需要根据题目要求和数据范围来确定。
2、划分
【题目描述】
2048年，第三十届CSP认证的考场上，作为选手的小明打开了第一题。这个题的 样例有n组数据，数据从1~n编号，i号数据的规模为ai。
小明对该题设计出了一个暴力程序，对于一组规模为u的数据，该程序的运行时 间为u^2。然而这个程序运行完一组规模为u的数据之后，它将在任何一组规模小于u 的数据上运行错误。样例中的ai,不一定递增，但小明又想在不修改程序的情况下正确 运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据 段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据 的规模之和.小明将让新数据的规模能够递增。
也就是说，小明需要找到一些分界点
使得
注意P可以为0且此时k0 = 0,也就是小明可以将所有数据合并在一起运行。
小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化
小明觉得这个问题非常有趣，并向你请教：给定n和ai,请你求出最优划分方案 下，小明的程序的最小运行时间。
【输入格式】
从文件partition.in中读入数据。
由于本题的数据范围较大，部分测试点的ai将在程序内生成。
第一行两个整数n.type. n的意义见题目描述，type表示输入方式。
1.若type = 0.则该测试点的ai直接给出。输入文件接下来：第二行n个以空格 分隔的整数ai，表示每组数据的规模。
2.若type = 1则该测试点的ai将特殊生成，生成方式见后文。输入文件接下来: 第二行六个以空格分隔的整数x,y,z,b1,b2,m。 接下来m行中，第i
行包含三个以空格分隔的正整数pi,li,ri。
对于type = 1的23 ~ 25号测试点，ai的生成方式如下：
给定整数x,y,z,b1，b2，m,以及m个三元组（pi，li，ri）。
保证 n
2。 若 n > 2,则
保证
对于所有
则有ai=（bi mod（rj-lj+1））+lj
上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。
【输出格式】
输出到文件partition.out中。
输出一行一个整数，表示答案。
【样例1输入】
5 0
5 17 9 9
【样例1输出】
247
【样例1解释】
最优的划分方案为{5,1},{7},{9},{9}。由5 + 1<=7<=9<=9知该方案合法。
答案为(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247。
虽然划分方案{5}，{1},{7},{9},{9}对应的运行时间比247小，但它不是一组合法 方案，因为5>1。
虽然划分方案{5},{1,7},{9},{9}合法，但该方案对应的运行时间为251,比247大。
【样例2输入】
10 0
5677462 13 19 9
【样例2输出】
1256
【样例2解释】
最优的划分方案为{5},{6}，{7}，{7},{4,6，2},{13},{19,9}。
【数据范围】
所有测试点满足：type € {0,1} , 2 < =n <= 4 x 10^7 , 1 < =ai,<= 10^9 , 1 <=m < =10^5 , 1 < =li <= ri <= 10^9 , 0 < x,y,z,b1,b2 < 2^30。
参考答案：对于本题，由于数据范围较大，我们需要设计一种高效的算法来求解。一种可行的思路是使用动态规划来解决这个问题。我们可以定义一个二维数组dp[i][j]，其中dp[i][j]表示将前i个数据划分为j段的最小运行时间。然后，我们可以使用动态规划的思想来填充这个二维数组。具体的，对于dp[i][j]，我们可以考虑将第i个数据划分到前面的j-1段中，或者将第i个数据单独划分为一段。如果我们将第i个数据划分到前面的j-1段中，那么我们需要找到一个分界点k，使得前k个数据可以划分到前面的j-1段中，而后i-k个数据可以单独划分为一段。因此，我们可以得到状态转移方程：dp[i][j] = min(dp[k][j-1] + sum(k+1, i)^2)，其中k从0到i-1遍历。最后，我们只需要计算dp[n][k]，其中k从1到n遍历，就可以得到最小运行时间。
解析：【喵呜刷题小喵解析】：
本题是一道动态规划的问题，可以通过定义二维数组dp[i][j]来求解。在动态规划的过程中，我们需要找到一种状态转移方程，使得我们可以通过这个方程来填充二维数组。在本题中，我们可以将问题转化为一个最优化问题，即找到一种划分方案，使得程序的最小运行时间最小。由于数据范围较大，我们需要设计一种高效的算法来求解这个问题。动态规划是一种常用的求解最优化问题的方法，可以通过定义状态、状态转移方程和填充二维数组来求解。在本题中，我们可以将前i个数据划分为j段，然后找到一种最优的划分方案，使得程序的最小运行时间最小。通过填充二维数组，我们可以找到一种最优的划分方案，从而得到最小运行时间。
3、树的重心
小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：
1.一个大小为n的树由n个结点与n-1条无向边构成，且满足任意两个结点间有 且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个 子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。
2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树 中删去c及与它关联的边后，分裂出的所有子树的大小均不超过
（其中Lx」 是下取整函数）。对于包含至少一个结点的树.它的重心只可能有1或2个。
课后老师给出了一个大小为n的树S,树中结点从1~n编号。小简单的课后作业 是求出S单独删去每条边后，分裂出的两个子树的重心编号和之和。即：
上式中，E表示树S的边集，（u，n）表示一条连接u号点和V号点的边。S'u与S'v 分别表示树S删去边（u，v）后，u号点与V号点所在的被分裂出的子树。
小简单觉得作业并不简单，只好向你求助，请你教教他。
【输入格式】
从文件centroid.in中读入数据。
本题输入包含多组测试数据。
第一行一个整数T表示数据组数。
接下来依次给岀每组输入数据，对于每组数据：
第一行一个整数n表示树S的大小。
接下来n -1行，每行两个以空格分隔的整数 ui，vi，表示树中的一条边（ui，vi）。
【输出格式】
输出到文件centroid.out中。
共T行，每行一个整数.第i行的整数表示：第i组数据给岀的树单独删去每条边 后，分裂出的两个子树的重心编号和之和。
【样例1输入】
2
5
12
23
24
35
7
1 2
1 3
1 4
3 5
3 6
6 7
【样例1输出】
32
56
【样例1解释】
对于第一组数据:
删去边（1,2）, 1号点所在子树重心编号为｛1｝, 2号点所在子树重心编号为｛2,3｝。 删去边（2,3）, 2号点所在子树重心编号为⑵，3号点所在子树重心编号为｛3,5｝。
删去边（2,4）, 2号点所在子树重心编号为｛2,3｝, 4号点所在子树重心编号为｛4｝。 删去边（3,5）, 3号点所在子树重心编号为｛2｝, 5号点所在子树重心编号为｛5｝。
因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。
【数据范围】
表中特殊性质一栏，两个变量的含义为存在一个1~n的排列
使得:
A：树的形态是一条链。即
存在一条边(pi,pi+1)。
B：树的形态是一个完美二叉树。即
存在两条边(Pi，P2i)与(Pi，P2i+1)。 对于所有测试点：
保证给岀的图是一个树。
参考答案：对于每组数据，首先构建树S，然后遍历每条边(u, v)，删去该边后，分别找到u号点和v号点所在的子树，并计算这两个子树的重心编号和。最后将所有子树的重心编号和相加，即为所求。
解析：【喵呜刷题小喵解析】：
根据题目描述，我们需要计算树S单独删去每条边后，分裂出的两个子树的重心编号和之和。首先，我们需要理解树的重心的定义。对于一个大小为n的树，称c是该树的重心当且仅当在树中删去c及与它关联的边后，分裂出的所有子树的大小均不超过n/2。对于包含至少一个结点的树，它的重心只可能有1或2个。
对于每组数据，我们首先构建树S，然后遍历每条边(u, v)，删去该边后，分别找到u号点和v号点所在的子树，并计算这两个子树的重心编号和。具体计算方法如下：
1. 找到u号点和v号点所在的子树，分别记为T1和T2。
2. 对于T1和T2，分别计算它们的重心编号和。对于T1，遍历T1中的所有结点，对于每个结点i，计算以i为根的子树的大小，如果大小不超过n/2，则将i加入T1的重心集合中。对于T2也进行相同的操作。
3. 将T1和T2的重心编号和相加，即为所求。
需要注意的是，由于题目中给出的树的大小n可能非常大，因此我们需要使用高效的算法来计算树的重心。一种常用的算法是DFS（深度优先搜索）算法，可以通过遍历树的所有结点来计算以每个结点为根的子树的大小，从而找到树的重心。
另外，题目中给出的数据范围较小，因此我们不需要考虑时间复杂度的问题。对于每组数据，我们只需要遍历树S的每条边，并计算相应的结果即可。
最后，我们需要注意题目中给出的特殊性质，这些性质可以帮助我们更快地解决问题。例如，如果树的形态是一条链，我们可以直接遍历链的每个结点，找到以该结点为根的子树的大小，从而找到重心。如果树的形态是一个完美二叉树，我们可以利用二叉树的性质，快速地找到重心。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
