CF1200E WA求助
  • 板块灌水区
  • 楼主Ray662
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/18 14:44
  • 上次更新2023/10/23 21:15:38
查看原帖
CF1200E WA求助
502658
Ray662楼主2023/3/18 14:44
#include <bits/stdc++.h>
#define int long long
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define _all(i, a, b)  for (int i = (a); i >= (b); i -- )
using namespace std;
const int N = 1e6 + 5, base1 = 131, base2 = 137, P = 1e9 + 7, Q = 1e9 + 9;
int n, p1[N], p2[N], hi[N], hj[N], gi[N], gj[N];
string ans, s[N];
inline int H1(int q[], int l, int r) { return ((q[r] - q[l - 1] * p1[r - l + 1]) % P + P) % P; }
inline int H2(int q[], int l, int r) { return ((q[r] - q[l - 1] * p2[r - l + 1]) % Q + Q) % Q; }
signed main() {
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	_for (i, 1, n)  cin >> s[i];
	p1[0] = p2[0] = 1ll;
	_for (i, 1, N - 1)  p1[i] = (p1[i - 1] * base1) % P;
	_for (i, 1, N - 1)  p2[i] = (p2[i - 1] * base2) % Q;
	ans += s[1];
	_for (i, 1, n - 1) {
		int j = i + 1, l1 = s[i].size(), l2 = s[j].size(), res = 0;
		_for (k, 1, l1)  hi[k] = (hi[k - 1] * base1 + (s[i][k - 1] - '0' + 1)) % P;
		_for (k, 1, l2)  hj[k] = (hj[k - 1] * base1 + (s[j][k - 1] - '0' + 1)) % P;
		_for (k, 1, l1)  gi[k] = (gi[k - 1] * base2 + (s[i][k - 1] - '0' + 1)) % Q;
		_for (k, 1, l2)  gj[k] = (gj[k - 1] * base2 + (s[j][k - 1] - '0' + 1)) % Q;
		_all (k, min(l1, l2), 1)
			if (H1(hi, l1 - k + 1, l1) == H1(hj, 1, k) && H2(gi, l1 - k + 1, l1) == H2(gj, 1, k)) { res = k; break; }
		ans += s[j].substr(res, l2 - res);
	}
	cout << ans << endl;
	return 0;
}
2023/3/18 14:44
加载中...