ABC213

AtCoder Beginner Contest 213

E - Stronger Takahashi

题意

给出一个迷宫: .代表可以走的道路，#代表墙，你可以花费一点力气打破任意一个 $2\times 2$ 区域中的所有的墙

请问从迷宫的左上角走到右下角，最少要花费多少力气？

思路

这道题相比F题要水多了，但我并没看出来

这题可以相当于建图跑最短路，但由于图上的边权只有0和1，所以只需要用BFS就能完成，这就是01BFS

01BFS通过维护双端队列，使得队头元素是单增的，如果当前使用边权为0的边进行的松弛操作，那么把新的顶点push到队头，否则就是用边权为1的边进行的松弛操作，把新的顶点push到队尾

如此操作，可以保证队列中的元素都是形如00…0011…11…

关于这道题，考虑当前在格点T

.***.
*****
**T**
*****
.***.

那么*都是可以通过花费一次力气到达的格点，而不需要力气到达的格点只有和T相邻的4个格点并且它们是.

则时间复杂度为 $O(21NM)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int dx[4] = {0, -1, 1, 0};
int dy[4] = {1, 0, 0, -1};
int n, m;
bool chk(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m;
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<string> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vii dis(n, vi(m, INF)), vis(n, vi(m));
	deque<pii> q;
	q.emplace_front(0, 0);
	dis[0][0] = 0;
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second;
		q.pop_front();
		if (vis[x][y]) continue;
		vis[x][y] = 1;
		for (int i = 0; i < 4; i++) {
			int tx = x + dx[i], ty = y + dy[i];
			if (chk(tx, ty) && a[tx][ty] == '.') {
				if (dis[tx][ty] > dis[x][y]) {
					dis[tx][ty] = dis[x][y];
					q.emplace_front(tx, ty);
				}
			}
		}
		for (int i = -2; i <= 2; i++) {
			for (int j = -2; j <= 2; j++) {
				if ((abs(i) + abs(j) == 4) || (i == 0 && j == 0)) {
					continue;
				}
				int tx = x + i, ty = y + j;
				if (chk(tx, ty) && dis[tx][ty] > dis[x][y] + 1) {
					dis[tx][ty] = dis[x][y] + 1;
					q.emplace_back(tx, ty);
				}
			}
		}
	}
	cout << dis[n-1][m-1] << '\n';
	return 0;
}

F - Common Prefixes

题意

定义字符串函数 $f(S,T)$ 为字符串 $S, T$ 的最长公共前缀，也就是LCM

给出一个长度为 $N$ 的字符串 $S$，$S_i$ 表示从 $S$ 的第 $i$ 个字符开始的 $S$ 的后缀
如abcd中 $S_2=bcd,S_3=cd$

对于每个 $k=1,\ldots,N$ 求 $f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N)$

思路

比赛时速度还是太慢了，对SAM还是不够熟练，由于公共前缀不好处理，考虑转为公共后缀，只需要将字符串反转后，倒序输出答案即可

那么 $\sum_{i=1}^N f(S_k,S_i)$ 就是求字符串 $s_1s_2\ldots s_k$ 的每个后缀在 $S$ 中的出现次数

这个问题使用后缀树很容易解决，用sz数组代表SAM中每个顶点right集合的大小，mx数组表示该顶点的right集合中的最大长度

先找到 $S_k$ 对应的节点 $p$，然后暴跳 $prt$ 数组，那么以 $s_{k-mx[p]+1}\ldots s_k$ 在 $S$ 中的出现次数就是 $sz[prt[p]] - sz[p]$

那么顶点 $p$ 对答案的贡献就是 $mx[p] \cdot (sz[prt[p]]-sz[p])$，求和即可

但是如果对每个节点都暴跳 $prt$ 数组复杂度是 $O(N^2)$ 肯定超时，所以还需要记忆化一下

记 $dp[p]$ 为顶点 $prt[p]$ 产生的贡献，不记当前顶点 $p$ 产生的贡献，是因为当前顶点的贡献会和它的而自己顶点的sz大小有关

时间复杂度为 $O(N)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 2e6 + 10;
struct SAM {
	int ch[N][26], mx[N], sz[N], prt[N], cnt, last;
	SAM() {cnt = last = 1; }
	void add(int c) {
		int p = last, np = ++cnt;
		last = np;
		mx[np] = mx[p] + 1;
		sz[np] = 1;
		for (; p && !ch[p][c]; p = prt[p]) ch[p][c] = np;
		if (!p) prt[np] = 1;
		else {
			int q = ch[p][c];
			if (mx[q] == mx[p] + 1) prt[np] = q;
			else {
				int nq = ++cnt;
				mx[nq] = mx[p] + 1;
				prt[nq] = prt[q];
				prt[q] = prt[np] = nq;
				memcpy(ch[nq], ch[q], sizeof(ch[q]));
				for (; ch[p][c] == q; p = prt[p]) ch[p][c] = nq;
			}
		}
	}
	int t[N], c[N];
	void tsort() {
		for (int i = 1; i <= cnt; i++) t[mx[i]]++;
		for (int i = 1; i <= cnt; i++) t[i] += t[i-1];
		for (int i = 1; i <= cnt; i++) c[t[mx[i]]--] = i;
		for (int i = cnt; i >= 1; i--) sz[prt[c[i]]] += sz[c[i]];
	}
	int dp[N];
	int dfs(int u) {
		if (dp[u] != -1) return dp[u];
		int a = mx[prt[u]], b = mx[prt[prt[u]]]+1;
		//return dp[u] = (sz[prt[u]] - sz[u]) * (a-b) + dfs(prt[u]);
		return dp[u] = (sz[prt[u]] - sz[u]) * a + dfs(prt[u]);
	}
	void solve() {
		memset(dp, -1, sizeof(dp));
		dp[0] = 0;
		int n;
		string s;
		cin >> n >> s;
		reverse(s.begin(), s.end());
		for (int i = 0; i < n; i++) {
			add(s[i] - 'a');
		}
		tsort();
		vi ans;
		for (int i = 0, p = 1; i < n; i++) {
			p = ch[p][s[i] - 'a'];
			ans.pb(dfs(p) + (i+1) * sz[p]);
		}
		for (int i = n-1; i >= 0; i--) {
			cout << ans[i] << '\n';
		}
	}
}sam;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	sam.solve();
	return 0;
}