难度: 钻石

思路: 字符串hash + 二分

先提炼下题意:

即存在字符串T, 它即是S的前缀, 也是S的后缀, 同时在S[1:-2]中存在子数组S'=T, 求最长的T

切入点是

• 先找到满足要求的T（从前后缀一致），获取候选的列表$[T_1,T_2,...,T_k],且T_i为T_j的前缀i\le j$
• 然后枚举$i\in [1,n-2]$, 作为起点，二分找最长的 $T_i$

为啥二分可以呢？因为存在阶段性

#include <bits/stdc++.h>using namespace std;using int64 = long long;struct StringHash {StringHash(const string& s, int64 p, int64 mod): p(p), mod(mod), pre(s.length() + 1, 0), pow(s.length() + 1, 0) {int n = s.length();pow[0] = 1;for (int i = 0; i < n; i++) {pow[i + 1] = pow[i] * p % mod;pre[i + 1] = (pre[i] * p % mod + s[i]) % mod;}}int query(int l, int r) {return ((pre[r + 1] - pre[l] * pow[r - l + 1] % mod) % mod + mod) % mod;}int64 mod;int64 p;vector<int64> pre;vector<int64> pow;
};int main() {string s;cin >> s;int p1 = 13, p2 = 17;int64 mod = (int64)1e9 +  7;StringHash sh1(s, p1, mod);StringHash sh2(s, p2, mod);int n = s.length();vector<int> ln;for (int i = 0; i < n; i++) {if (sh1.query(0, i) == sh1.query(n - 1 - i, n - 1) && sh2.query(0, i) == sh2.query(n - 1 - i, n - 1)) {ln.push_back(i + 1);}}int ans = 0;for (int i = 1; i < n - 1; i++) {int l = 0, r = ln.size() - 1;while (l <= r) {int m = l + (r - l) / 2;int lz = ln[m];if (i + lz < n && sh1.query(i, i + lz - 1) == sh1.query(0, lz - 1) && sh2.query(i, i + lz - 1) && sh2.query(0, lz - 1)) {l = m + 1;} else {r = m - 1;}}if (r >= 0) {ans = max(ans, ln[r]);}}if (ans > 0) {cout << s.substr(0, ans) << endl;} else {cout << "No" << endl;}return 0;
}

难度：钻石

思路: 图论

突破口：

$$所有点都经过，所有边都经过$$

那该图必然是

• 单条链
• 环

这两个图，有如下特点

• 出入度都小于等于1
• 彼此联通

因此结合这两点，通过出入度校验+并查集来求解

#include <bits/stdc++.h>using namespace std;struct Dsu {
public:Dsu(int n): m(n), arr(n, -1), gz(n, 1) {}int find(int u) {int fa = u;while (arr[fa] != -1) {fa = arr[fa];}while (arr[u] != -1) {int nfa = arr[u];arr[u] = fa;u = nfa;}return fa;}void merge(int u, int v) {int a = find(u), b = find(v);if (a != b) {arr[a] = b;gz[b] += gz[a];}}int group(int u) {return gz[find(u)];}int m;vector<int> arr;vector<int> gz;
};int main() {int t;cin >> t;while (t-- > 0) {int n, m;cin >> n >> m;// 出度，入度vector<int> in(n), out(n);Dsu dsu(n);// 不是环，就是链表for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;u--; v--;in[v]++;out[u]++;dsu.merge(u, v);}bool ok = true;for (int i = 0; i < n; i++) {if (in[i] > 1 || out[i] > 1) {ok = false;break;}}if (ok && dsu.group(0) == n) {cout << "YES" << endl;} else {cout << "NO" << endl;}}return 0;
}