链接：https://ac.nowcoder.com/acm/contest/58734/E 来源：牛客网 枫落有一个长度为 � n 的数组，你可以从这 � n 个数中任选 � ( � ≥ 1 ) x (x≥1) 个构成一个集合，定义一个集合的权值为该集合的数字之和，现在枫落想要问你一共可能构成多少种不同的权值。

这道题可以使用背包问题的思想来解决。我们可以先用一个数组来记录每个数字出现的次数，然后从小到大遍历所有数字，对于每个数字，我们可以选择将它加入之前的集合中，或者以它自己为一个新的集合。这样就可以得到所有可能的权值了。

具体地，我们可以使用一个数组 dp，其中 dp[i] 表示当只考虑前 i 个数字时，可能构成的不同权值的个数。初始时，dp[0] = 1，表示当没有数字可选时，只有一个权值为 0 的集合。然后对于每个数字 num，我们从大到小遍历 dp 数组，对于每个 dp[j]，我们可以选择将 num 加入之前的集合中，此时新的权值为 j+num，即 dp[j+num] += dp[j]；或者以 num 自己为一个新的集合，此时新的权值为 num，即 dp[num] += dp[j]。

最终，dp 数组的最大下标就是可能构成的最大权值，而 dp 数组中非零元素的个数就是可能构成的不同权值的个数。时间复杂度为 O(n^2)，可以通过此题。

相关问题

链接：https://ac.nowcoder.com/acm/contest/92236/J 来源：牛客网 小红拿到了一个仅由大小写字母组成的长度为 𝑛 n的字符串，她希望把前 𝑘 k个字母变成大写，后 𝑛 − 𝑘 n−k个字母变成小写

这是一个简单的字符串操作题目，要求将给定字符串中的前k个字符转换为大写，其余的转换为小写。在C语言中，我们可以使用`toupper()`和`tolower()`这两个标准库函数来进行字符的大小写转换。

#include <stdio.h>
#include <ctype.h>

void convert_case(char *str, int k) {
    for (int i = 0; i < k; i++) { // 将前k个字符转为大写
        str[i] = toupper(str[i]);
    }
    for (int i = k; i < strlen(str); i++) { // 将剩余字符转为小写
        str[i] = tolower(str[i]);
    }
}

int main() {
    char input[100]; // 假设字符串最大长度不超过100
    int n, k;
    
    printf("请输入字符串（忽略空格）和需要转换的大写字母数量: ");
    fgets(input, sizeof(input), stdin); // 注意处理换行符
    input[strlen(input) - 1] = '\0'; // 去掉末尾的换行符
    
    sscanf(input, "%d %d", &n, &k);
    
    if (k <= n && k >= 0) {
        convert_case(input, k);
        printf("转换后的字符串是: %s\n", input);
    } else {
        printf("k的值不正确，请确保0 <= k <= n。\n");
    }

    return 0;
}

在这个程序中，首先从用户那里获取字符串和k的值，然后调用`convert_case`函数执行转换。如果k的值在有效范围内（大于等于0且小于或等于n），则输出结果；否则提示错误。

链接：https://ac.nowcoder.com/acm/contest/59840/K 来源：牛客网 给定 n 个坐标，求其中 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形，等边三角形为特殊的等腰三角形。

对于这道题，我们可以考虑对输入的每两个点求出它们的中点，然后把这个中点作为哈希表的键值，值为一个列表，存储所有能与该中点构成等腰三角形的点。具体做法如下：

1. 枚举每两个点，计算它们的中点，把该中点作为哈希表的键值，值为一个空列表。

2. 遍历所有点，如果该点与中点的距离等于某个已有中点的距离，则将该点加入到对应的列表中。

3. 对于每个中点对应的列表，如果列表长度大于等于2，则说明存在能与该中点构成等腰三角形的点，计算组合数并累加到答案中。

时间复杂度为 $O(n^2 \log n)$，其中 $n$ 为点的个数。具体实现细节可以参考下面的代码：

from collections import defaultdict
import math

n = int(input())
points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

# 计算两点之间的距离
def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

# 构建哈希表
hash_map = defaultdict(list)
for i in range(n):
    for j in range(i + 1, n):
        p1, p2 = points[i], points[j]
        mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
        hash_map[mid] = []

# 遍历所有点
for i in range(n):
    for j in range(i + 1, n):
        p1, p2 = points[i], points[j]
        mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
        for k in range(n):
            if k != i and k != j:
                p3 = points[k]
                d1, d2 = dist(p1, p3), dist(p2, p3)
                if abs(d1 - d2) < 1e-6:
                    hash_map[mid].append(p3)

# 计算答案
ans = 0
for mid, points in hash_map.items():
    if len(points) >= 2:
        n = len(points)
        ans += n * (n - 1) // 2

print(ans)