NC275631 嘤嘤不想求异或喵，NC274492 76与61，NC273546 小红的数组移动

目录

NC275631嘤嘤不想求异或喵

题目描述

运行代码

代码思路

ff 函数解释：

主函数解释：

NC27449276与61

题目描述

运行代码

代码思路

函数 countSubsequences 的工作原理：

举例说明：

NC273546小红的数组移动

题目描述

运行代码

代码思路

嘤嘤不想求异或喵

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include <iostream>
using namespace std;
long long ff(long long x) {
    if (x % 4 == 0)
        return x;
    else if (x % 4 == 1)
        return 1;
    else if (x % 4 == 2)
        return x + 1;
    return 0;
}
int main() {
    int n;
    cin >> n;
    while (n--) {
        long long l, r;
        cin >> l >> r;
        cout << (ff(r) ^ ff(l - 1)) << endl;
    }
    return 0;
}

代码思路

ff 函数解释：

ff函数接受一个长整型参数x，并根据x模4的结果返回不同的值：

• 如果x % 4 == 0，则返回x。
• 如果x % 4 == 1，则返回1。
• 如果x % 4 == 2，则返回x + 1。
• 如果x % 4 == 3（虽然没有明确写出来，但根据else结构，实际上是返回0）。

这是因为在异或操作中，数字和它的下一个数字的异或结果有一个模式：

• 0 ^ 1 = 1
• 1 ^ 2 = 3
• 2 ^ 3 = 1
• 3 ^ 4 = 7

但是，对于连续的自然数，我们有：

• 0 ^ 1 ^ 2 ^ 3 = 0 （因为异或是自反的）
• 1 ^ 2 ^ 3 ^ 4 = 4
• 2 ^ 3 ^ 4 ^ 5 = 6
• 3 ^ 4 ^ 5 ^ 6 = 4

所以，当x模4等于0时，从0到x的所有数字异或的结果就是x本身。 当x模4等于1时，从0到x的所有数字异或的结果就是1。 当x模4等于2时，从0到x的所有数字异或的结果就是x + 1。 当x模4等于3时，从0到x的所有数字异或的结果就是0。

主函数解释：

在main函数中，首先读取一个整数n，表示测试用例的数量。然后对于每个测试用例，读取两个长整型l和r，代表一个闭区间[l, r]。接下来，计算从l到r所有数字的异或结果，这通过调用ff(r) ^ ff(l - 1)来实现。这是因为ff(l - 1)会给出从0到l - 1所有数字的异或结果，而ff(r)给出从0到r所有数字的异或结果。两者异或就得到了从l到r所有数字的异或结果。利用了异或操作的性质，即任何数和自身异或结果为0。

NC27449276与61

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include <iostream>
#include <string>

using namespace std;

long long countSubsequences(string s) {
    long long count7 = 0, count76 = 0, count761 = 0;
    for (char c : s) {
        if (c == '7') {
            count7++;
        } else if (c == '6') {
            count76 += count7;
        } else if (c == '1') {
            count761 += count76;
        }
    }
    return count761;
}

int main() {
    string s;
    cin >> s;
    cout << countSubsequences(s) << endl;
    return 0;
}

代码思路

函数 countSubsequences 的工作原理：

1. 初始化计数器：

   • count7 计数字符串中所有单独的 '7'。
   • count76 计数以 '7' 开始且紧接着 '6' 的子序列数量。
   • count761 计数完整的 "761" 子序列数量。

2. 遍历字符串：

   • 对于字符串中的每一个字符 c，检查它是否为 '7', '6', 或 '1'。
   • 如果 c 是 '7'，增加 count7，因为我们发现了一个可能的 "761" 的起始点。
   • 如果 c 是 '6'，增加 count76，增加的数量等于之前找到的所有 '7' 的数量，因为我们现在有 count7 个可能的 "76" 子序列。
   • 如果 c 是 '1'，增加 count761，增加的数量等于之前找到的所有 "76" 子序列的数量，因为我们现在有 count76 个可能的完整 "761" 子序列。

3. 返回结果：

   • 在遍历完字符串后，返回 count761，即 "761" 子序列的总数。

举例说明：

假设输入字符串是 "76716761761"。

• 当遇到第一个 '7' 时，count7 增加至 1。
• 当遇到第一个 '6' 时，count76 增加至 1（因为此时有 1 个 '7'）。
• 当遇到第一个 '1' 时，count761 增加至 1（因为此时有 1 个 "76"）。
• 继续处理，每遇到 '7'，count7 就增加；每遇到 '6'，count76 就加上当前 count7 的值；每遇到 '1'，count761 就加上当前 count76 的值。

最终，count761 将包含 "761" 子序列在原字符串中出现的总次数。这种方法利用了动态规划的思想，每次只关注当前字符和之前的统计结果，从而高效地解决了问题。

NC273546小红的数组移动

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include <iostream>
#include <vector>
#include<string>
using namespace std;
const long long mod = 1e9 + 7;
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n;++i) {
        cin >> arr[i];
    }
    string s;
    cin >> s;
    int score = 0;
    int cur = 0;
    for (char c : s) {
        if (c =='R') {
            if (cur < n - 1) {
                cur++;
            } 
        }
            else if (c =='L') {
                if (cur > 0) {
                    cur--;
                }
            }
            score = (score + arr[cur]) % mod;
        }
        cout << score << endl;
    return 0;
}

代码思路

1. 初始化：

   • 读入一个整数 n，表示数组的长度和字符串的长度。
   • 创建一个大小为 n 的整数向量 arr，用于存储每个位置上的分数。
   • 读入 arr 中的每个元素。
   • 读入一个字符串 s，其中的每个字符表示一次移动指令，'R' 表示向右移动，'L' 表示向左移动。
   • 初始化变量 score 和 cur，其中 score 用于记录累计得分，cur 用于跟踪当前位置。

2. 处理移动指令：

   • 遍历字符串 s 中的每个字符 c。
   • 如果 c 是 'R'，检查当前位置是否小于 n-1（数组最后一个位置的索引），如果是，则将当前位置 cur 增加 1。
   • 如果 c 是 'L'，检查当前位置是否大于 0，如果是，则将当前位置 cur 减少 1。
   • 每次移动后，更新 score，将其加上当前位置 cur 上的分数 arr[cur]，并将结果对 mod 取模以防止溢出。

3. 输出结果：

   • 输出最终的得分 score。

• 数组下标是从0开始的，所以在移动指令中检查边界时，使用 < n - 1 和 > 0。
• 每次计算 score 时都进行取模操作，确保不会发生整数溢出。