前七題的題解: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
+
12
2
?
4
=
26
\frac{1+12}{2}*4=26
21+12??4=26”(平均值乘以棋子數),
從序號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. 魔改斐波那契
( f n + 1 f n 0 f n f n ? 1 0 c c c ) = ( a b 1 1 0 0 0 0 1 ) ? ( f n f n ? 1 0 f n ? 1 f n ? 2 0 c c c ) = . . . \begin{pmatrix} f_{n+1} & f_{n} & 0 \\ f_{n} & f_{n-1} & 0 \\ c & c & c \end{pmatrix} = \begin{pmatrix} a & b & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} * \begin{pmatrix} f_{n} & f_{n-1} & 0 \\ f_{n-1} & f_{n-2} & 0 \\ c & c & c \end{pmatrix} =... ???fn+1?fn?c?fn?fn?1?c?00c????=???a10?b00?101????????fn?fn?1?c?fn?1?fn?2?c?00c????=...
=
(
a
b
1
1
0
0
0
0
1
)
n
?
(
f
1
f
0
0
f
0
f
?
1
0
c
c
c
)
= { \begin{pmatrix} a & b & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}}^n * \begin{pmatrix} f_{1} & f_{0} & 0 \\ f_{0} & f_{-1} & 0 \\ c & c & c \end{pmatrix}
=???a10?b00?101????n????f1?f0?c?f0?f?1?c?00c????
如果沒有計算
f
?
1
f_{-1}
f?1?可以允許出現
f
?
1
f_{-1}
f?1?,個人觀點,如有不對請指正,
如果先將十進制轉為二進制再矩陣快速冪可能會超時,所以用10進制的矩陣快速冪, I I I是單位矩陣,
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而已,論課后習題的重要性,
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/226845.html
標籤:其他
上一篇:[STL]空間配置器的原理
下一篇:VHDL撰寫二位數值比較器
