四道题，望专家讲解并附上代码，AC采纳

Question

勾股定理（triangle）

题目描述

小G最近学了勾股定理，于是他想问你一个问题。

小G给出了一个数字 $x$，请你判断它有没有可能是某个边长均为正整数的直角三角形中某一条边的长度。

如果不可能，输出 $-1$​ ​。如果可能，求出另外两条边的长度。

因为小G不擅长算数，所以如果答案不在 $10^{18}$ 范围内，也视为不可能。

勾股定理：直角三角形的三条边长度 $a, b, c$ 满足 $a^2+b^2=c^2$​ 。

输入格式

第一行包含一个正整数 $x$ ，表示小G给出的数字。

输出格式

输出包含一行，如果不可能，输出 $-1$。否则输出两个用空格隔开的正整数表示另外两条边的长度。

样例 #1

样例输入 #1

3

样例输出 #1

4 5

样例 #2

样例输入 #2

13

样例输出 #2

5 12

提示

【数据范围】

对于所有测试数据有：$1\leq x\leq 10^9$。

测试点	$x\leq$	特殊性质
$1\sim 3$	$50$	无
$4\sim 6$	$10^7$	有
$7\sim 10$	$10^9$	无

特殊性质：输入的 $x$ 保证能成为某个边长均为正整数的直角三角形中的一条斜边。

宝可梦军团（pokemon）

题目描述

在战乱纷飞的年代，平行宇宙中的各个世界陷入了混战。小 Z 作为宝可梦世界中的战略参谋，肩负着重大的使命。小 Z 手下拥有 $n$ 个强大的宝可梦（$n$ 是 $3$ 的倍数），它们各自具备独特的物理攻击能力和魔法攻击能力。更具体地，$n$ 个宝可梦编号为 $1,2,\cdots,n$，其中第 $i$ 个宝可梦的物理攻击能力为 $a_i$，魔法攻击能力为 $b_i$。

为了应对这场前所未有的危机，小 Z 决定将这些宝可梦分成三个军团，以应对不同类型的战争界面。

第一个军团将前往物理界面，与敌人进行物理对抗，因此我们需要挑选物理攻击能力最强的宝可梦，组成物理军团。顾名思义，就是想要使得团队中宝可梦的的物理攻击能力之和最大。我们记物理军团中宝可梦的物理攻击能力之和为 x。

第二个军团将前往魔法界面，与敌人进行魔法较量。因此我们需要挑选魔法攻击能力最强的宝可梦，组成魔法军团。顾名思义，就是想要使得团队中宝可梦的的魔法攻击能力之和最大。我们记魔法军团中宝可梦的魔法攻击能力之和为 y。

而第三个军团将面临更为复杂的挑战，它们需要在物理和魔法兼备的综合界面作战。这意味着我们需要挑选出既能物理攻击又能魔法攻击的宝可梦，组成综合军团。更具体地，想要使得组成的团队中宝可梦的物理攻击能力和魔法攻击能力之和再除以 $2$ 最大。我们记综合军团中宝可梦的物理攻击数值与魔法攻击数值之和除以 $2$ 的结果为 z。

由于 $n$ 是 $3$ 的倍数，可以确保每个军团拥有相同数量的宝可梦。小 Z 想要将这宝可梦分成数量相同的三个军团。然而，如何分配这些宝可梦，以最大化三个军团的战斗力估值之和，成为了小 Z 需要解决的关键问题。

输入格式

第一行输入一个整数 $n$，表示宝可梦的数量。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个宝可梦的物理攻击能力。

第三行输入 $n$ 个整数 $b_1,b_2,\cdots,b_n$ 表示每个宝可梦的魔法攻击能力。

输出格式

输出一行一个数字，表示答案，即x+y+z的最大值。如果答案是小数，则输出一位小数，如果答案是整数，则直接输出整数。

样例 #1

样例输入 #1

6
1 7 3 4 5 9
2 3 9 4 3 3

样例输出 #1

35

数据范围

对于 $50%$ 数据, $n \le 300$。

对于 $100%$ 数据, $3 \le n \le 3*10^5,1 \le a_i,b_i \le 10^9$，并且保证 $n$ 是 $3$ 的倍数。

五彩斑斓（colorful）

题目描述

小 Z 最近收到了一个花花绿绿的矩阵，有 $n$ 行 $m$ 列，位置在第 $i$ 行第 $j$ 列的方格颜色是 $c_{ij}$。

小 Z 觉得一个矩阵是五彩斑斓的，当且仅当这个矩阵四个顶点上的颜色不都相同。

• 不都相同的意思是，当且仅当矩阵四个顶点上的 $c_{ij}$ 至少有一个和其他点颜色不同。

现在小 Z 想让你帮忙数一下，这个矩阵有多少个子矩阵是五彩斑斓的。

• 特殊的，原矩阵也算一种子矩阵，四个顶点都在同一个位置也算一种子矩阵。

输入格式

第一行两个正整数 $n,m$ ，代表矩阵的大小。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 个第 $j$ 个整数 $c_{ij}$ 代表这个位置的颜色。

输出格式

输出一个整数，代表五彩斑斓的子矩阵个数。

样例 #1

样例输入 #1

3 4
1 2 3 1
1 3 1 2
1 2 1 1

样例输出 #1

35

提示

对于 $20%$ 的数据，$1\le n, m\le 80$。

对于另外 $20%$ 的数据，$c_{i,j}=0$ 或 $1$。

对于 $80%$ 的数据，$1\le c_{i,j}\le 400$。

对于全部数据，$1\le n,m\le 400, 0\le c_{i,j}\le 10^6$。

终局（end）

题目描述

仙剑 3 的结局中，景天接受了魔尊重楼的挑战，踏入新仙界，两人约定进行一场激烈的 $n$ 回合对决。景天深知速度的重要性，因此选择了全速装备，确保自己能在每个回合中先行行动。对决伊始，景天拥有 $A$ 点生命值，而重楼则拥有 $B$ 点。

在每一回合中，景天面临三种策略选择，景天会从如下三种决策中任选一种进行：

1. 举火燎天：他运用炼狱火海与仙风云体的组合技，对重楼造成 $X$ 点伤害。
2. 格挡：景天施展魔剑防御，使重楼在当回合无法对他造成伤害。
3. 暖雾：景天瞬间恢复 $Y$ 点生命值，确保自己能在接下来的战斗中保持最佳状态。

然而，重楼知道景天身为人类的局限，抵挡不了魔尊的全力，因此他选择了一种故意放水的策略——每回合仅对景天进行普通攻击，第 $i$ 回合造成的伤害为 $c_i$。

这场对决的胜负，将取决于双方的生命值。一旦某一方的生命值降至 $0$ 或以下，他便会宣告战败。

• 需要注意的是，每回合是景天先做出决策，然后才是重楼对景天进行攻击。即如果某一回合，景天攻击后，重楼生命值已经小于等于 $0$，那么此时重楼就已经战败了。

现在，我们需要帮助景天制定一个最优的战术方案。如果景天能在 $n$ 回合内战胜重楼，我们需要找出他所需的最少回合数；若景天无法在规定回合内取胜，我们则需要计算出他所能对重楼造成的最大伤害值。

输入格式

第一行为 $5$ 个数，分别为 $n，X，Y，A，B$，意义见描述。

接下来 $n$ 行，每行 $1$ 个数 $c_i$，意义见描述。

输出格式

包括两行。

如果能战胜重楼，则第一行输出 "Win"，第二行输出战胜重楼花费的最少的回合数。

如果无论如何都不能在 $n$ 回合内战胜，则在第一行输出 "Lose"，第二行输出能造成的最大伤害值。

样例 #1

样例输入 #1

4 1 1 3 3
1
10
1
10

样例输出 #1

Win
4

数据范围

对于 $30%$ 数据，$n \le 50$。

对于 $40%$ 数据，$n \le 200$。

对于 $50%$ 数据，$n \le 10^4$。

对于 $100%$ 数据,$n \le 10^5, A,B \le 10^9,X,Y,c_i \le 10^4$。

Answer 1

🕒下午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：“成功是不断学习和成长的过程。”** — 亨利·福特

下面是对四道题目的详细讲解和相应的 C++ 代码实现。

1. 勾股定理（triangle）

题目分析：
给定一个正整数 x，我们需要判断它是否可以是某个直角三角形的边长。如果可以，输出另外两条边的长度；如果不可以，输出 -1。根据勾股定理，若 x 是斜边，则需要找到 a 和 b 使得 a^2 + b^2 = x^2。

代码实现：

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long x;
    cin >> x;

    long long x2 = x * x;
    for (long long a = 1; a < x; ++a) {
        long long b2 = x2 - a * a;
        if (b2 <= 0) continue;
        long long b = sqrt(b2);
        if (b * b == b2 && b > 0) {
            cout << a << " " << b << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

2. 宝可梦军团（pokemon）

题目分析：
我们需要将 n 个宝可梦分成三个军团，使得每个军团的战斗力最大化。每个军团的战斗力分别是物理攻击、魔法攻击和综合攻击。由于 n 是 3 的倍数，我们可以简单地选择前 n/3 个最强的宝可梦。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    long long x = accumulate(a.begin(), a.begin() + n / 3, 0LL);
    long long y = accumulate(b.begin(), b.begin() + n / 3, 0LL);
    long long z = 0;

    for (int i = 0; i < n / 3; ++i) {
        z += (a[i] + b[i]) / 2;
    }

    cout << x + y + z << endl;
    return 0;
}

3. 五彩斑斓（colorful）

题目分析：
我们需要计算矩阵中有多少个子矩阵的四个角的颜色不全相同。可以通过遍历所有可能的子矩阵，检查其四个角的颜色。

代码实现：

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> matrix[i][j];

    long long count = 0;
    for (int r1 = 0; r1 < n; ++r1) {
        for (int r2 = r1; r2 < n; ++r2) {
            for (int c1 = 0; c1 < m; ++c1) {
                for (int c2 = c1; c2 < m; ++c2) {
                    set<int> colors = {
                        matrix[r1][c1],
                        matrix[r1][c2],
                        matrix[r2][c1],
                        matrix[r2][c2]
                    };
                    if (colors.size() < 4) count++;
                }
            }
        }
    }

    cout << count << endl;
    return 0;
}

4. 终局（end）

题目分析：
我们需要模拟战斗过程，选择最佳策略以最小化回合数或最大化造成的伤害。可以使用动态规划来解决这个问题。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, X, Y, A, B;
    cin >> n >> X >> Y >> A >> B;
    vector<int> c(n);
    for (int i =
继续完成第四道题的代码实现。

### 4. 终局（end）

**代码实现**：
我们将使用动态规划来模拟每一回合的选择。我们需要跟踪景天的生命值和重楼的生命值，并根据选择的策略更新它们。我们将尝试每种策略并记录结果。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, X, Y, A, B;
    cin >> n >> X >> Y >> A >> B;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }

    // dp[i]表示在第i回合结束时景天的生命值
    vector<long long> dp(n + 1, -1);
    dp[0] = A; // 初始生命值

    for (int i = 0; i < n; ++i) {
        for (int j = i; j >= 0; --j) {
            if (dp[j] < 0) continue; // 如果当前生命值无效，跳过
            // 选择举火燎天
            long long newB = B - X;
            if (newB <= 0) {
                cout << "Win\n" << j + 1 << endl;
                return 0;
            }
            dp[j + 1] = max(dp[j + 1], dp[j] - c[i]);

            // 选择格挡
            dp[j] = max(dp[j], dp[j] - c[i]);

            // 选择暖雾
            dp[j] = max(dp[j], dp[j] + Y - c[i]);
        }
    }

    // 如果到最后一回合都没有赢，计算最大伤害
    long long maxDamage = 0;
    for (int i = 0; i <= n; ++i) {
        if (dp[i] > 0) {
            maxDamage = max(maxDamage, (long long)(i * X));
        }
    }

    cout << "Lose\n" << maxDamage << endl;
    return 0;
}

总结

以上是四道题目的详细讲解和 C++ 代码实现。每道题目都涉及不同的算法和数据结构，适合不同的编程技巧和思维方式。希望这些代码和解释能帮助你理解题目并顺利完成相关的编程任务！如果有任何问题或需要进一步的解释，请随时询问。