洛谷解题日记||基础篇2

题目链接

0 = 剪刀，1 = 石头，2 = 布，3 = 蜥蜴人，4 = 斯波克
我们可以根据题意，构建一个二维矩阵 result[5][5] 来表示每一种出拳的胜负情况。

#include <iostream>
#include <vector>
using namespace std;int main() {int N, N_A, N_B;cin >> N >> N_A >> N_B;vector<int> A(N_A), B(N_B);for (int i = 0; i < N_A; i++) {cin >> A[i];}for (int i = 0; i < N_B; i++) {cin >> B[i];}// 胜负关系表：result[a][b]表示a和b的对决结果int result[5][5] = {{0, 0, 1, 1, 0},{1, 0, 0, 1, 0},{0, 1, 0, 0, 1},{0, 0, 1, 0, 1},{1, 1, 0, 0, 0}};int score_A = 0, score_B = 0;for (int i = 0; i < N; i++) {//保证a,b的值在各自的周期内int a = A[i % N_A];int b = B[i % N_B];if (result[a][b] == 1) {  //先判断a是否赢再判断b是否赢score_A++;} else if (result[b][a] == 1) {score_B++;}}cout << score_A << " " << score_B << endl;return 0;
}

#include <iostream>
#include <cstring>
using namespace std;int win[62503];  // 存储每回合的比赛结果，1 为华华胜，2 为对手胜 最大为25*2500=62500
int w, l;  // w 为华华得分，l 为对手得分int main() {char s;// 读取比赛结果，直到遇到字符 'E'for(int i = 1; cin >> s && s != 'E'; i++) {if(s == 'W') win[i] = 1;  // 华华胜else win[i] = 2;  // 对手胜}//---------------- 11 分制 ----------------w = 0; l = 0;  // 初始化比分for(int i = 1; ; i++) {if(win[i] == 1) w++;  // 华华得分if(win[i] == 2) l++;  // 对手得分// 判断是否读到 '0'，即比赛结束if(win[i] == 0) {cout << w << ":" << l << endl << endl;  // 输出当前比分break;  // 结束 11 分制部分}// 判断 11 分制结束的条件if(w - l >= 2 || l - w >= 2) {if(w >= 11 || l >= 11) {  // 一方得分大于等于 11 且领先至少 2 分cout << w << ":" << l << endl;  // 输出当前比分w = 0;  // 比分清零，开始下一局l = 0;}}}w = 0; l = 0;  // 清零，为 21 分制做准备//---------------- 21 分制 ----------------for(int i = 1; ; i++) {if(win[i] == 1) w++;  // 华华得分if(win[i] == 2) l++;  // 对手得分// 判断是否读到 '0'，即比赛结束if(win[i] == 0) {cout << w << ":" << l;  // 输出最后一局的比分break;  // 结束 21 分制部分}// 判断 21 分制结束的条件if(w - l >= 2 || l - w >= 2) {if(w >= 21 || l >= 21) {  // 一方得分大于等于 21 且领先至少 2 分cout << w << ":" << l << endl;  // 输出当前比分w = 0;  // 比分清零，开始下一局l = 0;}}}return 0;  // 结束程序
}

代码解释：

输入和存储：
- 通过 cin >> s 循环读取每回合的比赛结果。字符 'W' 表示华华获胜，'L' 表示对手获胜，'E' 表示输入结束。
- 每个回合的比赛结果存储在 win 数组中，win[i] = 1 表示华华胜，win[i] = 2 表示对手胜。
11 分制规则：
- 比赛中如果一方的得分大于等于 11 且领先至少 2 分，就输出该局的比分并清零比分，开始下一局。
- 如果遇到字符 '0'（即比赛结束标志），则输出当前比分并结束 11 分制部分。
21 分制规则：
- 21 分制与 11 分制类似，但规则要求一方得分达到 21 且领先至少 2 分才能结束局，并清零比分。
- 同样，遇到字符 '0' 时结束并输出最后比分。

关键点总结：

win[i] 的赋值过程在输入读取时进行：'W' 对应 1，'L' 对应 2。
win[i] 的值并不是手动设置为 0，而是因为输入流被终止，程序不再读取新的字符。
当读取到 'E' 时，输入流结束，程序停止继续读取比赛数据。
程序通过 win[i] == 0 来确定比赛输入的结束，然后停止比赛结果的输出。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 判断是否可以通过删除至多 M 个岩石来保证最小跳跃距离不小于 minJump
bool canAchieveMinJumpDistance(const vector<int>& rocks, int L, int M, int minJump) {int removed = 0;  // 用来统计删除的岩石数量int lastPosition = 0;  // 起点的位置// 从第一个岩石开始遍历for (int i = 1; i < rocks.size(); ++i) {if (rocks[i] - lastPosition < minJump) {// 如果当前岩石和上一个岩石之间的跳跃距离小于 minJump，就需要删除当前岩石removed++;} else {// 否则，我们跳到这个岩石，更新 lastPositionlastPosition = rocks[i];}// 如果删除的岩石数超过了 M，就说明当前 minJump 不可行if (removed > M) {return false;}}// 最后检查从最后一个岩石到终点的距离if (L - lastPosition < minJump) {removed++;}return removed <= M;
}int main() {int L, N, M;cin >> L >> N >> M;vector<int> rocks(N + 2);  // +2 是因为我们还要考虑起点0和终点Lrocks[0] = 0;  // 起点for (int i = 1; i <= N; ++i) {cin >> rocks[i];}rocks[N + 1] = L;  // 终点// 二分查找最小的最大跳跃距离int low = 1, high = L;int answer = 0;while (low <= high) {int mid = low + (high - low) / 2;  // 中间值if (canAchieveMinJumpDistance(rocks, L, M, mid)) {answer = mid;  // 如果可以达到这个最小跳跃距离，记录下来low = mid + 1; // 尝试更大的最小跳跃距离} else {high = mid - 1; // 尝试更小的最小跳跃距离}}cout << answer << endl;  // 输出最终的答案return 0;
}

L 是终点的坐标。
N 是岩石的数量。
M 是你可以删除的岩石的最大数量。

接下来，我们用一个 vector<int> 来存储所有的岩石的位置，rocks[0] = 0 表示起点，rocks[N + 1] = L 表示终点。

`2canAchieveMinJumpDistance` 函数：

这个函数的作用是判断，给定一个 minJump，是否可以通过删除至多 M 个岩石来保证从起点到终点的跳跃距离都不小于 minJump。

bool canAchieveMinJumpDistance(const vector<int>& rocks, int L, int M, int minJump) {int removed = 0;  // 统计删除的岩石数量int lastPosition = 0;  // 起点的位置// 遍历岩石位置for (int i = 1; i < rocks.size(); ++i) {if (rocks[i] - lastPosition < minJump) {// 如果当前岩石和上一个岩石之间的距离小于 minJump，就删除当前岩石removed++;} else {// 否则，跳到这个岩石，更新 lastPositionlastPosition = rocks[i];}// 如果删除的岩石数超过 M，返回 falseif (removed > M) {return false;}}// 最后检查从最后一个岩石到终点的距离if (L - lastPosition < minJump) {removed++;}return removed <= M;
}

removed 用来统计已经删除的岩石数。
lastPosition 表示上一个能够跳跃的岩石的位置。
遍历所有岩石，对于每一个岩石，如果它和前一个岩石之间的跳跃距离小于 minJump，那么就考虑删除这个岩石（即 removed++）。
如果删除的岩石数大于 M，那么就返回 false，表示无法满足要求。
最后还需要检查从最后一个岩石到终点之间的距离，若小于 minJump 也需要删除。

3. 二分查找最小的最大跳跃距离：

为了找到最小的最大跳跃距离，我们使用二分查找。

int low = 1, high = L;
int answer = 0;while (low <= high) {int mid = low + (high - low) / 2;  // 计算中间值if (canAchieveMinJumpDistance(rocks, L, M, mid)) {answer = mid;  // 如果可以达到这个最小跳跃距离，记录下这个距离low = mid + 1; // 尝试更大的最小跳跃距离} else {high = mid - 1; // 尝试更小的最小跳跃距离}
}