将数组划分为 k 个非空非相交子段，使得每个子段具有奇数和
Partitioning the array into k non-empty non-intersecting subsegments such that each subsegment has odd sum
我是竞争性编程的新手。前几天我正在解决这个问题
给你一个数组a，由n个整数a1,a2,…,an组成。你想把它分成正好 k 个非空非相交的子段，这样每个子段的和都是奇数（即对于每个子段，属于这个子段的所有元素的总和是奇数）。不可能重新排列（洗牌）给定数组的元素。数组 a 的 n 个元素中的每一个都必须恰好属于 k 个子段之一。
我做了以下观察：
1.Ifn小于(<)k则不可能得到这样的段
2.If k=1 那么我们已经有了段。
3.If k 是奇数，那么为了得到所有条目的分区总和应该是奇数，即使 k 是偶数。
基于此，我想为分区构建一个逻辑。我遵循了 https://www.geeksforgeeks.org/partition-set-k-subsets-equal-sum/ 中给出的代码，但我认为可以通过一些逻辑来缩短这段代码。但我还没有构建一个具体的算法。
你们能帮我想出一个算法来完成这个任务吗？您可以随时分享任何想法
我首先要指出的是，您链接的代码旨在解决与您概述的问题不同的问题——而且它允许重新排列数组元素这一事实几乎肯定使它更适合难题。
你说的这个问题，就是把数组分成N个子数组，每个子数组都是奇数，先看奇数和偶数的性质。具体来说，偶数之和总是偶数。偶数个奇数之和也是偶数。要使总和为奇数，输入必须包含奇数个奇数。
基于此，我们可以很容易地确定是否可以得到想要的结果。要获得 K 个分区，每个分区的和都是奇数，输入必须至少包含 K 个奇数。否则，我们不可能创建 K 个奇数分区。
所以，如果恰好包含K个奇数，答案马上就是"yes"，我们就可以做分区了。我们可以从头开始，并在遇到第一个奇数时停止每个分区。当我们以这种方式创建 K-1 个分区时，输入的其余部分成为最后一个分区。
我们的每一个分区恰好包含一个奇数，并且我们将这K个奇数都划分到自己的分区中，所以我们满足了要求。
如果输入中有超过K个奇数，我们就得考虑到底多了多少。我们希望每个分区包含一个偶数加一个奇数。偶数和可以由任意数量的偶数产生，可以选择与偶数个奇数组合。
所以，让我们计算输入中的奇数，并将其称为 M。如果 K-M 是偶数，那么（再次）我们可以像以前一样选择 K-1 个分区——任意数量的偶数后跟一个奇数。因为每个只包含一个奇数，所以它们的和都是奇数。
最后一个分区将（再次）是单个奇数 + 一些偶数的总和 + 偶数个奇数的总和，因此（再次）它的总和将是奇数。
事实上，我们可以很快意识到第一种情况（正好是 K 个奇数）实际上只是第二种情况的特例，其中 K-M = 0，我们将 [0, 2, 4, 8, . ..] 为偶数。
所以你是对的：这个代码可能比你链接的问题更简单。首先计算输入中的奇数。如果它是 K+M（其中 M 是偶数），您可以创建从当前开始到下一个奇数的每个分区，并重复直到获得 K-1 个分区，然后输入的其余部分进入最后一个划分。如果M是奇数，那么这个输入根本就做不完任务。
我是竞争性编程的新手。前几天我正在解决这个问题
给你一个数组a，由n个整数a1,a2,…,an组成。你想把它分成正好 k 个非空非相交的子段，这样每个子段的和都是奇数（即对于每个子段，属于这个子段的所有元素的总和是奇数）。不可能重新排列（洗牌）给定数组的元素。数组 a 的 n 个元素中的每一个都必须恰好属于 k 个子段之一。
我做了以下观察：
1.Ifn小于(<)k则不可能得到这样的段
2.If k=1 那么我们已经有了段。
3.If k 是奇数，那么为了得到所有条目的分区总和应该是奇数，即使 k 是偶数。
基于此，我想为分区构建一个逻辑。我遵循了 https://www.geeksforgeeks.org/partition-set-k-subsets-equal-sum/ 中给出的代码，但我认为可以通过一些逻辑来缩短这段代码。但我还没有构建一个具体的算法。
你们能帮我想出一个算法来完成这个任务吗？您可以随时分享任何想法
我首先要指出的是，您链接的代码旨在解决与您概述的问题不同的问题——而且它允许重新排列数组元素这一事实几乎肯定使它更适合难题。
你说的这个问题，就是把数组分成N个子数组，每个子数组都是奇数，先看奇数和偶数的性质。具体来说，偶数之和总是偶数。偶数个奇数之和也是偶数。要使总和为奇数，输入必须包含奇数个奇数。
基于此，我们可以很容易地确定是否可以得到想要的结果。要获得 K 个分区，每个分区的和都是奇数，输入必须至少包含 K 个奇数。否则，我们不可能创建 K 个奇数分区。
所以，如果恰好包含K个奇数，答案马上就是"yes"，我们就可以做分区了。我们可以从头开始，并在遇到第一个奇数时停止每个分区。当我们以这种方式创建 K-1 个分区时，输入的其余部分成为最后一个分区。
我们的每一个分区恰好包含一个奇数，并且我们将这K个奇数都划分到自己的分区中，所以我们满足了要求。
如果输入中有超过K个奇数，我们就得考虑到底多了多少。我们希望每个分区包含一个偶数加一个奇数。偶数和可以由任意数量的偶数产生，可以选择与偶数个奇数组合。
所以，让我们计算输入中的奇数，并将其称为 M。如果 K-M 是偶数，那么（再次）我们可以像以前一样选择 K-1 个分区——任意数量的偶数后跟一个奇数。因为每个只包含一个奇数，所以它们的和都是奇数。
最后一个分区将（再次）是单个奇数 + 一些偶数的总和 + 偶数个奇数的总和，因此（再次）它的总和将是奇数。
事实上，我们可以很快意识到第一种情况（正好是 K 个奇数）实际上只是第二种情况的特例，其中 K-M = 0，我们将 [0, 2, 4, 8, . ..] 为偶数。
所以你是对的：这个代码可能比你链接的问题更简单。首先计算输入中的奇数。如果它是 K+M（其中 M 是偶数），您可以创建从当前开始到下一个奇数的每个分区，并重复直到获得 K-1 个分区，然后输入的其余部分进入最后一个划分。如果M是奇数，那么这个输入根本就做不完任务。