前七题的题解：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而已。论课后习题的重要性。
京公网安备 11010502036488号