当我把osu!的模组搬到OI中以后...第1期

今天突发奇想，想到了OI算法题对应的四个模组：
（1）HR - 提升算法题目的es, hp, od难度系数，以及提升memory limit和time limit的难度系数（通常是要降低它们，比如降低到原来的70%）
es: 相当于osu!的circle size，测试用例的上限提升到原来的2倍；
hp: 限制提交算法的最大次数，和osu!一样，值越大，一次挑战的提交次数越少（HP0 - 最多提交30次；HP10 - 最多提交2次）
od: 限制提交时间间隔的属性，OD值越高，每次留给你写代码的时间越短。OD0: 完美判定为36分钟；OD10: 完美判定为6分钟（在6分钟内写完代码并提交，否则会判定为一次失误，即浪费一次提交次数）
（2）DT - 增加算法题的维度
比如三维接雨水问题+DT = 四维接雨水
但不改变测试样例的数值特征和尺寸特征/范围，OD不变。
（3）HD: 写代码时不借助任何外部提示
（4）FL: 写代码时只能注意到本行的范围/用笔手写代码

当然除了这些模组以外，还有一些模组值得我们注意：
NF: 提交次数无限制
EZ: 通过50%的测试样例就能通关
HT: 降低题目的维度
比如说 -
两数之和这个题+HT就变成了：
给定一个数num和target, 输出另一个数使其加上num = target.

我一下子睡不着了……然后把剩下几个模组也弄出来了：
RX(Relax):只阐述算法原理，无需编写具体代码（或由AI生成）
AP(Auto-Pilot):提供题解详细思路，但需要用其中一种语言实现代码
SO(Spun-Out):这个似乎没想出来，但想到因为osu!有转盘……那或许……我知道了！（一些脏代码预先生成，只需补充核心代码）

然后还是没有睡着...于是和GPT-4o交流了一些问题：

Leetcode每日一题：一个小组的最大实力值

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​] 。

请你返回老师创建的小组能得到的最大实力值为多少。

示例 1：

输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。
示例 2：

输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

提示：

1 <= nums.length <= 13
-9 <= nums[i] <= 9

加上HR模组后：
1 <= nums.length <= 16

• -12 <= nums[i] <= 12

EZ模组：

1 <= nums.length <= 6
0 <= nums[i] <= 5

上面是No Mod题目的描述，如果加了HT和DT之后，描述会有所变化：

加上HT后的题目描述

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一个同学和其他已经选好的最优的人组成一组（设这个同学的实力为h），假设老师新选的同学提供的实力增幅为h^2,那么：
请你返回老师创建的小组能得到的最大实力增幅是多少。

HTHR模组：
1 <= nums.length <= 16
-2^31 <= nums[i] <= 2^31-1

加上DT后的题目描述

给你一个下标从 0 开始的二维数组 nums ，它表示一个年级中不同班级（每行代表一个班级）中所有学生在一次考试中的成绩。老师想在每班选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0,j0; i1,j1; i2,j2; ... ;ik,jk ，那么这个小组的实力值定义为 nums[i0][j0] * nums[i1][j1] * nums[i2][j2] * ... * nums[ik​][jk] 。
而且，老师选择的同学要满足每班至少有一个同学入选。
请你返回老师创建的小组能得到的最大实力值为多少。

DTNM要求：

1 <= nums.row <= 7
1 <= nums.col <= 7
-9 <= nums[i][j] <= 9

DTEZ 要求：
1 <= nums.row <= 3
1 <= nums.col <= 3
0 <= nums[i][j] <= 2

DTHR要求（可能部分语言无法达标，因为超long long int了，可能需要自己写字符串表示的大整数类型）

1 <= nums.row <= 9
1 <= nums.col <= 9
-12 <= nums[i][j] <= 12

HD: 不借助任何提示
FL: 手写或限制代码编辑区视野

那么，我们如何解决这道题不同模组对应的问题呢？

NM/HR题解：

这段代码旨在解决如何在给定的 nums 数组中选取若干个元素，使得其乘积最大的问题。算法的时间复杂度为 O(n)，意味着它能够在线性时间内找到最大乘积。这是通过以下几个步骤实现的：

1. 初始化变量：

   • negativeCount：统计负数的个数。
   • zeroCount：统计零的个数。
   • positiveCount：统计正数的个数。
   • prod：用于记录所有非零数的乘积。
   • maxNegative：记录最接近零的负数（即最大的负数）。

2. 遍历 nums 数组：

   • 负数处理：
     • 如果当前数字为负数，增加 negativeCount 计数，并将其乘积累积到 prod 中。
     • 同时更新 maxNegative，即当前最大的负数。
   • 零处理：
     • 如果当前数字为零，则增加 zeroCount 计数。
   • 正数处理：
     • 如果当前数字为正数，增加 positiveCount 计数，并将其乘积累积到 prod 中。

3. 特殊情况处理：

   • 如果整个数组只有一个负数，且没有零和正数，那么最大乘积就是这个负数。
   • 如果数组中只有一个负数或没有负数，且没有正数，那么最大乘积为零（因为无法形成有效的小组）。
   • 如果所有数字乘积为负数（即负数的数量为奇数），那么我们要将最大的那个负数除掉（这能使得乘积变为正数，并且是最大可能的正数）。
   • 如果乘积为正数，则直接返回乘积。

4. 返回结果：

   • 根据情况返回最终计算的最大乘积。

代码解析

class Solution:
    def maxStrength(self, nums: List[int]) -> int:
        negativeCount, zeroCount, positiveCount = 0, 0, 0
        prod = 1
        maxNegative = -9
        
        for num in nums:
            if num < 0:
                negativeCount += 1
                prod *= num
                maxNegative = max(maxNegative, num)
            elif num == 0:
                zeroCount += 1
            else:
                prod *= num
                positiveCount += 1
        
        # Special case where there's only one negative number
        if negativeCount == 1 and zeroCount == 0 and positiveCount == 0:
            return nums[0]
        
        # Special case where there are only zero or one negative number and no positive number
        if negativeCount <= 1 and positiveCount == 0:
            return 0
        
        # If product is negative and there's more than one negative number, remove the largest negative number
        if prod < 0:
            return prod // maxNegative
        else:
            return prod

时间复杂度分析

• O(n)：在遍历 nums 数组时，每个元素只被访问一次，因此时间复杂度是线性的，即 O(n)。

核心思想

• 这段代码巧妙地使用了条件判断和积累乘积的方式来处理不同的情况。通过计算和剔除（如必要）特定元素（如最大的负数），算法能在保证时间复杂度为 O(n) 的情况下求得最大乘积值。

DT/DTHR题解

要在 DT 模组下解决这个问题，我们需要将二维数组 nums 中每个班级（即每一行）选出一部分学生，使得这些选出来的学生的成绩乘积最大，并且每个班级至少要选出一个学生。这与 NM 模组下的一维问题有相似的逻辑，但增加了维度和约束条件，因此需要进行一些调整和扩展。

• 核心思路

1. 最大乘积的计算：类似于 NM 模组，我们需要计算每一行的最大乘积。这意味着在每个班级内选择一些学生的成绩，使得乘积最大。
2. 负数处理：我们仍然需要关注负数的情况，因为负数的个数会影响乘积的符号。如果某一行的乘积是负数，我们需要考虑是否剔除掉其中的某个负数，来使得整体的乘积最大化。
3. 行组合：最终我们需要将所有班级的最大乘积组合起来。这里需要注意，如果总乘积为负数，我们应该剔除绝对值最小的负数。

• 具体算法步骤

1. 初始化：对于每一行，我们分别统计正数、负数的数量，乘积，以及最大负数的值。
2. 遍历二维数组：对于每一行，计算出最大乘积，考虑剔除负数的情况。
3. 计算最终结果：将所有行的最大乘积相乘，并处理可能的负数组合问题。

• 实现代码

def maxStrengthDT(nums):
    rows = len(nums)
    overall_prod = 1
    all_pos = True  # 判断是否全为正数或包含零
    min_negative = float('inf')  # 存储绝对值最小的负数
    has_negative = False  # 判断是否有负数
    
    for row in nums:
        row_prod = 1
        negativeCount = 0
        maxNegative = -float('inf')
        positiveCount = 0
        zeroCount = 0
        
        for num in row:
            if num < 0:
                negativeCount += 1
                row_prod *= num
                maxNegative = max(maxNegative, num)
            elif num > 0:
                positiveCount += 1
                row_prod *= num
            else:
                zeroCount += 1
        
        if negativeCount % 2 != 0:  # 行乘积为负数
            row_prod //= maxNegative
            has_negative = True
            min_negative = min(min_negative, maxNegative)
        
        # 只有零的情况
        if row_prod == 1 and zeroCount == len(row):
            row_prod = 0
        
        overall_prod *= row_prod
        if row_prod < 0:
            all_pos = False
    
    # 全是正数的情况直接返回乘积
    if all_pos:
        return overall_prod
    
    # 如果总乘积为负数，则剔除绝对值最小的负数
    if has_negative:
        return overall_prod // min_negative
    
    return overall_prod

# 示例用法
nums = [
    [3, -1, -5, 2],
    [4, -2, 1, -7],
    [0, 5, 3, -8],
    [2, -9, -4, 1]
]
print(maxStrengthDT(nums))  # 输出最大实力值

复杂度分析

• 时间复杂度：O(rows * cols)，其中 rows 是二维数组的行数，cols 是列数。每行计算乘积的时间复杂度是 O(cols)，整个算法需要遍历所有行，因此时间复杂度是 O(rows * cols)。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间来存储变量。

通过这种算法设计，已经能够应对更高维度的挑战（例如 DTHR），因为其时间复杂度仍然较低。即使数组规模增大或数值范围更广，这个算法仍然是最优解。

一些模组下的特殊解法：

1. HT
   思路：
2. 取绝对值：对每个学生的成绩取绝对值。
3. 计算平方：对绝对值进行平方计算以获得增幅。
4. 找最大值：记录最大的增幅。

优化后的 Python 实现：

def max_strength_increase_optimized(nums):
    max_abs = float('-inf')
    
    for h in nums:
        abs_h = abs(h)
        if abs_h > max_abs:
            max_abs = abs_h
    
    return max_abs * max_abs

# 示例测试
nums = [3, -1, -5, 2, 5, -9]
print(max_strength_increase_optimized(nums))  # 输出 81，即 -9 的平方

nums = [-4, -5, -4]
print(max_strength_increase_optimized(nums))  # 输出 25，即 -5 的平方

复杂度分析：

• 时间复杂度：O(n)，遍历一次数组来计算绝对值和找最大值。
• 空间复杂度：O(1)，只需要常数空间来记录最大绝对值。

结论：

这个优化不仅简化了计算步骤，还提高了效率，特别适合 HT 和 HTHR 模组。在这种情况下，计算绝对值再平方比直接计算平方更加高效。

2. cpp 实现的HTHR(long long)

#include <iostream>
#include <vector>
#include <climits>  // For LONG_LONG_MIN and LONG_LONG_MAX
#include <cstdlib>  // For std::abs

long long max_strength_increase_optimized(const std::vector<int>& nums) {
    long long max_abs = LLONG_MIN;
    
    for (int h : nums) {
        long long abs_h = std::abs(static_cast<long long>(h));  // Convert to long long before taking abs
        if (abs_h > max_abs) {
            max_abs = abs_h;
        }
    }
    
    return max_abs * max_abs;
}

int main() {
    std::vector<int> nums1 = {3, -1, -5, 2, 5, -9};
    std::cout << "Maximum Strength Increase: " << max_strength_increase_optimized(nums1) << std::endl;  // Output: 81

    std::vector<int> nums2 = {-4, -5, -4};
    std::cout << "Maximum Strength Increase: " << max_strength_increase_optimized(nums2) << std::endl;  // Output: 25

    return 0;
}

2. EZDT

由于EZDT模组的非负性和范围有限，范围是0～2之间（注意到只有实力为2才会影响总实力，而1不影响，因为1乘以任何数都等于其本身），我们甚至可以将全0检查和后续的实力计算优化到位运算的精度。具体步骤如下：
（1）计算每一行按位或的值再把结果按位与，如果结果为0。则输出0；
（2）如果结果不为0，初始化结果为1，遍历输入中“2”的个数，将结果左移2的个数位即位最终结果。
我们甚至只用按位运算加1两种运算就能解决这个问题！

#include <iostream>
#include <vector>
#include <bitset>

int max_strength_dtez_optimized(const std::vector<std::vector<int>>& nums) {
    int rows = nums.size();
    std::vector<int> row_or_results(rows, 0);
    
    // Step 1: Compute bitwise OR for each row
    for (int i = 0; i < rows; ++i) {
        for (int num : nums[i]) {
            row_or_results[i] |= num;
        }
    }
    
    // Compute overall bitwise AND of row OR results
    int overall_or = row_or_results[0];
    for (int i = 1; i < rows; ++i) {
        overall_or &= row_or_results[i];
    }
    
    // Step 2: Check if the overall OR is zero
    if (overall_or == 0) {
        return 0;
    }
    
    // Count the number of 2s in the matrix
    int count_of_twos = 0;
    for (const auto& row : nums) {
        count_of_twos += std::count(row.begin(), row.end(), 2);
    }
    
    // Compute the result as 2 raised to the power of count_of_twos
    return 1 << count_of_twos;
}

int main() {
    std::vector<std::vector<int>> nums1 = {{1, 2, 0}, {2, 1, 1}, {1, 0, 0}};
    std::cout << "Maximum Strength: " << max_strength_dtez_optimized(nums1) << std::endl;  // Output: 4 (2^2)

    std::vector<std::vector<int>> nums2 = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
    std::cout << "Maximum Strength: " << max_strength_dtez_optimized(nums2) << std::endl;  // Output: 0

    return 0;
}