「果壳语法杯」ROUND #4

派蒙的西瓜

题目描述

派蒙和旅行者今天在清泉镇捡到了一个西瓜，经过称重确认这个西瓜的重量为千克，派蒙提出可以将西瓜分成两份，分别是千克、千克，针对分西瓜的方式有以下要求：

换句话说就是：分出来的两份西瓜重量加起来正好是这个西瓜的重量千克，还要保证分出来的两份西瓜重量是偶数的重量。

现在派蒙和旅行者还要去蒙德城交接任务，所以需要聪明的你来帮忙分西瓜，如果不可以按照以上要求分西瓜的话，就会把这个西瓜送给你，如果可以就会送你一份神秘礼包。

请问派蒙和旅行者交接完任务之后能不能吃到西瓜呢？如果能输出 Yes ，反之输出 No 。

输入格式

输入多行。

第一行输入一个正整数，代表有组测试数据。

接下来行，每行输入一个正整数，代表西瓜的重量。

输出格式

输出行。

对于每组测试数据，如果派蒙和旅行者交接完任务之后可以吃到西瓜输出 Yes ，反之输出 No 。

输入样例

输出样例

Yes
No
Yes
No
No

数据规模与约定

说明/提示：

对于第一组测试数据：可以将西瓜分成千克和千克，这样就可以让派蒙和旅行者吃上西瓜，输出 Yes 。
对于第五组测试数据：无法分成两份正好是偶数重量的西瓜，所以派蒙和旅行者无法吃上西瓜，输出 No 。

数据范围：

对于所有的数据范围保证：

。
。

测试点编号
`1 ~ 5`
`6 ~ 10`
`11 ~ 15`
`16 ~ 20`

✅【思路分析】

首先可以考虑直接暴力枚举的方式，枚举每一块西瓜的重量，然后检查是否符合要求即可：

时间复杂度为。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int w;
inline void solve() {
    cin >> w;
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= w; j++) {
            if ((i % 2 == 0) && (j % 2 == 0) && i + j == w) {
                printf("Yes\n");
                return;
            }
        }
    }
    printf("No\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

很明显是超时的，那么进行简单的优化，可以考虑枚举，如果为偶数，直接通过计算出来，检查是否为偶数。

需要注意计算出来的可能。

时间复杂度。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int w;
inline void solve() {
    cin >> w;
    for (int i = 1; i <= w; i++) {
        if (i % 2 == 0) {
            int j = w - i;
            if (j > 0 && j % 2 == 0) {
                printf("Yes\n");
                return;
            }
        }
    }
    printf("No\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

依然超时，继续分析。
根据题目要求，分出来的两块西瓜重量都要是偶数，那么根据偶数偶数偶数，需要保证西瓜本身的重量就是偶数，可以直接考虑是否为零，如果为零就是 Yes ，反之就是 No 。

这里需要注意一个特殊情况，就是为的时候，是偶数，但是只能分成和，做一个特判即可。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int w;
inline void solve() {
    cin >> w;
    if (w == 2) {
        printf("No\n");
        return;
    }
    if (w & 1) printf("No\n");
    else printf("Yes\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

⏱️【复杂度分析】

时间复杂度：
空间复杂度：

派蒙发现的数学题

题目描述

派蒙和旅行者在风龙遗迹的石碑上发现了一个有趣的数学题，如下：

现在给定两个正整数，对于所有的整数，找出的最小值。

派蒙已经知道如何去写了，现在把这个问题拿给同学们，请同学们找出的最小值。

输入格式

输入多行。

第一行输入一个正整数，代表有组测试数据。

接下来行，每行输入两个正整数。

输出格式

输出行。

对于每组测试数据，输出的最小值。

输入样例

输出样例

1
2
3

1
7
0

数据规模与约定

说明/提示：

对于第一组测试数据：当的时候，得到的答案为，可以证明该结果一定是最小的。
对于第三组测试数据：当的时候，得到的答案为，可以证明该结果一定是最小的。

数据范围：

对于所有的数据范围保证：

。
。

测试点编号
`1 ~ 5`
`6 ~ 10`

✅【思路分析】

首先可以考虑暴力枚举的值，的取值范围为，在这个过程中计算公式的结果，如果有小的就更新结果。

时间复杂度。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10, INF = 1e9 + 10;
int a, b;
inline void solve() {
    cin >> a >> b;
    int Ans = INF;
    for (int i = 0; i <= max(a, b); i++) {
        int Res = abs((i - a) + (b - i));
        Ans = min(Ans, Res);
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

事实上可以直接对公式。
直接简化：
。
可以发现最小的情况就是。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int a, b;
inline void solve() {
    cin >> a >> b;
    printf("%d\n", (int)abs(a - b));
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

⏱️【复杂度分析】

时间复杂度：
空间复杂度：

升级旅行者等级

题目描述

派蒙和旅行者正在冒险，现在进入了一个副本，副本中一共有个怪物，编号为到，其中第个怪物不能击杀，该副本有一个打怪的限制，如下：

1.第一个击杀的怪物是第个怪物，将会获得升级经验。。
2.接下来派蒙和旅行者只能对第个怪物造成伤害，也就是说只能击杀这些怪物；当击杀了这些怪物之后相应的也会获取到的升级经验。

旅行者升级需要非常多的升级经验，希望在该副本中尽可能的获取更多的升级经验，请告诉旅行者先将第几只怪物击杀，才可以在这个副本中获取到最多的升级经验。

输入格式

输入多行。

第一行输入一个正整数，代表有组测试数据。

接下来行，每行输入一个正整数，代表副本中怪物的数量。

输出格式

输出行。

对于每组测试数据，告诉旅行者先将第几只怪物击杀，才可以在这个副本中获取到最多的升级经验。

输入样例

2
3
15

输出样例

1
2

3
2

数据规模与约定

说明/提示：

对于第一组测试数据：如果第一个击杀的是编号为的怪物，最终可以获得升级经验；如果第一个击杀的是编号为的怪物，最终可以获得升级经验。
对于第二组测试数据：如果第一个击杀的是编号为的怪物，最终可以获得升级经验；如果第一个击杀的是编号为的怪物，最终可以获得升级经验；……；最终会发现第一个击杀编号为的怪物是最好的。

数据范围：

对于所有的数据范围保证：

。
。

测试点编号
`1 ~ 5`
`6 ~ 10`

✅【思路分析】

考虑暴力枚举枚举首杀怪物，然后计算通过规则击杀其他的怪物，计算这种情况下获得的经验，对比每一次经验，记录最高的情况，更新结果即可。

时间复杂度。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int n;
inline void solve() {
    cin >> n;
    int Ans = 0, Max = 0;
    for (int i = 2; i <= n; i++) {
        int Res = 0;
        for (int j = i; j <= n; j += i) {
            Res += j;
        }
        if (Res > Max) {
            Max = Res;
            Ans = i;
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

事实上可以观察到，经验其实就是将一些值进行相加，那么这些值的公差其实就是第一次击杀的怪物，所以可以直接通过等差数列求和计算。

首项为第一次击杀的怪物，项数为，公差为，末项为。
等差数列求和推导：
若等差数列首项为，公差为，共项，记作：

第项为，
前项的和为。

现在要求的是它的和：

把这个式子倒过来写，再加一遍：

将这两个式子逐项相加：

所以得出(使用首项和公差)：

因为：

所以可以把写作，于是有另一种形式(使用首项和末项)：

时间复杂度。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int n;
inline void solve() {
    cin >> n;
    int Ans = 0, Max = 0;
    for (int i = 2; i <= n; i++) {
        int Cnt = n / i;
        int Res = Cnt * (i + i * Cnt) / 2;
        if (Res > Max) {
            Max = Res;
            Ans = i;
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

继续观察会发现，差为的情况肯定是最大的。
证明：

我们假设所有数列都是从开始的，看看不同公差下，能构造出多长的数列，和是多少。

举例：

公差：
数列：，共项。

公差：
数列： → 和为

继续下去和会越来越小，这里就不再继续算了。

🧠 观察发现：

当时，和最大（）
但在一些约束条件下，比如不能从开始、或者不能连续取太多数时，会是最优

🧩 更通用的解释（答案的核心）：

在从开始，等差数列的和随着增大而减小，因为：

公差越大，数列变稀疏；
能取的项数就越少；
即使后面项更大，但数量少，和也小。

但是有一个微妙的点：

在某些优化问题中（比如选取不相邻数、或者要从某个集合中尽可能取大和），公差为的结构就“意外”地变成最优。

这就是你可能看到某些题中，“公差为 ”效果最好的根本原因 —— 它在“数量”和“数值大小”之间取得了很好的平衡。

✅ 结论总结：

如果从开始一直取到，那公差的和一定最大。
但在某些优化问题中（比如不能取相邻的数，或要最大子序列和），
公差为的等差结构会成为最佳选择，
因为它能兼顾：项数不少，数值又不太小，形成了最优解。

所以第一次击杀第只怪物就能保证经验最多，需要注意的是对于怪物数量为的时候，击杀第只怪物是最好的，需要做一个判别。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int n;
inline void solve() {
    cin >> n;
    if (n == 3) printf("3\n");
    else printf("2\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

⏱️【复杂度分析】

时间复杂度：
空间复杂度：

派蒙数

题目描述

当一个十进制整数所有位数上的数字相同，就可以将该数字称之为派蒙数，比如：就是派蒙数，但是就不是派蒙数。

现在给定一个，请找出到以内有多少个派蒙数。

输入格式

输入多行。

第一行输入一个正整数，代表有组测试数据。

接下来行，每行输入一个正整数。

输出格式

输出行。

对于每组测试数据，输出到以内有多少个派蒙数。

输入样例

输出样例

数据规模与约定

说明/提示：

对于第一组测试数据：到以内只有一个，该数字的每一位都相同。
对于第六组测试数据：到以内的派蒙数有一共有个。

数据范围：

对于所有的数据范围保证：

。
。

测试点编号
`1 ~ 5`
`6 ~ 10`
`11 ~ 15`
`16 ~ 20`

✅【思路分析】

首先可以直接观察暴力枚举的做法，对于每一个枚举中所有的数字，然后对于每一个数字进行，观察所有位数是否相同。

时间复杂度。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int n;
bool check(int x) {
    int Tmp = x % 10;
    while (x) {
        if (Tmp != (x % 10)) return false;
        x /= 10;
    }
    return true;
}
inline void solve() {
    cin >> n;
    int Ans = 0;
    for (int i = 1; i <= n; i++) {
        if (check(i)) Ans++;
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

很明显这个时间复杂度是超时的，那么观察，可发现对于一位数中有个派蒙数，对于两位数同样也有个派蒙数，对于三位数也是个，所以可以考虑的位数，那么简单的思考结果就是。

但是并没有那么简单，因为无法保证正好是完美的一个位数，这里的完美指的是：

比如一个两位数：的确是有个派蒙数，但是也是，并没有个。

继续观察：

可发现，最高位如果为的时候，并且后面一位是大于的值，那么这个区间肯定是包含这个值的，所以个数其实就是个，分别是。

如果最高位是但是后面一位小于，比如，那么这个区间肯定不会包含这个值，但是会包含这个值，相对于上面的情况会少一个，所以个数就是个，分别是。

还有就是和这种情况，对于前者最高位后面一位甚至两位、三位都是和最高位相等的，但是中途出现了小于最高位的情况，那么也不会包含；对于后者是会出现的情况的。

最后总结下来就是：
求出的位数，对于一个位数，区间肯定存在 $，$ 位数所有的派蒙数，那么这部分的数量就是，那么对于位数来说就可以看看最高位是多少，假设最高位是，这个时候就可以先加上这个，也就是，最后就是检查一下该数字出去最高位一位其他的位数是属于什么情况，这里分为两种：

第一种：从最高位往低位遍历，如果出现了大于最高位的，就可以直接结束，比如上面这种，
第二种：从最高位往低位遍历，如果出现了小于最高位的，就可以将然后直接结束，比如这种。

：在比较的过程中，遇到等于最高位的不用管，直接即可，继续寻找下一位。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
inline void solve() {
    cin >> n;
    string s = to_string(n);
    int Len = s.size();
    int x = s[0] - '0';
    bool ok = true;
    for (auto c : s) {
        if (c - '0' > x) break;
        else if (c - '0' == x) continue;
        else {
            ok = false;
            break;
        }
    }
    if (ok) printf("%d\n", ((Len - 1) * 9) + x);
    else printf("%d\n", ((Len - 1) * 9) + x - 1);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

⏱️【复杂度分析】

时间复杂度：
空间复杂度：

派蒙的规划

题目描述

派蒙和旅行者准备出发距离当前位置米的位置做任务，旅行者将会在秒移动米并且消耗点体力，如果体力消耗完将会死亡，每休息秒旅行者将会恢复点体力，最开始旅行者有点体力。

现在派蒙要给旅行者做前进的规划，派蒙为了保险起见，将会规划秒的行动方式。

请问旅行者按照这个规划前进，是否可以到达任务地点？如果可以输出 Yes ，反之输出 No 。

需要注意，因为旅行者到达地点之后还要做任务，所以不能出现到达任务地点之后体力为的情况，对于这种情况也是输出 No 。

输入格式

输入两行。

第一行输入两个正整数，代表任务地点距离当前位置米，初始体力为。

第二行输入个数字，，如果代表第秒旅行者是休息状态，如果代表第秒旅行者是移动状态。

输出格式

输出一行。

一行输出结果，如果旅行者可以到达任务地点输出 Yes ，反之输出 No 。

输入样例 #1

1 2	10 100 11111111101000000001

输出样例 #1

Yes

输入样例 #2

1 2	15 5 111101110000000000000000000000

输出样例 #2

No

数据规模与约定

说明/提示：

对于样例 #1：旅行者在前面秒前进了米，在第秒休息了秒，在第秒又前进了米，走到了任务地点。
对于样例 #2：旅行者在前面秒前进了米，在第秒休息了秒，之后继续前进，但是在第秒的时候体力消耗完了，导致旅行者死亡，无法到达任务地点。

数据范围：

对于所有的数据范围保证：

。
。

测试点编号
`1 ~ 10`
`11 ~ 15`
`16 ~ 20`

✅【思路分析】

很简单的一个模拟题目。

根据每一秒的行动进行不同的操作，对于第秒为的情况，体力直接增加即可；对于第秒为的情况，需要跑图，这个时候体力会被消耗，既然体力会消耗，就有可能消耗成零，所以消耗完之后检查是否已经为零了，如果没有变成零，就说明可以行动距离，然后检查是否已经走到了距离为的终点目标即可。

对于体力消耗到零的情况直接输出 No ，然后结束程序。

对于到达终点的情况直接输出 Yes ，然后结束程序。

如果秒的操作执行完成，还没有到达终点目标也输出 No 。因为调皮的派蒙和旅行者，想休息就休息，即便体力足够也要休息😝，所以千万不要看着体力比距离大，就直接做特判哦。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int n, x;
char s[N];
inline void solve() {
    cin >> n >> x;
    scanf("%s", s + 1);
    int Len = strlen(s + 1);
    int Ds = 0;
    for (int i = 1; i <= Len; i++) {
        if (s[i] == '1') {
            x--;
            if (x <= 0) {
                printf("No\n");
                return;
            }
            Ds++;
            if (Ds == n) {
                printf("Yes\n");
                return;
            }

        } else {
            x++;
        }
    }
    printf("No\n");
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

⏱️【复杂度分析】

时间复杂度：
空间复杂度：

果壳语法杯ROUND4题解

「果壳语法杯」ROUND #4

派蒙的西瓜

题目描述

输入格式

输出格式

输入样例

输出样例

数据规模与约定

说明/提示：

数据范围：

✅【思路分析】

⏱️【复杂度分析】

派蒙发现的数学题

题目描述

输入格式

输出格式

输入样例

输出样例

数据规模与约定

说明/提示：

数据范围：

✅【思路分析】

⏱️【复杂度分析】

升级旅行者等级

题目描述

输入格式

输出格式

输入样例

输出样例

数据规模与约定

说明/提示：

数据范围：

✅【思路分析】

⏱️【复杂度分析】

派蒙数

题目描述

输入格式

输出格式

输入样例

输出样例

数据规模与约定

说明/提示：

数据范围：

✅【思路分析】

⏱️【复杂度分析】

派蒙的规划

题目描述

输入格式

输出格式

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

数据规模与约定

说明/提示：

数据范围：

✅【思路分析】

⏱️【复杂度分析】