牛客小白月赛118 A-C 题解

牛客小白月赛118 A-C 题解

题目链接：https://ac.nowcoder.com/acm/contest/111666

A题

签到，直接模拟即可

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int x, y;
  cin >> x >> y;

  if (x == y) cout << "Draw\n";
  else if ((x == 0 && y == 1) || (x == 1 && y == 2) || (x == 2 && y == 0))
    cout << "Hongwins\n";
  else
    cout << "chengwins\n";

  return 0;
}

B题

从题目描述“可以改成任意大于 1 的数”，意味着任何一组都可以改成合法序列，目标是使得所有相邻元素都是互质的，也就是 gcd(a[i], a[i+1]) == 1​ 对于所有 1 <= i < n​ 都成立。我们可以​从左往右扫​，每遇到一对不互质，就“修复”这个对：

• 贪心地选择​修改右边 a[i+1] ​（这样不影响已经处理的 a[i-1]）
• 修改后跳过下一对，这样一次修改可以影响两个对。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll gcdll(ll a, ll b) {
    while (b) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<ll> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        int res = 0;
        int i = 0;
        while (i < n - 1) {
            if (gcdll(a[i], a[i + 1]) != 1) {
                // 修改a[i+1]
                res++;
                i += 2; // 跳过下一个边，因为a[i+1]修改后，两个相邻边都解决了
            } else {
                i++;
            }
        }

        cout << res << "\n";
    }

    return 0;
}

C题

在此题中，全为0或1，所以每个字符串每个数字都是相同的实际上每个位置都有选和不选的两种可能，但需要减掉一种全不选为空的情况，所以答案就是$2^{|s|\times n}-1，|s|$表示$s$的长度。需要注意$n$比较大，如果使用的是$longlong$会出现溢出，所以可以考虑分两次快速幂来计算,

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

typedef long long ll;
const ll mod = 1e9 + 7;

// 快速幂：计算 a^b % mod
ll qpow(ll a, ll b) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    ll n;
    string s;
    cin >> n >> s;
    ll base = qpow(2, s.size());      // 计算 2^|s|
    ll ans = qpow(base, n);           // 再计算 (2^|s|)^n = 2^{|s|*n}
    ans = (ans - 1 + mod) % mod;      // 减 1，注意加 mod 防止负数
    cout << ans << '\n';
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}