P10571 [JRKSJ R8] 三七二十一 题解

Little_x_starTYJ · 2024-06-13 14:58:53 · 题解

解题思路

为了不让数字串中出现 2 的非负整数次幂，那么 1,2,4,8 必须得删去，于是写出了以下代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans;
signed main() {
    ios::sync_with_stdio(false);
    string a;
    cin >> a;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '1' || a[i] == '2' || a[i]== '4' || a[i] == '8')
            ans++;
    }
    cout << ans;
    return 0;
}

交上去发现只有 10 分。为什么只有 10 分？会不会有特殊情况？于是打了一个表，发现 2^k(k\in \N) 只有 65536 不包含 1,2,4,8，所以我们还需要单独处理 65536。需要注意的是，对于两个重叠的 65536，我们只需要删掉 1 个数，例如 655365536，我们只需要删除最中间的 6。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans;
signed main() {
    ios::sync_with_stdio(false);
    string a;
    cin >> a;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '6' && a[i + 1] == '5' && a[i + 2] == '5' && a[i + 3] == '3' && a[i + 4] == '6')
            ans++, i += 4;
    }
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '1' || a[i] == '2' || a[i]== '4' || a[i] == '8')
            ans++;
    }
    cout << ans;
    return 0;
}