A Alice and Bob

题目解释

博弈论简单题，NIM游戏。问从两堆里面一次一堆取k个另一堆取k*s个，谁先不能取就输。

题目理解

当时看到题，知道是博弈论，不会算SG函数，没了。这题其实就是暴力算SG函数打表就能过（std还有一种找规律的方法），根据SG函数的定义枚举s这个倍数以及每一个k，开一个vis数组记录哪些方案被枚举到了（理解就是倒着枚举子方案，其实这题不需要真的算出来sg，只需要知道定义就行了），最后没被枚举到的方案就是必输，枚举到的就是必胜。

代码

ps：这个代码直接跑会t，需要先用代码跑出结果然后直接打表

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 5000 + 10;
const int mod = 1e9 + 7;
int sg[N][N], vis[N][N];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void calsg(int n, int m) {
    for (int i = 1; n + i <= 5000; i++) {
        for (int s = 0; m + s * i <= 5000; s++) {
            vis[n + i][m + s * i] = 1;
        }
    }
    for (int i = 1; m + i <= 5000; i++) {
        for (int s = 0; n + s * i <= 5000; s++) {
            vis[n + s * i][m + i] = 1;
        }
    }
}

void solve() {
    int n, m;
    read(n);
    read(m);
    if (vis[n][m]) printf("Alice\n");
    else printf("Bob\n");

}

int main() {
    int n;
    read(n);
    memset(vis, 0, sizeof vis); // 记录哪些子局面被访问到了，最后用于计算MEX操作的值
    for (int i = 0; i <= 5000; i++) {
        for (int j = 0; j <= 5000; j++) {
            if (!vis[i][j]) calsg(i, j);
        }
    }
    for (int i = 1; i <= n; i++)
        solve();
    return 0;
}

D Determine the Photo Position

题目解释

就是问匹配指定数量的字符串方案数量。开场的时候sb了，乍一看以为是匹配0的个数，写了半天，交了，T了。后面改了下计算方法就A了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <map>
#include <cmath>

using namespace std;
typedef long long ll;
const int N = 2000 + 10;
int n, m;
int mxa[N][N], mxb[N], zeros[N];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void solve() {
    memset(zeros, 0, sizeof zeros);
    int cur = -1, last = -1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        int lscur = 0;
        cur = -1, last = -1;
        string str;
        cin >> str;
        bool fl = false;
        for (int j = 0; j < n; j++) {
            cur = str[j] - '0';
            if (cur == 0 && !fl) {
                fl = true;
                lscur++;
                last = cur;
                if (m == 1) cnt++;
                continue;
            }
            if (j == 0) {
                last = cur;
                continue;
            }
            if (cur == 0 && last == 0) {
                lscur++;
                if (lscur >= m) cnt++;
            } else if (cur != 0) {
                lscur = 0;
                fl = false;
            }
            last = cur;
        }
    }
    string str;
    cin >> str;
    cout << cnt;
}

int main() {
    read(n);
    read(m);
    // for (int i = 0; i < n; i++) read(a[i]);
    //for (int i = 0; i < n; i++)
    solve();
    return 0;
}

F Find 3-friendly Integers

题目解释

题目定义了一种数字，只要一个数中的任何一个子串是3的倍数就说属于这种数，问在给定的n范围内有多少个这样的数。

题目理解

这题有两种做法，一种是数位dp，一种是找规律，数位dp做法另外在后面的数位专题里补，这里用规律A。可以发现，100之后的数全都满足题目要求，因此只需要暴力模拟100之前的数就行。

代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <map>
#include <cmath>

using namespace std;
typedef long long ll;
const int N = 20 + 10;
int n, m;
int mxa[N][N], mxb[N], zeros[N];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void solve() {
    ll l, r;
    ll cntl = 0, cntr = 0, last = 0;
    cin >> l >> r;
    ll dp[N][5] = {0};
    if (l > 100) {
        cout << r - l + 1 << endl;
        return;
    } else {
        last = l - 1;
        for (int k = 1; k <= last; k++) {
            string sz = to_string(k);
            memset(dp, 0, sizeof dp);
            bool flag = false;
            for (int i = 1; i <= sz.size(); i++) {
                dp[i][(sz[i - 1] - '0') % 3] = 1;
                for (int j = 0; j < 3; j++) {
                    dp[i][j] += dp[i - 1][j];
                    dp[i][j] += dp[i - 1][(j + 15 - (sz[i - 1] - '0')) % 3];
                    if (dp[i][0]) {
                        flag = true;
                        cntl++;
                        break;
                    }
                }
                if (flag) break;
            }
        }
        if (r <= 100) {
            last = r;
            for (int k = 1; k <= last; k++) {
                string sz = to_string(k);
                memset(dp, 0, sizeof dp);
                bool flag = false;
                for (int i = 1; i <= sz.size(); i++) {
                    dp[i][(sz[i - 1] - '0') % 3] = 1;
                    for (int j = 0; j < 3; j++) {
                        dp[i][j] += dp[i - 1][j];
                        dp[i][j] += dp[i - 1][(j + 15 - (sz[i - 1] - '0')) % 3];
                        if (dp[i][0]) {
                            flag = true;
                            cntr++;
                            break;
                        }
                    }
                    if (flag) break;
                }
            }
            cout << cntr - cntl << endl;
            return;
        } else {
            cout << r - 100 + 76 - cntl << endl;
        }
    }
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++)
        solve();
    return 0;
}

H Hash Function