15天前

### 例题1 编辑距离 传送门

dp[i][j]：所有将a中的前i个字母变成 b中前j个字母的集合的操作次数

1. 在该字母之后添加: dp[i][j] = dp[i][j-1] + 1
2. 删除该字母: dp[i][j] = dp[i-1][j] + 1
3. 替换该字母: dp[i][j] = dp[i-1][j-1] + 1
4. 啥也不做(对应结尾字母相同): dp[i][j] = dp[i-1][j-1]

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
char s1[N], s2[N];
int dp[N][N];

int edit_distance(char s1[], char s2[], int n, int m)
{
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) dp[0][i] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
return dp[n][m];
}

int main()
{
cin >> s1 + 1;
cin >> s2 + 1;
int n = strlen(s1 + 1);
int m = strlen(s2 + 1);

cout << edit_distance(s1, s2, n, m);
}


### 例题2 禁止字符串

trans[i][j]：在S[1…i]添加字符cho[j]后（新串T）, 满足 T的后缀 和 S的前缀 相等的最大长度
dp[i][j]：当前构造字符串P长度为i，满足𝑃[𝑖 −𝑗+1…𝑖]=𝑆[1…𝑖]的方案数

//禁止字符串
#include <bits/stdc++.h>

using namespace std;

const int K = 110;
const int N = 10010;
const int C = 5;
const int mod = 10009;

int n, k;
string cho = "AGCT", s;

//trans[i][j]:当前已经匹配i个字符,添加字符cho[j]后,匹配的字符个数
int trans[K][C];
//dp[i][j]:当当前字符串长度为i,状态j结尾的方案数
int dp[N][K];

int main()
{
cin >> n >> k;
cin >> s;

//预处理trans
memset(trans, 0, sizeof trans);
for (int i = 0; i < k; i++)
{
string tmp = s.substr(0, i);
for (int j = 0; j < 4; j++)
{
string cur = tmp + cho[j];
while (s.substr(0, cur.length()) != cur)
cur = cur.substr(1);
trans[i][j] = cur.length();
}
}

//计算dp
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
for (int c = 0; c < 4; c++)
{
int ne = trans[j][c];
if (ne == k) continue;
dp[i + 1][ne] = (dp[i + 1][ne] + dp[i][j]) % mod;
}

//计算总方案数
int tot = 0;
for (int i = 0; i < k; i++)
tot = (tot + dp[n][i]) % mod;
cout << tot << endl;

return 0;
}


### 例题3 DNA repair 传送门

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

using namespace std;

typedef long long ll;

const int N = 55;
const int S = 1010;

int n, cas;
string s, p[N], cho = " AGCT";
bool flag[S];
int trans[S][5], dp[S][S];

int main()
{
ios::sync_with_stdio(false);

while (cin >> n && n)
{
for (int i = 1; i <= n; i++)
{
cin >> p[i];
p[i] = " " + p[i];
}
cin >> s; s = " " + s;

vector<string>pre;
pre.push_back(" ");
for (int i = 1; i <= n; i++)
for (int j = 1; j < p[i].length(); j++)
pre.push_back(" " + p[i].substr(1, j));
stable_sort(pre.begin(), pre.end());
pre.erase(unique(pre.begin(), pre.end()), pre.end());
int m = (int)pre.size() - 1;

for (int i = 0; i <= m; i++) flag[i] = 1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
int lens = pre[i].length(), lent = p[j].length();
if (lens >= lent && pre[i].substr(lens - lent + 1) == p[j].substr(1))
{
flag[i] = 0;
break;
}
}

for (int i = 0; i <= m; i++)
for (int j = 1; j <= 4; j++)
{
string ne = pre[i] + cho[j];
while (true)
{
int pos = lower_bound(pre.begin(), pre.end(), ne) - pre.begin();
if (pos <= m && pre[pos] == ne)
{
trans[i][j] = pos;
break;
}
ne = " " + ne.substr(2);
}
}

int lens = (int)s.length() - 1;
for (int i = 0; i <= lens; i++)
for (int j = 0; j <= m; j++)
dp[i][j] = 0x3f3f3f3f;
dp[0][0] = 0;
for (int i = 0; i < lens; i++)
{
for (int j = 0; j <= m; j++)
{
if (dp[i][j] == 0x3f3f3f3f) continue;
for (int k = 1; k <= 4; k++)
{
int st = trans[j][k];
if (flag[st] == 0) continue;

if (s[i + 1] == cho[k]) dp[i + 1][st] = min(dp[i + 1][st], dp[i][j]);
else dp[i + 1][st] = min(dp[i + 1][st], dp[i][j] + 1);
}
}
}

int mi = 0x3f3f3f3f;
for (int i = 0; i <= m; i++) mi = min(mi, dp[lens][i]);
if (mi == 0x3f3f3f3f) mi = -1;
printf("Case %d: %d\n", ++cas, mi);
}

return 0;
}


### 习题1 Easy Problem 传送门

dp[i][j]:当前处理位置为i, 包含t.subtr(1, i)子序列的最大权值和

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

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n, fare[N];
char s[N], t[10] = " hard";
//dp[i][j]:当前处理位置为i, 包含t.subtr(1, i)子序列的最大权值和
ll dp[N][5];

int main()
{
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) scanf("%d", &fare[i]);

ll sum = 0;
for (int i = 1; i <= n; i++) sum += fare[i];

for (int i = 1; i <= n; i++)
{
if (s[i] == 'h')
{
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) + fare[i];
dp[i][2] = dp[i - 1][2] + fare[i];
dp[i][3] = dp[i - 1][3] + fare[i];
}
else if (s[i] == 'a')
{
dp[i][0] = dp[i - 1][0] + fare[i];
dp[i][1] = dp[i - 1][1];
dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + fare[i];
dp[i][3] = dp[i - 1][3] + fare[i];
}
else if (s[i] == 'r')
{
dp[i][0] = dp[i - 1][0] + fare[i];
dp[i][1] = dp[i - 1][1] + fare[i];
dp[i][2] = dp[i - 1][2];
dp[i][3] = max(dp[i - 1][2], dp[i - 1][3]) + fare[i];
}
else if (s[i] == 'd')
{
dp[i][0] = dp[i - 1][0] + fare[i];
dp[i][1] = dp[i - 1][1] + fare[i];
dp[i][2] = dp[i - 1][2] + fare[i];
dp[i][3] = dp[i - 1][3];
}
else
{
dp[i][0] = dp[i - 1][0] + fare[i];
dp[i][1] = dp[i - 1][1] + fare[i];
dp[i][2] = dp[i - 1][2] + fare[i];
dp[i][3] = dp[i - 1][3] + fare[i];
}
}

ll ma = 0;
for (int i = 0; i < 4; i++) ma = max(ma, dp[n][i]);
printf("%lld\n", sum - ma);

return 0;
}


15天前

### 例题1 Sequence 传送门

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

using namespace std;

const int N = 4e5 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N];

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(int s[], int n, int m)
{
int i, p, w;
memset(cnt, 0, sizeof cnt);
//for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

memset(cnt, 0, sizeof(cnt));
//for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

memcpy(oldrk, rk, sizeof(rk));
//for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

int n, s[N], val[N], tmp1[N], tmp2[N];

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &s[i]);

vector<int>v;
for (int i = 1; i <= n; i++) v.push_back(s[i]);
stable_sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int len = v.size();
for (int i = 1; i <= n; i++)
val[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin() + 1;

reverse(val + 1, val + n + 1);
reverse(s + 1, s + n + 1);

get_sa(val, n, len);

vector<int>ans;
//取第一段
int p = 0;
for (int i = 1; i <= n; i++)
if (sa[i] > 2)
{
p = sa[i];
break;
}
for (int i = p; i <= n; i++) ans.push_back(s[i]);
reverse(val + 1, val + n + 1);
reverse(s + 1, s + n + 1);

//取第二、三段
int tot = 0;
for (int i = n - p + 2; i <= n; i++)
tmp1[++tot] = s[i], tmp2[tot] = val[i];
int cnt = tot;
for (int i = 1; i <= cnt; i++)
tmp1[++tot] = tmp1[i], tmp2[tot] = tmp2[i];
reverse(tmp1 + 1, tmp1 + tot + 1);
reverse(tmp2 + 1, tmp2 + tot + 1);

get_sa(tmp2, tot, len);

for (int i = 1; i <= tot; i++)
if (sa[i] <= tot / 2 && sa[i] > 1)
{
p = sa[i];
break;
}
for (int i = p, j = 1; j <= tot / 2; i++, j++)
ans.push_back(tmp1[i]);

for (int i = 0; i < ans.size(); i++) printf("%d\n", ans[i]);

return 0;
}


### 例题2 Secretary 传送门

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

using namespace std;

const int N = 2e4 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];
// px[i] = rk[id[i]]（用于排序的数组所以叫 px）

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
int i, m = 300, p, w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

void get_height(char s[], int n)
{
for (int i = 1, k = 0; i <= n; ++i)
{
if (k) --k;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
ht[rk[i]] = k;
}
}

int T, n, m;
char s[N], t[N];

int main()
{
scanf("%d", &T);
getchar();
while (T--)
{
cin.getline(s + 1, N);
cin.getline(t + 1, N);

n = strlen(s + 1);
m = strlen(t + 1);

s[n + 1] = '#';
strcpy(s + n + 2, t + 1);

get_sa(s, n + m + 1);
get_height(s, n + m + 1);

int ma = 0;
for (int i = 2; i <= n + m + 1; i++)
{
int pos1 = sa[i - 1], pos2 = sa[i];
if ((pos1 <= n && pos2 <= n) ||
(pos1 >= n + 2 && pos2 >= n + 2))
continue;
ma = max(ma, ht[i]);
}
printf("Nejdelsi spolecny retezec ma delku %d.\n", ma);
}

return 0;
}


### 例题3 最长回文子串 传送门

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

using namespace std;

const int N = 220050;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];
// px[i] = rk[id[i]]（用于排序的数组所以叫 px）

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
int i, m = 300, p, w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

void get_height(char s[], int n)
{
for (int i = 1, k = 0; i <= n; ++i)
{
if (k) --k;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
ht[rk[i]] = k;
}
}

int Log[N], f[N][23];
void RMQ_pre(int n)
{
Log[0] = -1;
for (int i = 1; i <= n; i++)
{
if (!(i & (i - 1))) Log[i] = Log[i - 1] + 1;
else Log[i] = Log[i - 1];
f[i][0] = ht[i];
}
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int RMQ_min(int l, int r)
{
int d = Log[r - l + 1];
return min(f[l][d], f[r - (1 << d) + 1][d]);
}

char s[N], t[N];

int main()
{
while (~scanf("%s", s + 1))
{
int tot = 0, n = strlen(s + 1);
for (int i = 1; i <= n; i++) t[++tot] = s[i];
t[++tot] = '#';
for (int i = n; i >= 1; i--) t[++tot] = s[i];

get_sa(t, tot);
get_height(t, tot);
RMQ_pre(tot);

int ma = 0;
for (int i = 1; i <= n; i++)
{
int x = i, y = n * 2 + 2 - i;
//奇数长度
int rkx = rk[x], rky = rk[y];
if (rkx > rky) swap(rkx, rky);
ma = max(ma, RMQ_min(rkx + 1, rky) * 2 - 1);
//偶数长度
if (i == 1) continue;
x = i; y = n * 2 + 3 - i;
rkx = rk[x], rky = rk[y];
if (rkx > rky) swap(rkx, rky);
ma = max(ma, RMQ_min(rkx + 1, rky) * 2);
}
printf("%d\n", ma);
}

return 0;
}


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

using namespace std;

const int N = 2e4 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N];

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
int i, m = 300, p, w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

int t;
char s[N];

int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%s", s + 1);

int n = strlen(s + 1);
for (int i = 1; i <= n; i++) s[n + i] = s[i];
s[n * 2 + 1] = '{';
get_sa(s, n * 2 + 1);

int ans = 0;
for (int i = 1; i <= 2 * n; i++)
{
if (sa[i] <= n)
{
ans = sa[i];
break;
}
}
printf("%d\n", ans);
}

return 0;
}


### 习题2 Common Substrings 传送门

L = 左侧最近比height[i]小的下标 + 1, R = 右侧最近比height[i]小的下标 + 1, 可用单调栈维护

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

using namespace std;

const int N = 2e5 + 10;

typedef long long ll;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
int i, m = 300, p, w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

void get_height(char s[], int n)
{
for (int i = 1, k = 0; i <= n; ++i)
{
if (k) --k;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
ht[rk[i]] = k;
}
}

int l[N], r[N], qu[N], tot;
void get_array_lr(int n)
{
ht[0] = ht[n + 1] = -1;
tot = 0; qu[++tot] = 0;
for (int i = 1; i <= n; i++)
{
while (tot && ht[i] <= ht[qu[tot]]) tot--;
l[i] = qu[tot] + 1;
qu[++tot] = i;
}

tot = 0; qu[++tot] = n + 1;
for (int i = n; i >= 1; i--)
{
while (tot && ht[i] <= ht[qu[tot]]) tot--;
r[i] = qu[tot] - 1;
qu[++tot] = i;
}

ht[0] = ht[n + 1] = 0;
}

int k;
char s[N], t[N];
vector<int>v[N];
ll sum[N];

int main()
{
while (~scanf("%d", &k) && k)
{
scanf("%s", s + 1);
scanf("%s", t + 1);

int lens = strlen(s + 1);
int lent = strlen(t + 1);

s[lens + 1] = '#';
for (int i = 1; i <= lent; i++) s[lens + 1 + i] = t[i];
int n = lens + lent + 1;

get_sa(s, n);
get_height(s, n);
get_array_lr(n);

for (int i = 1; i <= n; i++) v[i].clear();
for (int i = 1; i <= n; i++) v[ht[i]].push_back(i);
for (int i = 0; i <= n; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++)
{
if (sa[i] <= lens) cnt[i] = 1;
else cnt[i] = 0;
cnt[i] += cnt[i - 1];
}

for (int i = 0; i <= n + 1; i++) sum[i] = 0;

for (int i = n; i >= 1; i--)
{
int rborder = 0;
for (int j = 0; j < v[i].size(); j++)
{
if (r[v[i][j]] <= rborder) continue;
rborder = r[v[i][j]];
int le = l[v[i][j]] - 1, ri = r[v[i][j]];
int cnt1 = cnt[ri] - cnt[le - 1];
int cnt2 = ri - le + 1 - cnt1;
ll val = 1LL * cnt1 * cnt2;
int mi = max(ht[le], ht[ri + 1]) + 1;
sum[mi] += val; sum[i + 1] -=val;
}
}

for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];
for (int i = n; i >= 1; i--) sum[i] += sum[i + 1];
printf("%lld\n", sum[k]);
}

return 0;
}


### 习题3 Facer’s string 传送门

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

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(int s[], int n, int m)
{
int i, p, w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

void get_height(int s[], int n)
{
for (int i = 1, k = 0; i <= n; ++i)
{
if (k) --k;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
ht[rk[i]] = k;
}
}

int pre[N];
int cal_least_k(int n, int k)
{
int l = 0, r = 0, ans = 0;
for (int i = 1; i <= n; i++)
{
if (ht[i] < k)
{
if (l != 0 && pre[r] - pre[l - 1] != r - l + 1) ans += pre[r] - pre[l - 1];
l = r = 0;
continue;
}
if (l == 0) l = i - 1;
r = i;
}
if (l != 0 && r != 0) ans += pre[r] - pre[l - 1];

return ans;
}

int n, m, k;
int a[N], b[N];

int main()
{
while (~scanf("%d %d %d", &n, &m, &k))
{
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i]++;
for (int i = 1; i <= m; i++) scanf("%d", &b[i]), b[i]++;

a[n + 1] = 10005;
for (int i = 1; i <= m; i++) a[n + 1 + i] = b[i];

int tot = n + m + 1;
get_sa(a, tot, 10005);
get_height(a, tot);

for (int i = 0; i <= tot; i++) pre[i] = 0;
for (int i = 1; i <= tot; i++)
{
if (sa[i] <= n) pre[i] = 1;
pre[i] += pre[i - 1];
}

int ans = cal_least_k(tot, k) - cal_least_k(tot, k + 1);
printf("%d\n", ans);
}

return 0;
}


### 习题4 Common Palindromes 传送门

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

using namespace std;

typedef long long ll;
typedef map<int, ll>::iterator IT;

const int N = 4e5 + 50;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
int i, m = 300, p, w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

void get_height(char s[], int n)
{
for (int i = 0; i <= n; i++) ht[i] = 0;
for (int i = 1, k = 0; i <= n; ++i)
{
if (k) --k;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
ht[rk[i]] = k;
}
}

int Log[N], f[N][21];
void RMQ_pre(int n)
{
Log[0] = -1;
for (int i = 1; i <= n; i++)
{
if (!(i & (i - 1))) Log[i] = Log[i - 1] + 1;
else Log[i] = Log[i - 1];
f[i][0] = ht[i];
}
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int RMQ_min(int l, int r)
{
int d = Log[r - l + 1];
return min(f[l][d], f[r - (1 << d) + 1][d]);
}

char s[N], t[N], p[N];

void get_rad(char p[], int pos, int lens)
{
int prepos = pos;
p[++pos] = '&';
for (int i = prepos; i >= 1; i--) p[++pos] = p[i];

get_sa(p, pos);
get_height(p, pos);
RMQ_pre(pos);

for (int i = 1; i <= prepos; i++)
{
int x = i, y = pos - i + 1;
int rkx = rk[x], rky = rk[y];
if (rkx > rky) swap(rkx, rky);
rad[i] = RMQ_min(rkx + 1, rky) / 2;
if (x > lens) rad[i] = min(rad[i], x - lens - 1);
}
}

struct BIT_tree{
int treemax;
ll tree[N];
void init() //初始化
{
memset(tree, 0, sizeof tree);
treemax = 100010;
}
inline int lowbit(int x){ return x & (-x); }
void modify(int i, ll x) //单点更新
{
i++;
while(i <= treemax)
{
tree[i] += x;
i += lowbit(i);
}
}
ll query(int i)//前缀和查询
{
i++;
ll s = 0;
while(i > 0)
{
s += tree[i];
i -= lowbit(i);
}
return s;
}

ll get_ans(int pos)
{
ll ans = 0;
map<int, ll>mp[2];
for (int i = 0; i < 2; i++) lencnt[i].init(), addsum[i].init(), mp[i].clear();
for (int i = 1; i <= pos; i++)
{
int lcplen = ht[i];
lcplen -= pre[min(pos, sa[i] + ht[i] - 1)] - pre[sa[i] - 1];
for (int j = 0; j < 2; j++)
{
IT it = mp[j].upper_bound(lcplen);
while (it != mp[j].end())
{
int x = it->first;
ll y = it->second;
lencnt[j].modify(x, -y);
addsum[j].modify(x, -1LL * x * y);
lencnt[j].modify(lcplen, y);
addsum[j].modify(lcplen, 1LL * lcplen * y);
mp[j][lcplen] += y;
mp[j].erase(it++);
}
}
int rlen = rad[sa[i]], cho = 1 - flag[i];
ans += 1LL * rlen * (lencnt[cho].query(100005) - lencnt[cho].query(rlen));
lencnt[flag[i]].modify(rlen, 1);
mp[flag[i]][rlen] += 1;
}
return ans;
}

int main()
{
scanf("%s", s + 1);
scanf("%s", t + 1);

int lens = strlen(s + 1), lent = strlen(t + 1);

int pos = 0;
for (int i = 1; i <= lens; i++) p[++pos] = '#', p[++pos] = s[i];
p[++pos] = '#'; p[++pos] = '*';
for (int i = 1; i <= lent; i++) p[++pos] = '#', p[++pos] = t[i];
p[++pos] = '#';
lens = lens << 1 | 1;
lent = lent << 1 | 1;

p[pos + 1] = '\0';
get_sa(p, pos);
get_height(p, pos);
for (int i = 1; i <= pos; i++)
{
if (sa[i] <= lens) flag[i] = 0;
else flag[i] = 1;
if (p[i] == '#') pre[i] = 1;
pre[i] += pre[i - 1];
}

ll ans = get_ans(pos);
printf("%lld\n", ans);

return 0;
}


### 习题5 String 传送门

1. 对出现大于等于2次的计算，处理方法类似习题2, 利用单调栈和height分类求解即可
2. 对只出现1次的计算，枚举每个串S[i], len = |S[i]|, 则有 len - max(height[i], height[i + 1]) 个串只出现了一次

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

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w)
{
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
int i, m = 300, p, w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

for (w = 1; w < n; w <<= 1, m = p)
{  // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;

for (int i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}

void get_height(char s[], int n)
{
for (int i = 1, k = 0; i <= n; ++i)
{
if (k) --k;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
ht[rk[i]] = k;
}
}

int l[N], r[N], qu[N], tot;
void get_array_lr(int n)
{
ht[0] = ht[n + 1] = -1;

qu[++tot] = 0;
for (int i = 1; i <= n; i++)
{
while (tot && ht[i] <= ht[qu[tot]]) tot--;
l[i] = qu[tot] + 1;
qu[++tot] = i;
}

tot = 0;
qu[++tot] = n + 1;
for (int i = n; i >= 1; i--)
{
while (tot && ht[i] <= ht[qu[tot]]) tot--;
r[i] = qu[tot] - 1;
qu[++tot] = i;
}

ht[0] = ht[n + 1] = 0;
}

char s[N];
vector<int>v[N];
int sum[N];

int main()
{
scanf("%s", s + 1);

int len = strlen(s + 1);

get_sa(s, len);
get_height(s, len);
get_array_lr(len);

ll ans = 0;
for (int i = 1; i <= len; i++) v[ht[i]].push_back(i);
for (int i = len; i >= 1; i--)
{
int rborder = 0;
for (int j = 0; j < v[i].size(); j++)
{
int le = l[v[i][j]], ri = r[v[i][j]];
if (ri <= rborder) continue;
rborder = ri;
int down = max(ht[le - 1], ht[ri + 1]) + 1;
int cs = ri - le + 2;
ans += 1LL * cs * (cs + 1) / 2 * (i + 1 - down);
}
}

for (int i = 1; i <= len; i++)
{
int ma = max(ht[i], ht[i + 1]);
ans += len - sa[i] + 1 - ma;
}

printf("%lld\n", ans);

return 0;
}


15天前

### 例题1 Constellations 传送门

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

using namespace std;

typedef unsigned int UI;

const int N = 1010;
const int M = 60;

int n, m, t, x, y;
char mp[N][N], s[M][M];

const UI p0 = 1413;
UI p[N * N], hash1[N][N], hash2[N];
multiset<UI>se;

//计算大01矩阵
void pre(int n, int m, int x, int y)
{
p[0] = 1;
for (int i = 1; i <= n * m; i++) p[i] = p[i - 1] * p0;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
hash1[i][j] = hash1[i][j - 1] * p[1] + mp[i][j];

for (int i = y; i <= m; i++)
{
for (int j = 1; j <= n; j++)
hash2[j] = hash1[j][i] - hash1[j][i - y] * p[y];
for (int j = 1; j <= n; j++)
hash2[j] = hash2[j - 1] * p[y] + hash2[j];
for (int j = x; j <= n; j++)
se.erase(hash2[j] - hash2[j - x] * p[x * y]);
}
}

int main()
{
int cas = 0;
while (~scanf("%d %d %d %d %d", &n, &m, &t, &x, &y))
{
if (n + m + t + x + y == 0) break;
se.clear();

for (int i = 1; i <= n; i++)
scanf("%s", mp[i] + 1);

for (int T = 1; T <= t; T++)
{
for (int i = 1; i <= x; i++)
scanf("%s", s[i] + 1);

//计算小01矩阵
UI ans = 0;
for (int i = 1; i<= x; i++)
for (int j = 1; j <= y; j++)
ans = ans * p0 + s[i][j];
se.insert(ans);
}

pre(n, m, x, y);

int cnt = t - se.size();
printf("Case %d: %d\n", ++cas, cnt);
}

return 0;
}


### 习题1 Constellations 传送门

1. t1包含t2, 则合并结果为t1
2. t1不包含t2, 设 len 为 t1的后缀串 和 t2的前缀串 的最长公共子串T, 则合并时去掉T即可

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

using namespace std;

typedef unsigned long long ULL;

const int N = 3e5 + 10;

string s[5];
int num[N], tot;
ULL p[N], hash1[N], hash2[N];

void init(int n)
{
p[0] = 1;
for (int i = 1; i <= n; i++) p[i] = p[i - 1] * 131;
}

string merge(string a, string b)
{
a = " " + a; b = " " + b;
int lena = a.length() - 1, lenb = b.length() - 1;
for (int i = 1; i <= lena; i++) hash1[i] = hash1[i - 1] * 131 + a[i] - '0';
for (int i = 1; i <= lenb; i++) hash2[i] = hash2[i - 1] * 131 + b[i] - '0';

for (int i = 1; i <= lena - lenb + 1; i++)
if (hash1[i + lenb - 1] - hash1[i - 1] * p[lenb] == hash2[lenb])
return a.substr(1);
for (int i = max(1, lena - lenb + 2); i <= lena; i++)
{
int len = lena - i + 1;
if (hash1[lena] - hash1[i - 1] * p[len] == hash2[len])
return a.substr(1) + b.substr(len + 1);
}
return a.substr(1) + b.substr(1);

}

string merge(string a, string b, string c)
{
return merge(merge(a, b), c);
}

int main()
{
init(300005);

for (int i = 1; i <= 3; i++) cin >> s[i];

for (int i = 1; i <= 3; i++) num[i] = i;

int mi = N;
do{
string ans = merge(s[num[1]], s[num[2]], s[num[3]]);
mi = min(mi, (int)ans.length());
}while (next_permutation(num + 1, num + 4));
printf("%d\n", mi);

return 0;
}


### 习题2 Where’s Wally 传送门

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

using namespace std;

typedef unsigned long long ULL;

const int N = 1e3 + 10;
const int M = 1e2 + 10;

int w, h, p;
char s[N][N], t[N][N];
char ns[N][N], nt[N][N], backup[N][N];

int get_val(char c)
{
if (c >= 'A' && c <= 'Z') return c - 'A';
if (c >= 'a' && c <= 'z') return 26 + c - 'a';
if (c >= '0' && c <= '9') return 52 + c - '0';
if (c == '+') return 62;
if (c == '/') return 63;
}

void change_matrix(int n, int m, char (&s)[N][N], char (&e)[N][N])
{
for (int i = 1; i <= n; i++)
{
int tot = 0;
for (int j = 1; s[i][j]; j++)
{
int val = get_val(s[i][j]);
for (int k = 5; k >= 0; k--)
if (val & (1 << k)) e[i][++tot] = '1';
else e[i][++tot] = '0';
}
}
}

ULL P[N * N], ha[N][N];
void init(int n)
{
P[0] = 1;
for (int i = 1; i <= n; i++) P[i] = P[i - 1] * 131;
}

int main()
{
init(1000005);

while (~scanf("%d %d %d", &w, &h, &p))
{
if (w + h + p == 0) break;

for (int i = 1; i <= h; i++) scanf("%s", s[i] + 1);
for (int i = 1; i <= p; i++) scanf("%s", t[i] + 1);

change_matrix(h, w, s, ns);
change_matrix(p, p, t, nt);

for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
ha[i][j] = ha[i][j - 1] * 131 + ns[i][j] - '0';

set<ULL>se;

for (int t = 1; t <= 8; t++)
{
if (t == 5)
{
memcpy(backup, nt, sizeof nt);
for (int i = 1; i <= p; i++)
for (int j = 1; j <= p; j++)
nt[i][p - j + 1] = backup[i][j];
}

ULL val = 0;
for (int i = 1; i <= p; i++)
for (int j = 1; j <= p; j++)
val = val * 131 + nt[i][j] - '0';
se.insert(val);

memcpy(backup, nt, sizeof nt);
for (int i = 1; i <= p; i++)
for (int j = 1; j <= p; j++)
nt[p - j + 1][i] = backup[i][j];
}

int cnt = 0;
for (int i = 1; i + p - 1 <= h; i++)
for (int j = 1; j + p - 1 <= w; j++)
{
ULL val = 0;
for (int k = i; k <= i + p - 1; k++)
val = val * P[p] + ha[k][j + p - 1] - ha[k][j - 1] * P[p];
if (se.find(val) != se.end()) cnt++;
}
printf("%d\n", cnt);
}

return 0;
}


### 习题3 The Oculus 传送门

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ULL;

const int N = 2e6 + 10;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;

ll f1[N], f2[N];
ULL f3[N];

int t;
int alen, a[N];
int blen, b[N];
int clen, c[N];

set<pair<ll,ll> >se;

int main()
{
f1[1] = 1; f1[2] = 2;
f2[1] = 1; f2[2] = 2;
f3[1] = 1; f3[2] = 2;
for (int i = 3; i <= 2000005; i++)
{
f1[i] = (f1[i - 1] + f1[i - 2]) % mod1;
f2[i] = (f2[i - 1] + f2[i - 2]) % mod2;
f3[i] = f3[i - 1] + f3[i - 2];
}

scanf("%d", &t);
while (t--)
{
scanf("%d", &alen);
for (int i = 1; i <= alen; i++)
scanf("%d", &a[i]);
scanf("%d", &blen);
for (int i = 1; i <= blen; i++)
scanf("%d", &b[i]);
scanf("%d", &clen);
for (int i = 1; i <= clen; i++)
scanf("%d", &c[i]);

ll aval1 = 0, bval1 = 0;
ll aval2 = 0, bval2 = 0;
ULL aval3 = 0, bval3 = 0;
for (int i = 1; i <= alen; i++)
if (a[i])
{
aval1 = (aval1 + f1[i]) % mod1;
aval2 = (aval2 + f2[i]) % mod2;
aval3 += f3[i];
}
for (int i = 1; i <= blen; i++)
if (b[i])
{
bval1 = (bval1 + f1[i]) % mod1;
bval2 = (bval2 + f2[i]) % mod2;
bval3 += f3[i];
}

ll res1 = aval1 * bval1 % mod1;
ll res2 = aval2 * bval2 % mod2;
ULL res3 = aval3 *bval3;

ll cval1 = 0, cval2 = 0;
ULL cval3 = 0;
for (int i = 1; i <= clen; i++)
if (c[i])
{
cval1 = (cval1 + f1[i]) % mod1;
cval2 = (cval2 + f2[i]) % mod2;
cval3 += f3[i];
}
int ans = 0;
for (int i = 1; i <= clen; i++)
{
if (c[i]) continue;
ll tmp1 = (cval1 + f1[i]) % mod1;
ll tmp2 = (cval2 + f2[i]) % mod2;
ULL tmp3 = cval3 + f3[i];
if (tmp1 == res1 && tmp2 == res2 && tmp3 == res3)
{
ans = i;
break;
}
}

printf("%d\n", ans);
}

return 0;
}


22天前

·

### 问题分析

例如 n = 10
S(2) = {2, 4, 6, 8, 10}
S(3) = {3, 9}
S(5) = {5}
S(7) = {7}


(当然你得判断y合法,)

#### C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int p[N], tot, d[N], st[N];
void init(int n)//用线性筛预处理出每个数的最小质因子
{
for (int i = 2; i <= n; i++)
{
if (!st[i]) p[++tot] = i, d[i] = i;
for (int j = 1; j <= tot && i * p[j] <= n; j++)
{
st[i * p[j]] = 1;
if (i % p[j] == 0)
{
d[i * p[j]] = d[i];
break;
}
else d[i * p[j]] = p[j];
}
}
}

int t, n;
set<int>divv[N];

int main()
{
init(200005);

scanf("%d", &t);
while (t--)
{
scanf("%d", &n);

//放入对应的集合 divv
for (int i = 1; i <= n; i++) divv[i].clear();
for (int i = 1; i <= n; i++) divv[d[i]].insert(i);

//记录答案
vector<int>a, b;
a.clear(); b.clear();

//优先构造 p > sqrt(n) 的情况
int sqn = sqrt(n);
int pos = upper_bound(p + 1, p + tot + 1, sqn) - p;
for (int i = pos; p[i] <= n; i++)
{
int val1 = p[i], val2 = 2 * p[i];
if (val2 > n) continue;
a.push_back(val2);
b.push_back(val1);
divv[2].erase(val2);
divv[p[i]].erase(val1);
}

//处理 S(p).size() % 2 == 1的情况
vector<int>v;
for (int i = 1; p[i] <= n; i++)
{
int sz = divv[p[i]].size();
if (sz & 1) v.push_back(p[i]);
}
for (int i = 0; i + 1 < v.size(); i += 2)
{
int val1 = v[i], val2 = v[i + 1];
if (1LL * val1 * val2 > n) continue;
a.push_back(val1 * val2);
b.push_back(val2);
divv[val1].erase(val1 * val2);
divv[val2].erase(val2);
}

//若存在奇数个元素的集合，直接删一个，以便后续处理
for (int i = 1; p[i] <= n; i++)
{
if (divv[p[i]].size() % 2 == 1)
divv[p[i]].erase(p[i]);
}

//最后将所有集合里的元素匹配
for (int i = 1; p[i] <= n; i++)
{
for (auto it = divv[p[i]].begin(); it != divv[p[i]].end(); it++)
{
a.push_back(*it);
it++;
b.push_back(*it);
}
}

printf("%d\n", a.size());
for (int i = 0; i < a.size(); i++)
printf("%d %d\n", a[i], b[i]);
}
}


### 附

1个月前

KMP：

• 前缀：指的是字符串的子串中从原串最前面开始的子串
如abcdef的前缀有：a,ab,abc,abcd,abcde

• 后缀：指的是字符串的子串中在原串结尾处结尾的子串
如abcdef的后缀有：f,ef,def,cdef,bcdef

• Next[i]：满足 以1开始的前缀以i结尾的后缀 相等条件的最大长度（长度<i）

Next数组求解：

• 边界：Next[1]=0;（由定义即可得到）

• 匹配状态：j + 1表示当前P要匹配的下标，i表示当前S串要匹配的下标
若P[j+1]=S[i]，直接匹配成功，则Next[j]=Next[j-1]+1;
若P[j+1]≠S[i]，匹配失败，需要根据Next[j]不断向前跳j，直到匹配成功或者j=0；

void get_Next(char S[], char P[])//S:文本串 P:模式串(此时S = P)
{
int n = strlen(S + 1);
int m = strlen(P + 1);

Next[1] = 0;
for (int i = 2, j = 0; i <= n; i++)
{
while (j && S[i] != P[j + 1]) j = Next[j];
if (S[i] == P[j + 1]) j++;
Next[i] = j;
}
}


Next数组运用：

//例：获取文本串S 中 模式串P 的个数
int get_count(char S[], char P[])
{
int n = strlen(S + 1);
int m = strlen(P + 1);

int cnt = 0; //统计个数

for (int i = 1, j = 0; i <= n; i++)
{
while (j && S[i] != P[j + 1]) j = Next[j];
if (S[i] == P[j + 1]) j++;
if (j == m) //找到匹配成功项
cnt++, j = Next[j];
}

return cnt;
}


• 若模式串P中 j / (j - Next[j]) == 0, 则P中必存在最小循环节(P[1~j-Next[j]),且循环次数为 j / (j - Next[j])
证明方法可通过切割移项法证“循环节”成立，通过反证法证“最小”成立
• 若模式串P中 j / (j - Next[j]) ≠ 0, 则P中必存在最小循环节(P[1~j-Next[j]),且循环次数为 j / (j - Next[j])，余项为P[1 ~ j % Next[j]]
证明方法如上

3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 510;
typedef pair<int,int> PII;

int t, n, m;
char mp[N][N];
int dist[N][N], st[N][N];

string ops = "\\//\\";
int dir1[4][2] = {-1, -1, -1, 1, 1, -1, 1, 1};
int dir2[4][2] = {0, 0, 0, 1, 1, 0, 1, 1};

bool check(int x, int y)
{
return x >= 0 && x <= n && y >= 0 && y <= m;
}

int bfs()
{
deque<PII>qu;

memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[0][0] = 0;
qu.push_back({0, 0});

while (!qu.empty())
{
PII cur = qu.front(); qu.pop_front();
int x = cur.first, y = cur.second;
if (st[x][y]) continue;
st[x][y] = 1;

for (int i = 0; i < 4; i++)
{
int nex = x + dir1[i][0], ney = y + dir1[i][1];
int j = x + dir2[i][0], k = y + dir2[i][1];

if (!check(nex, ney) || st[nex][ney]) continue;
int w = 0;
if (mp[j][k] != ops[i]) w = 1;
if (dist[nex][ney] > dist[x][y] + w)
{
dist[nex][ney] = dist[x][y] + w;
if (w == 1) qu.push_back({nex, ney});
else qu.push_front({nex, ney});
}
}
}

return dist[n][m];
}

int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);

int ans = bfs();
if (ans == 0x3f3f3f3f) printf("NO SOLUTION\n");
else printf("%d\n", ans);
}

return 0;
}


3个月前
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 25;

int t, n, m;
char mp[N][N];//mp: 存地图
string ops = "nswe";//ops：上下左右
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};//下上右左

struct node{
int x, y, dir;
};

bool check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != '#';
}

int vis[N][N], pre_man[N][N];
int bfs_man(PII sta, PII en, PII box, string& seq)
{
memset(vis, 0, sizeof vis);
memset(pre_man, -1, sizeof pre_man);

queue<PII>qu;
vis[sta.first][sta.second] = 1;
vis[box.first][box.second] = 1;
qu.push(sta);

int flag = -1;
while (!qu.empty())
{
PII cur = qu.front(); qu.pop();
int x = cur.first, y = cur.second;
if (cur == en)
{
while (pre_man[x][y] != -1)
{
int d = pre_man[x][y];
seq.push_back(ops[d]);
x = x + dir[d][0];
y = y + dir[d][1];
}
flag = seq.length();
break;
}
for (int i = 0; i < 4; i++)
{
int nex = x - dir[i][0], ney = y - dir[i][1];//(nex,ney):人的位置
if (check(nex, ney) == 0 || vis[nex][ney]) continue;
vis[nex][ney] = 1;
qu.push({nex, ney});
pre_man[nex][ney] = i;
}
}
return flag;
}

node pre[N][N][4];//pre(i,j,k):当前箱子在(i,j),上一个在(i+dir[k][0],j+dir[k][1])的状态
string path[N][N][4];//path(i,j,k):走到推(i,j,k)这个状态的位置的行走路程
PII dist[N][N][4];//dist(i,j,k):从初始状态到达(i,j,k)状态的箱子最短路程和人最短路程
bool st[N][N][4];
bool bfs_box(PII man, PII box, node& end)
{
memset(st, 0, sizeof st);

queue<node>qu;

for (int i = 0; i < 4; i++)
{
int x = box.first, y = box.second;
int a = x + dir[i][0], b = y + dir[i][1];//(a,b):人的位置
int j = x - dir[i][0], k = y - dir[i][1];//(j,k):箱子的位置

if (check(a, b) == 0 || check(j, k) == 0) continue;
string seq;
int distance = bfs_man(man, {a, b}, box, seq);
if (distance == -1) continue;
st[j][k][i] = 1;
qu.push({j, k, i});
pre[j][k][i] = {x, y, -1};
path[j][k][i] = seq;
dist[j][k][i] = {1, distance};
}

bool flag = false;
PII mi = {1e9, 1e9};

while (!qu.empty())
{
node cur = qu.front(); qu.pop();
int x = cur.x, y = cur.y, d = cur.dir;
if (mp[x][y] == 'T')
{
flag = true;
if (dist[x][y][d] < mi) mi = dist[x][y][d], end = cur;
continue;
}
for (int i = 0; i < 4; i++)
{
int a = x + dir[i][0], b = y + dir[i][1];//(a,b):人的位置
int j = x - dir[i][0], k = y - dir[i][1];//(j,k):箱子的位置

if (check(a, b) == 0 || check(j, k) == 0) continue;
string seq;
int distance = bfs_man({x + dir[d][0], y + dir[d][1]}, {a, b}, {x, y}, seq);
if (distance == -1) continue;
PII now_dist = {dist[x][y][d].first + 1, dist[x][y][d].second + distance};
if (!st[j][k][i])
{
st[j][k][i] = 1;
qu.push({j, k, i});
pre[j][k][i] = cur;
path[j][k][i] = seq;
dist[j][k][i] = now_dist;
}
else if (dist[j][k][i] > now_dist)
{
pre[j][k][i] = cur;
path[j][k][i] = seq;
dist[j][k][i] = now_dist;
}
}
}

return flag;
}

int main()
{
while (~scanf("%d%d", &n, &m))
{
if (n == 0 && m == 0) break;

for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);

PII man, box;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (mp[i][j] == 'B') box = {i, j};
if (mp[i][j] == 'S') man = {i, j};
}

printf("Maze #%d\n", ++t);
node end;
if (bfs_box(man, box, end))
{
string ans;
while (end.dir != -1)
{
ans.push_back((char)(ops[end.dir] - 32));
ans.append(path[end.x][end.y][end.dir]);
end = pre[end.x][end.y][end.dir];
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
}
else printf("Impossible.\n");
printf("\n");
}

return 0;
}


3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n, m, dist[N][N];
char mp[N][N];

struct node{
int x, y;
};
int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

bool check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m && dist[x][y] == -1;
}

int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);

memset(dist, -1, sizeof dist);
queue<node>qu;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (mp[i][j] == '1') qu.push({i, j}), dist[i][j] = 0;

while (!qu.empty())
{
node cur = qu.front(); qu.pop();
for (int i = 0; i < 4; i++)
{
int nex = cur.x + dir[i][0];
int ney = cur.y + dir[i][1];
if (!check(nex, ney)) continue;
dist[nex][ney] = dist[cur.x][cur.y] + 1;
qu.push({nex, ney});
}
}

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) printf("%d ", dist[i][j]);
printf("\n");
}

return 0;
}


3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 5e2 + 10;
int n, m, dist[5][N][N];
char mp[N][N];

struct node{
int x, y, sta;
};
//sta: 0->立着 1->横着躺 2->竖着躺
int dir[3][4][3] = {
-2, 0, 2, 1, 0, 2, 0, -2, 1, 0, 1, 1, // sta = 0
-1, 0, 1, 1, 0, 1, 0, -1, 0, 0, 2, 0, // sta = 1
-1, 0, 0, 2, 0, 0, 0, -1, 2, 0, 1, 2  // sta = 2
};

bool check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != '#';
}

int bfs(node sta, node en)
{
queue<node>qu;
while (!qu.empty()) qu.pop();
qu.push(sta);
dist[sta.sta][sta.x][sta.y] = 0;

while (!qu.empty())
{
node cur = qu.front(); qu.pop();
int x = cur.x, y = cur.y, sta = cur.sta;
if (x == en.x && y == en.y && sta == en.sta) return dist[sta][x][y];

for (int i = 0; i < 4; i++)
{
int nex = x + dir[sta][i][0];
int ney = y + dir[sta][i][1];
int nesta = dir[sta][i][2];

if (!check(nex, ney)) continue;
if (nesta == 0 && mp[nex][ney] == 'E') continue;
if (nesta == 1 && !check(nex, ney + 1)) continue;
if (nesta == 2 && !check(nex + 1, ney)) continue;
if (dist[nesta][nex][ney] != -1) continue;

node ne = {nex, ney, nesta};
dist[nesta][nex][ney] = dist[sta][x][y] + 1;
qu.push(ne);
}
}

return -1;
}

int main()
{
ios::sync_with_stdio(false);

while (cin >> n >> m)
{
if (n == 0 && m == 0) break;
memset(dist, -1, sizeof dist);
for (int i = 1; i <= n; i++) cin >> mp[i] + 1;

node sta = {0, 0, 0}, en;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (mp[i][j] == 'X' && sta.x == 0)
{
if (mp[i][j + 1] == 'X') sta = {i, j, 1};
else if (mp[i + 1][j] == 'X') sta = {i, j, 2};
else sta = {i, j, 0};
}
if (mp[i][j] == 'O') en = {i, j, 0};
}

int ans = bfs(sta, en);
if (ans == -1) cout << "Impossible" << endl;
else cout << ans << endl;
}

return 0;
}


3个月前
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 50;
const int M = 25;
int n, w, g[N];
int w1[1 << M], tot, k;
int ans;

void dfs1(int pos, int val)
{
if (pos == k)
{
w1[++tot] = val;
return;
}

ll sum = 1LL * val + g[pos + 1];
if (sum <= w) dfs1(pos + 1, sum);
dfs1(pos + 1, val);
}

void dfs2(int pos, int val)
{
if (pos == n)
{
int l = 1, r = tot;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (1LL * w1[mid] + val <= w) l = mid;
else r = mid - 1;
}
ans = max(ans, val + w1[l]);
return;
}

ll sum = 1LL * val + g[pos + 1];
if (sum <= w) dfs2(pos + 1, sum);
dfs2(pos + 1, val);
}

int main()
{
scanf("%d %d", &w, &n);
for (int i = 1; i <= n; i++) scanf("%d", &g[i]);

k = n / 2 + 2;
sort(g + 1, g + n + 1);
reverse(g + 1, g + n + 1);

dfs1(0, 0);

sort(w1 + 1, w1 + tot + 1);
tot = unique(w1 + 1, w1 + tot + 1) - w1 - 1;

dfs2(k, 0);

printf("%d\n", ans);

return 0;
}