20250824-拓冰建站

T1

我们惊奇地发现这题不是直接哈希加一个桶就写完了吗？顺序统计哈希，记录答案。光速打了一个出来，发现空间只有 31.25MB，算了算，好像不会超。

赛后一测发现超时了。map 换成 umap 就过了。map 万恶之源。

#include <bits/stdc++.h>using namespace std;
using ULL = unsigned long long;const int kN = 2e5 + 7;
const ULL base = 13331;int n, ans;
string s; 
ULL has[kN], bpow[kN];
unordered_map<ULL, bool> b;ULL gethash(int l, int r) {return has[r] - has[l - 1] * bpow[r - l + 1];
}bool check(int x) {b.clear(); ULL f = 0;for (int i = 1; i + x - 1 <= n; i++) {f = gethash(i, i + x - 1);if (b.count(f)) return 1; b[f] = 1;}return 0;
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> s, s = " " + s, bpow[0] = 1; for (int i = 1; i <= n; i++) {has[i] = has[i - 1] * base + s[i];bpow[i] = bpow[i - 1] * base;}for (int l = 1, r = n, mid; l <= r; ) {mid = (l + r) >> 1;if (check(mid)) l = mid + 1, ans = mid;else r = mid - 1;}cout << ans;return 0;
}

T2

这个东西不是我上午刚出的模拟赛的 T4 吗？？？简直一模一样！

实际上就是考虑到等差加排列的性质：当我们建立一个桶时，如果对于数 \(i\)，假设差为 \(d\)，如果 \(i-d\) 存在过但 \(i+d\) 还没有出现，那么由于这是个排列，这个数一定在后面出现，那么也就一定是等差序列。因此考虑拿线段树维护一个桶，对于每个 \(i\)，只要其左右不回文，那么一定找得到，线段树/树状数组维护哈希即可。

然后写出来了，大样例都过了，赛后一测，0 分？？？我一看，int len = min(n - a[i], a[i] - 1), Update(a[i]);，哈哈😄！

#include <bits/stdc++.h>
#define ls (p << 1)
#define rs ((p << 1) | 1)using namespace std;
using ULL = unsigned long long;const int kN = 5e5 + 7, base = 131;int T, n, a[kN];
ULL bpow[kN];struct S {ULL has1, has2, len;friend S operator + (S a, S b) {return {a.has1 * bpow[b.len] + b.has1, b.has2 * bpow[a.len] + a.has2, a.len + b.len}; }
} seg[kN << 2];void Build(int l = 1, int r = n, int p = 1) {if (l == r) return (void)(seg[p] = {0, 0, 1});int mid = (l + r) >> 1;Build(l, mid, ls), Build(mid + 1, r, rs);seg[p] = seg[ls] + seg[rs];
}void Update(int x, int l = 1, int r = n, int p = 1) {if (l == r) return (void)(seg[p] = {1, 1, 1});int mid = (l + r) >> 1;if (x <= mid) Update(x, l, mid, ls);else Update(x, mid + 1, r, rs);seg[p] = seg[ls] + seg[rs];
}S Query(int s, int t, int l = 1, int r = n, int p = 1) {if (s <= l && r <= t) return seg[p];int mid = (l + r) >> 1; S res = {0, 0, 0};if (s <= mid) res = res + Query(s, t, l, mid, ls);if (mid + 1 <= t) res = res + Query(s, t, mid + 1, r, rs);return res;
}void Work() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}Build(1, n, 1);for (int i = 1, len = 0; i <= n; i++) {len = min(n - a[i], a[i] - 1), Update(a[i]);if (len == 0) continue;if (Query(a[i] - len, a[i] - 1).has1 != Query(a[i] + 1, a[i] + len).has2) return (void)(cout << "YES\n");}cout << "NO\n";
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);bpow[0] = 1;for (int i = 1; i < kN; i++) bpow[i] = bpow[i - 1] * base;Work();return 0;
}

T3

考虑什么时候有无解的情况：一个串的前缀出现过，或者在按字典序建图时出现了环。

前者可以直接使用字典树，后者带一个建图，将串对 trie 建边，如果形成了环则无解，答案可以在跑拓扑排序时记录。

#include <bits/stdc++.h>using namespace std;const int kN = 1e6 + 7, kM = 2.5e4 + 7;int n, m, in[kN];
string s[kM];
queue<int> q;
vector<int> g[28], ans;struct T {int ch[27], ed, t;
} a[kN];int f(int c) {return c - 'a';
}void Insert(string s) {int p = 0, k = 0;for (int c : s) {k = f(c), (a[p].ch[k] == 0) && (a[p].ch[k] = ++m), p = a[p].ch[k], a[p].t++;}a[p].ed++;
}bool Find(string s) {int p = 0, k = 0;for (int c : s) {k = f(c);if (a[p].ed) return 1;p = a[p].ch[k];}return 0;
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> s[i], Insert(s[i]);}for (int i = 1; i <= n; i++) {if (Find(s[i])) {cout << "nemoguce\n";continue;}ans.clear();for (int j = 0; j < 26; j++) g[j].clear(), in[j] = 0;int u = 0;for (int j = 0; j < s[i].size(); j++) {int c = s[i][j] - 'a';for (int k = 0; k < 26; k++) {if (c == k || !a[u].ch[k]) continue;g[c].push_back(k), in[k]++;}u = a[u].ch[c];}for (int j = 0; j < 26; j++) {if (!in[j]) q.push(j);}while (q.size()) {int u = q.front(); q.pop();ans.push_back(u + 'a');for (int v : g[u]) {if (!--in[v]) q.push(v);}}for (int j = 0; j < 26; j++) {if (in[j] > 0) {cout << "nemoguce\n";goto shit;}}if (ans.size() == 26) for (char x : ans) cout << x;else cout << "nemoguce";cout << '\n';shit:;}return 0;
}