前七题的题解:https://blog.csdn.net/qq_46144509/article/details/109905618?utm_source=app

C. Pokémon Go

选择每一个出口对所有的点进行bfs,然后取最小值。
如果不知道bfs,建议先学一下bfs模板题。
搬运删去部分后 风竹曦 的代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define rep(i, a, n) for (int i = a; i <= n; i++)

const ll mod = (ll)1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = (int)1e3 + 10;
const int DIR[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
int a[N][N], dis[N][N], vis[N][N];
int n, m, flag = 0;
struct Node {
    int x, y, step;
};
void bfs(int x, int y);
inline bool check(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }

int main() {
    int k;
    cin >> n >> m >> k;
    rep(i, 1, k) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x][y] = 1;
    }
    memset(dis, 0x3f, sizeof dis);
    int t;
    cin >> t;
    rep(i, 1, t) {
        int x, y;
        scanf("%d%d", &x, &y);
        bfs(x, y);
    }

    int p;
    cin >> p;
    rep(i, 1, p) {
        int x, y;
        scanf("%d%d", &x, &y);
        int ans = dis[x][y];
        if (ans >= INF) {
            ans = -1;
        }
        printf("%d\n", ans);
    }

    return 0;
}

void bfs(int x, int y) {
    flag++;
    queue<Node> q;
    q.push({x, y, 0});
    vis[x][y] = flag;
    while (!q.empty()) {
        Node f = q.front();
        q.pop();
        dis[f.x][f.y] = min(dis[f.x][f.y], f.step);
        rep(d, 0, 3) {
            int x0 = f.x + DIR[d][0], y0 = f.y + DIR[d][1];
            if (check(x0, y0) && a[x0][y0] == 0 && vis[x0][y0] != flag) {
                q.push({x0, y0, f.step + 1});
                vis[x0][y0] = flag;
            }
        }
    }
}

B. 跳棋

dfs题。如果直接全排列,12!,会超时。
所以需要剪枝。
经过12打表可以发现,棋盘处于“超平衡状态”的时候,每一条直线的和为(平均值乘以棋子数)。

从序号1开始递归,递归到第6层时检测,a[2],a[3],a[4],a[5]的和不等于26就return

    if (step == 6) {
        if (a[2] + a[3] + a[4] + a[5] != 26) {
            return;
        }
    }

递归到第9层时检测,a[1],a[3],a[6],a[8]的和不等于26就return

    if (step == 9) {
        if (a[1] + a[3] + a[6] + a[8] != 26) {
            return;
        }
    }

然后12层的时候再检测一次

    if (step == 12) {
        if (a[8] + a[9] + a[10] + a[11] != 26) {
            return;
        }

        if (a[1] + a[4] + a[7] + a[11] != 26) {
            return;
        } 
    }

如果是红色棋盘就直接递归下一层

    if (step == 1 || step == 9) {
        dfs(step + 1);
        return;
    }

到第13层时

    if (step == 13) {
        if (a[2] + a[6] + a[9] + a[12] != 26) {
            return;
        }

        if (a[5] + a[7] + a[10] + a[12] != 26) {
            return;
        }

        /*
            存储或者输出
        */
        return;
    }

然后,如果直接每次询问都进行一次dfs,再输出,这个代码还是会超时。先把所有的从12个数中选2个不同的数的全排列写出来,

void init() {
    for (n1 = 1; n1 <= 12; n1++) {
        for (n2 = 1; n2 <= 12; n2++) {
            if (n2 != n1) {
                memset(vis, 0, sizeof(vis));
                a[1] = n1;
                a[9] = n2;
                vis[n1] = vis[n2] = true;

                dfs(1);
            }
        }
    }
}

然后再用一个二维数组dp[13][13]记忆每一种排列的情况。dp里面是一个二维数组,存储该排列情况的所有字典序数组。所以这是一个四维数组。

struct save {
    std::vector<std::vector<int> > v;
};

save dp[13][13];

完整代码就是:

# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>

int a[13];
bool vis[13];

int n1, n2;

struct save {
    std::vector<std::vector<int> > v;
};

save dp[13][13];

void dfs(int step) {
    if (step == 13) {
        if (a[2] + a[6] + a[9] + a[12] != 26) {
            return;
        }

        if (a[5] + a[7] + a[10] + a[12] != 26) {
            return;
        }

        std::vector<int> vp;
        for (int i = 1; i <= 12; i++) {
            vp.push_back(a[i]);
        }
        dp[n1][n2].v.push_back(vp);
        return;
    }

    if (step == 6) {
        if (a[2] + a[3] + a[4] + a[5] != 26) {
            return;
        }
    }

    if (step == 9) {
        if (a[1] + a[3] + a[6] + a[8] != 26) {
            return;
        }
    }

    if (step == 12) {
        if (a[8] + a[9] + a[10] + a[11] != 26) {
            return;
        }

        if (a[1] + a[4] + a[7] + a[11] != 26) {
            return;
        } 
    }

    if (step == 1 || step == 9) {
        dfs(step + 1);
        return;
    }


    for (int i = 1; i <= 12; i++) {
        if (!vis[i]) {
            vis[i] = true;
            a[step] = i;
            dfs(step + 1);

            vis[i] = false;
        }
    }
}

void solve() {
    if (dp[n1][n2].v.size() == 0) {
        puts("-1");
    } else {
        for (int i = 0; i < dp[n1][n2].v.size(); i++) {
            for (int j = 0; j < dp[n1][n2].v[i].size(); j++) {
                printf("%d ", dp[n1][n2].v[i][j]);
            }
            puts("");
        }
    }

    puts("");
}

void init() {
    for (n1 = 1; n1 <= 12; n1++) {
        for (n2 = 1; n2 <= 12; n2++) {
            if (n2 != n1) {
                memset(vis, 0, sizeof(vis));
                a[1] = n1;
                a[9] = n2;
                vis[n1] = vis[n2] = true;

                dfs(1);
            }
        }
    }
}

int main() {
    init();
    while (~scanf("%d%d", &n1, &n2)) {
        solve();
    }

    return 0;
}

此题解的数组维度有点高,并且vector和普通数组混用,因此看懂有点难度。

但似乎有大佬没有记忆化,并且和我的思路差不多,也过了?难道字符串比数组处理要快?
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45659756

本以为超过10000字符的代码牛客不允许提交,结果后来发现可以。暴力打表。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45655689
一千多行代码怎么敲?先把打表的数据输出到txt,然后复制txt里面的内容,粘贴到代码上。
本来一开始我想出事先放三个棋子的,后来想降低难度就只出了放两个棋子的。不知道如果是放三个棋子,打表会不会超过牛客规定的提交代码大小上限。

J. 魔改斐波那契


~~如果没有计算可以允许出现。个人观点,如有不对请指正。~~

如果先将十进制转为二进制再矩阵快速幂可能会超时。所以用10进制的矩阵快速幂。是单位矩阵。

Node decpow(Node x) {
    int len = strlen(s + 1);

    Node base = x;
    Node ans = I;
    for (int i = len; i; i--) {
        ans  = ans * qpow(base, s[i] - '0');
        base = qpow(base, 10);
    }

    return ans;
}

代码整体就是:

# include <iostream>
# include <cstring>
# include <cstdio>

int mod;
const int N = 1e6 + 5;
char s[N];

struct Node {
    int a[3][3];

    Node operator * (const Node& rhs) {
        Node t = {0};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    t.a[i][j] += 1ll * a[i][k] * rhs.a[k][j] % mod;

                    if (t.a[i][j] >= mod) {
                        t.a[i][j] -= mod;
                    }
                }
            }
        }

        return t;
    }
};

const Node I = {1, 0, 0, 0, 1, 0, 0, 0, 1};

Node qpow(Node x, int p) {
    Node ans = I;
    while (p) {
        if (p & 1) {
            ans = ans * x;
        }

        x = x * x;
        p >>= 1;
    }

    return ans;
}

Node decpow(Node x) {
    int len = strlen(s + 1);

    Node base = x;
    Node ans = I;
    for (int i = len; i; i--) {
        ans  = ans * qpow(base, s[i] - '0');
        base = qpow(base, 10);
    }

    return ans;
}

int main() {
    int x0;
    int x1;
    int a;
    int b;

    scanf("%d%d%d%d%s%d", &a, &b, &x0, &x1, s + 1, &mod);

    Node T = {a, b, 1, 1, 0, 0, 0, 0, 1};
    Node ans = decpow(T);
    int res = ((1ll * ans.a[1][0] * x1 % mod + 1ll * ans.a[1][1] * x0 % mod) % mod + 1ll * ans.a[1][2] * 7 % mod) % mod;
    printf("%d\n", res);

    return 0;
}

方法二:斐波那契循环节。
斐波那契数列的模数每隔一段就会重复原来的序列,这个性质被称为皮萨诺周期。“每隔一段”的长度被称为循环节。
下面的代码求的循环节不一定是最小循环节,但也可以作为模数。别问我这代码的原理是什么,我是找的别人的代码

ll lcm(ll a, ll b) {
    return a / std::__gcd(a, b) * b;
}

ll pFac[105][2];
int getFactors(ll n) {
    int pCnt = 0;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i) {
            continue;
        }

        pFac[pCnt][0] = i;
        pFac[pCnt][1] = 0;
        while (n % i == 0) {
            n /= i;
            pFac[pCnt][1]++;
        }

        pCnt++;
    }

    if (n > 1) {
        pFac[pCnt][0] = n;
        pFac[pCnt++][1] = 1;
    }

    return pCnt;
}

int Legendre(ll a, ll p) {
    if (qpow(a, (p - 1) >> 1, p) == 1) {
        return 1;
    }

    return -1;
}

ll find_loop(ll n, ll a = 1, ll b = 1) {
    int cnt = getFactors(n);
    ll c = a * a + b * 4;
    ll ans = 1, record;

    for (int i = 0; i < cnt; ++i) {
        if (pFac[i][0] == 2) {
            record = 3 * 2 * 2;
        } else if (c % pFac[i][0] == 0) {
            record = pFac[i][0] * (pFac[i][0] - 1);
        } else if (Legendre(c, pFac[i][0]) == 1) {
            record = pFac[i][0] - 1;
        } else {
            record = (pFac[i][0] - 1) * (pFac[i][0] + 1);
        }

        for (int j = 1; j < pFac[i][1]; ++j) {
            record *= pFac[i][0];
        }

        ans = lcm(ans, record);
    }

    return ans;
}

int main() {
    ll p = find_loop(mod, a, b);
    return 0;
}    

然后再对大数求模

ll read_mod(ll mod) {
    int len = strlen(s + 1);
    ll n = 0;

    for (int i = 1; i <= len; i++) {
        n = ksc(n, 10, mod) + s[i] - '0';
        if (n >= mod) {
            n -= mod;
        }
    }

    return n;
}

完整版就是:

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

typedef long long ll;
typedef __int128 lll;

const int N = 5e5 + 5;
char s[N];
ll mod;

struct Node {
    ll m[3][3];

    Node operator * (const Node& rhs) {
        Node t = {0};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    t.m[i][j] += m[i][k] * rhs.m[k][j] % mod;

                    if (t.m[i][j] >= mod) {
                        t.m[i][j] -= mod;
                    }
                }
            }
        }

        return t;
    }

};

const Node I = {1, 0, 0, 0, 1, 0, 0, 0, 1};

Node qpow(Node x, ll p) {
    Node ans = I;
    while (p) {
        if (p & 1) {
            ans = ans * x;
        }

        x = x * x;
        p >>= 1;
    }

    return ans;
}

ll qpow(ll x, ll p, int Mod = mod) {
    ll ans = 1 % Mod;
    x %= Mod;
    while (p) {
        if (p & 1) {
            ans = ans * x % Mod;
        }

        x = x * x % Mod;
        p >>= 1;
    }

    return ans;
}

ll lcm(ll a, ll b) {
    return a / std::__gcd(a, b) * b;
}

ll pFac[105][2];
int getFactors(ll n) {
    int pCnt = 0;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i) {
            continue;
        }

        pFac[pCnt][0] = i;
        pFac[pCnt][1] = 0;
        while (n % i == 0) {
            n /= i;
            pFac[pCnt][1]++;
        }

        pCnt++;
    }

    if (n > 1) {
        pFac[pCnt][0] = n;
        pFac[pCnt++][1] = 1;
    }

    return pCnt;
}

int Legendre(ll a, ll p) {
    if (qpow(a, (p - 1) >> 1, p) == 1) {
        return 1;
    }

    return -1;
}

ll find_loop(ll n, ll a = 1, ll b = 1) {
    int cnt = getFactors(n);
    ll c = a * a + b * 4;
    ll ans = 1, record;

    for (int i = 0; i < cnt; ++i) {
        if (pFac[i][0] == 2) {
            record = 3 * 2 * 2;
        } else if (c % pFac[i][0] == 0) {
            record = pFac[i][0] * (pFac[i][0] - 1);
        } else if (Legendre(c, pFac[i][0]) == 1) {
            record = pFac[i][0] - 1;
        } else {
            record = (pFac[i][0] - 1) * (pFac[i][0] + 1);
        }

        for (int j = 1; j < pFac[i][1]; ++j) {
            record *= pFac[i][0];
        }

        ans = lcm(ans, record);
    }

    return ans;
}

inline ll ksc(ll x, ll y, ll mod) {
    x %= mod;
    y %= mod;

    return (lll)x * y % mod;
//    ll tmp = x * y - (ll)((long double)x / mod * y + 1.0e-8) * mod;
//    return tmp < 0 ? tmp + mod : tmp > mod ? tmp -= mod : tmp;
}

ll read_mod(ll mod) {
    int len = strlen(s + 1);
    ll n = 0;

    for (int i = 1; i <= len; i++) {
        n = ksc(n, 10, mod) + s[i] - '0';
        if (n >= mod) {
            n -= mod;
        }
    }

    return n;
}

int main() {
    int a;
    int b;
    int f0;
    int f1;
    scanf("%d%d%d%d%s%lld", &a, &b, &f0, &f1, s + 1, &mod);

    if (mod == 1) {
        std::cout << 0;
        return 0;
    }

    ll p = find_loop(mod, a, b);
    ll n = read_mod(p);

    Node T = {a, b, 1, 1, 0, 0, 0, 0, 1};
    Node ans = qpow(T, n);

    int res = (ans.m[1][0] * f1 % mod + ans.m[1][1] * f0 % mod + ans.m[1][2] * 7 % mod) % mod;
    std::cout << res;

    return 0;
}

对于本校学生,我们来回顾一下劝退课程之 《ACM第四次课20201107》的最后一张PPT:
遗留内容
其中的三个链接:
https://ac.nowcoder.com/acm/contest/885/B
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45482960
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45482976
发现没有?就是多加了一个7而已。论课后习题的重要性。