第 4 场 小白入门赛

发表于 更新于 分类于 阅读次数： 本文字数： 406 阅读时长 ≈ 1 分钟
Better be the head of a dog than the tail of a lion.

A. 美丽的2024

思路：

  • 直接运用 __builtin_popcount() 这个库函数可以直接得到一个十进制数转 2 进制中 1 的个数

时间复杂度：\(O(logn)\)

1
2
3
4
5
6
7
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cout << __builtin_popcount(2024) << "\n";
    return 0;
}

B. 自助餐

思路：

  • 打表即可

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::unordered_map<std::string, int> h{{"yuanxing", 1}, {"zhengfangxing", 2},
     {"changfangxing", 3}, {"sanjiaoxing", 4}, {"tuoyuanxing", 5}, {"liubianxing", 6}};

    int n;
    std::cin >> n;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        if (h.count(s)) {
            ans += h[s];
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

C. 玩游戏

思路：

  • A的必胜态为石子个数为奇数的情况
  • B的必胜态为石子个数为偶数的情况
  • 无论怎么分，只要石子的个数为奇数，那么A一定可以拿到最后一个，反之，偶数的情况，B一定可以拿最后一个

时间复杂度：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    if (n & 1) {
        std::cout << "A\n";
    } else {
        std::cout << "B\n";
    }

    return 0;
}

D. 乘飞机

思路：

  • 只要在 [l, r]这个区间中，那么一定最多只会出现100个数相差大于365，只要这100个数以外的其他数，一定是满足条件的
  • 所以暴力枚举即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def check(ages, l, r):
    # 对给定区间内的年龄进行排序
    sorted_ages = sorted(ages[l-1:min(r, l + 100)])

    left = 0
    right = 1
    while right < len(sorted_ages):
        if abs(sorted_ages[right] - sorted_ages[left]) <= 365:
            return "YES"
        left += 1
        right += 1
    if r > l + 100:
        return "YES"
    else:
        return "NO"

n, q = map(int, input().split())
ages = list(map(int, input().split()))

for _ in range(q):
    l, r = map(int, input().split())
    print(check(ages, l, r))