ShanDong Multi-University Training ＃4 A、B、C、G

A

或运算，1不是题意下的质数，其他和均是质数，剩下的不是

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

LL lowbit(LL x) {
    return x & -x;
}

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

    LL n;
    cin >> n;
    LL x = n;
    int cnt = 0;
    LL y = lowbit(n);
    while (x) {
        if (x & 1) {
            cnt++;
        }
        x >>= 1;
    }
    if (cnt == 1) {
        if (n == 1) {
            cout << "No\n";
        }
        else {
            cout << "Yes\n";
        }
    }
    else if (cnt == 2) {
        if (y == 1) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }
    else {
        cout << "No\n";
    }

    return 0;
}

B

可知要得，可得到,n是1e5但异或值域只有不到2e5，那么根据鸽巢原理暴力跑即可

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;



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

    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (mp[a[i] ^ a[j]] == 1) {
                cout << "Yes\n";
                return 0;
            }
            mp[a[i] ^ a[j]] = 1;
        }
    }
    cout << "No\n";

    return 0;
}

C

大数取模模拟，因为它我才知道我的大数取模模板的取模运算锅了QAQ

AC代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <numeric>
#include <functional>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;
//head

const LL mod = 1e9 + 7;
LL a[200010];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int len = s.size();
    s = '*' + s;
    int q;
    cin >> q;
    LL sum = 0;
    for (int i = 1; i <= len; i++) {
        sum = a[i - 1];
        a[i] = (sum * 10 + (LL)(s[i] - '0')) % mod;
    }
    rep (i, 0, q) {
        string op;
        cin >> op;
        int x;
        if (op == "+") {
            cin >> x;
            sum = a[len];
            len++;
            a[len] = (sum * 10 + x) % mod;
            cout << a[len] << '\n';
        }
        else {
            len--;
            cout << a[len] << '\n';
        }
    }

    return 0;
}

G

数位DP板板题，先找Fibonacci数列的规律，可以猜到的是所有Fibonacci数列里的数都是包含1、2、3、5、8的，那么就有了数位DP的基础，就是不要1、2、3、5、8，统计0到n有多少个这样的数

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

LL dp[20][20], w[20], cnt = 0;
LL getfib(LL x) {
    if (x == 1) {
        return 1;
    }
    if (x == 0) {
        return 0;
    }
    return getfib(x - 1) + getfib(x - 2);
}
LL dfs(int x, int p, int flag) {//1 2 3 5 8->p=0or1
    if (x < 0) {
        return p == 0;
    }
    if (dp[x][p] != -1 && !flag) {
        return dp[x][p];
    }
    int lim = flag ? w[x] : 9;
    LL ans = 0;
    for (int i = 0; i <= lim; i++) {
        if (i == 1) {
            if (p == 0) {
                ans += dfs(x - 1, 1, flag && (i == lim));
            }
            else {
                continue;
            }
        }
        else if (i == 2) {
            if (p == 0) {
                ans += dfs(x - 1, 1, flag && (i == lim));
            }
            else {
                continue;
            }
        }
        else if (i == 3) {
            if (p == 0) {
                ans += dfs(x - 1, 1, flag && (i == lim));
            }
            else {
                continue;
            }
        }
        else if (i == 5) {
            if (p == 0) {
                ans += dfs(x - 1, 1, flag && (i == lim));
            }
            else {
                continue;
            }
        }
        else if (i == 8) {
            if (p == 0) {
                ans += dfs(x - 1, 1, flag && (i == lim));
            }
            else {
                continue;
            }
        }
        else {
            if (p == 0) {
                ans += dfs(x - 1, 0, flag && (i == lim));
            }
            else {
                continue;
            }
        }
    }
    if (!flag) {
        dp[x][p] = ans;
    }
    return ans;
}
void Solve() {
    LL n;
    cin >> n;
    cnt = 0;
    while (n) {
        w[cnt] = n % 10;
        cnt++;
        n /= 10;
    }
    cnt--;
    memset(dp, -1, sizeof(dp));
    cout << dfs(cnt, 0, 1) << '\n';
}

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

    int T;
    cin >> T;
    // for (int i = 0; i <= T; i++) {
    //     cout << getfib(i) << '\n';
    // }
    rep (i, 0, T) {
        Solve();
    }

    return 0;
}