ZZJC新生训练赛第一场题解

Proaes / 2024-09-28 / 原文

先给出比赛链接：
https://ac.nowcoder.com/acm/contest/91452

下面说一下难度分层：(同一难度下按字典序排序)
Easy(简单): B, F

Medium(中等): A, E, H

Hard(困难): C, G

Anti-AK(防AK): D, I

cin.tie(nullptr)->sync_with_stdio(false); / /加速输入输出的

A 游游的整数翻转

将所给数前k位进行翻转即可，注意要去掉前导0

我的做法是根据k切片，前一块转成int类型自动去前导0（只有数字小到能够用int表示才能这样）

Show Code A


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    string s;
    int k;
    cin >> s >> k;
    string s1 = s.substr(0, k), s2 = s.substr(k); // 切片，详见ACM notes博客
    reverse(s1.begin(), s1.end()); // 翻转字符串
    int ans1 = stoi(s1); // stoi可以把string转成int，此处用于int自动去前导零
    cout << ans1 << s2 << "\n";
}

B 困难数学题

先介绍一下异或的性质

异或及其性质

异或在C++中的运算符是 ^ (Shift + 6)

异或可以理解为按位不进位加法

1.异或的逆运算就是异或本身如果 a $ \otimes $ b = c ，那么 c $ \otimes $ b = a

2.异或满足交换律即 a $ \otimes $ b == b $ \otimes $ a

3.异或满足结合律即 (a $ \otimes $ b) $ \otimes $ c == a $ \otimes $ (b $ \otimes $ c)

4.异或满足分配律即 a $ \otimes $ (b & c) == (a $ \otimes $ b) & (a $ \otimes $ c)

对于普通加法可以用高斯定律 sn = (1 + n) * n / 2 快速计算1~n的值

对于异或运算来说也有快速计算1~n各数的异或和的方法，即：

异或前缀和

$ s(n)为1到n的数的异或和 $

$ s(n) = \begin{cases} 1 , ~~~ n \% 4 == 1 \\ 0 , ~~~ n \% 4 == 3 \\ n , ~~~ n \% 4 == 0 \\ n + 1 , ~~~ n \% 4 == 2 \\ \end{cases} $

代码实现如下：

auto xorprefix = [&](ll n) {
    int flag = n % 4;
    if (flag == 0) {
        return n;
    } else if (flag == 1) {
        return 1;
    } else if (flag == 2) {
        return n + 1;
    } else if (flag == 3) {
        return 0;
    }
};

根据异或的性质，我们可以知道 a xor a = 0
那么 a xor a xor a xor a = 0
所以直接输出0即可

Show Code B


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << 0 << "\n";
}

C 小红的完全平方数

用二分找到第一个比x小的完全平方数，由于x只能+2或者-2，根据x和二分到的完全平方数的奇偶性得到与x最接近的完全平方数再求值即可

Show Code C


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n;
    cin >> n;
    auto check = [&](ll x) {
        if (x * x >= n) {
            return 1;
        } else {
            return 0;
        }
    };
    ll l = 1, r = 2000000;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    ll ans = inf, cur;
    if (r % 2 != n % 2) r--;
    cur = abs(r * r - n) / 2ll;
    ans = min(ans, cur);
    r += 2;
    cur = abs(r * r - n) / 2ll;
    ans = min(ans, cur);
    cout << ans  << "\n";
}

E 回文对称数

输出1到n之间所有的回文数

直接暴力遍历，对每个数判断是否是回文数即可

复杂度 $ O(nlg(n)) $

Show Code E


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        string cur = to_string(i);
        string recur = cur;
        reverse(recur.begin(), recur.end());
        if (cur == recur) {
            cout << cur << "\n";
        }
    }
}

F 小红的新周赛

把六个数加起来输出即可

Show Code F


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n = 6;
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        int cur;
        cin >> cur;
        ans += cur;
    }
    cout << ans << "\n";
}

G 小红小紫投硬币

打表可以发现答案只可能是0.5

下证充分性：

根据古典概型

总共有 $ (n + 1) * (n + 2) $ 种情况

总共有小红正面多的情况有 $ (n + 1) * (n + 2) / 2 $ 种

除一下可知答案恒定为0.5

Show Code G


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << "0.500000" << "\n";
}

H 等差数列

根据题目模拟即可

注意到当 a 和 k 都是偶数的时候，所有项都是偶数
当 k 是偶数的时候，所有项都和a的奇偶性相同
当 k 是奇数的时候，根据 a 和区间的长度 len 就能知道哪种数多了

Show Code H


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll a, k, q;
    cin >> a >> k >> q;
    if (k & 1) {
        while (q--) {
            ll l, r;
            cin >> l >> r;
            ll len = r - l + 1ll;
            if (len & 1) {
                // 注意下面的if里面直接算由于数字太大会爆ll，所以除2取模只计算奇偶性
                if ((a % 2 + (l - 1ll) % 2 * k % 2) & 1) {
                    cout << 1 << "\n";
                } else {
                    cout << -1 << "\n";
                }
            } else {
                cout << 0 << "\n";
            }
        }
    } else {
        if (a & 1) {
            while (q--) cout << 1 << "\n";
        } else {
            while (q--) cout << -1 << "\n";
        }
    }
}