TopCoder SRM842

A. ToniasTower

题意

Tonia 有N个单位立方体。她想用它们来建造一座塔。 Tonia 的塔将由一排或多排立方体组成，每一排立在下一排上。（显然，除了站在地上的最下面一排。） 只有一个限制：除底部以外的每一行都必须严格比它所在的行短（即，立方体严格减少）。

Tonia 现在想知道：她可以用所有立方体建造的最高塔是什么？ 找到最大的 X，这样 Tonia 可以使用她的N个立方体来建造一个有 X 行立方体的塔。然后，找到一种建造这样一座塔的方法。换句话说，确定塔的 X 行中每一行的立方体数量。 返回带有 X 个元素的 a：对于塔的每一行，从上到下，Tonia 应该在该行中使用的立方体数量。

思路

让n一次减去，1，2，3，4，5…，最后如果剩下一个数字，则加给最后一个数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class ToniasTower {
public:
    std::vector<int> build(int);
};

std::vector<int> ToniasTower::build(int n) {
    std::vector<int> ans;
    for (int i = 1; i <= n; i++) {
        ans.push_back(i);
        n -= i;
    }
    ans.back() += n;
    return ans;
}

B. SmallRectangles

题意

我们有两个 A 和 B，分别有AL和BL元素。这些描述了如何切割矩形

整个矩形的尺寸为 sum(A) 乘以 sum(B)。通过使AL -1 切割正交于长度 sum(A) 的一侧和BL -1 切割与另一侧正交， 它被切割成AL乘以BL的较小矩形。

A 的元素是段的长度，切割将长度 sum(A) 的边分成这些段。类似地，B 的元素是矩形另一边被分割成的线段的长度。因此，A 和 B 是通过将大矩形切成块而产生的较小矩形的边长。

思路

对每一个pair插入到set中，求set到size()即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class SmallRectangles {
public:
    long long count(std::vector<int> Aprefix, std::vector<int> Bprefix, int AL, int BL, int AM, int BM, int seed);
};

long long SmallRectangles::count(std::vector<int> Aprefix, std::vector<int> Bprefix, int AL, int BL, int AM, int BM, int seed) {
    std::map<std::pair<int, int>, long long> cnt;
    for (int i = 0; i < AL; i++) {
        for (int j = 0; j < BL; j++) {
            int a = std::min(Aprefix[i], Bprefix[j]);
            int b = std::max(Aprefix[i], Bprefix[j]);
            cnt[{a, b}]++;
        }
    }
    long long ans = cnt.size();
    return ans;
}

C. StringReduction

题意

你有一串小写英文字母： 开始。

您还获得了 X和 Y。这些描述了您可以对字符串执行的一些操作。更准确地说，对于每个有效索引 i，整数X [i] 和字符Y [i] 描述了一个这样的操作，如下所述。

您可以通过以任意顺序任意多次执行以下操作来修改字符串：

交换字符串中的任意两个连续字符。 对于任何有效索引 i：选择一组特定的X [i] 个字母Y [i ] 的连续副本。擦除其中的X [i]-1 个，保留剩下的一个。 当然，只有当当前字符串中某处存在所需的相同字母组时，才能应用擦除规则。

思路

用cnt存下每个字符的个数，对每个字符，尽最大努力依次减去X[i] - 1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 class StringReduction {
public:
    int reduce(std::string, std::vector<int>, std::string);
};

int StringReduction::reduce(std::string start, std::vector<int> X, std::string Y) {

    std::vector<int> cnt(26);
    for (char &c : start) {
        cnt[c - 'a']++;
    }

    for (int i = 0; i < (int) X.size(); i++) {
        if (X[i] == 1) continue ;
        int digit = Y[i] - 'a';
        while (cnt[digit] >= X[i]) {
            cnt[digit] -= X[i] - 1;
        }
    }

    return std::accumulate(cnt.begin(), cnt.end(), 0);
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2022/12/03/topcoder-srm842/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！