HZ怎么老考试啊23333
考试前一天占个坑。给自己的忠告：想不出正解就别想了，暴力打满Rank就不会难看QaQ
---华丽的分割线---
考完了，Rank14，我又boomboomboom了orz
最后T3的暴力还是没打出来，我就是个想不出正解还要ning想的DD
T1:匹配
我是Sb
一眼KMP，刚正不阿的cwy不会忘记了看猫片，果断\(O(N^2)\)暴力走人（
后来一看正解居然是蛤希，我草了，，，早知道就ning干力QAQ
考场上现推KMP估计还是能推出来的，如果能多想想就好了
简直对不起图巨
而且想不到KMP为啥不想想别的啊。。。懊悔中
复习下KMP：
\(nxt[i]\)表示了\(S[,i]\)的前缀最长border的位置，当我们要匹配一个新的字母，我们设定一个指针p = nxt[i - 1]，如果S[i] = S[p+1]说明匹配大成功，p+1就是\(S[,i]\)的前缀最长border的位置，否则p指针一直往回跳，最恶情况就是无法匹配，一直跳到了1。
#include <bits/stdc++.h>
const int N = 300000 + 233;
int T, la, lb, nxt[N];
char a[N], b[N], add[5];
signed main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &la, &lb);
scanf("%s%s", a + 1, add);
a[la + 1] = '$', ++la;
for (int i = 1; i <= lb; i++) a[i + la] = a[i];
a[la + lb + 1] = add[0];
for (int i = 2; a[i]; i++) {
int p = nxt[i - 1];
while (p && a[i] != a[p + 1]) p = nxt[p];
if (a[i] == a[p + 1]) nxt[i] = p + 1;
}
printf("%d\n", nxt[la + lb + 1]);
memset(nxt, 0, sizeof(nxt));
}
return 0;
}T2:回家
我离AC只差一个90w的数组
一眼求割点，速码开T3。T3写完，二眼好像不对，割点不一定在1-n路径上。于是赶回来修锅，建个圆方树，dfs求出1-n经过的圆点。
然后就MLE了？？？？红太阳GMK说他数组开小了，我跟风给常数乘个10.
然后我就A了？？？
这题还是挺显然的，思路秒出
考试时候千万别吝啬空间，够开就开，QAQ
#include <bits/stdc++.h>
const int N = 2000000 + 233;
int T, n, m, ans;
struct Edge {int to, nxt;} e[N << 2], c[N << 2];
int ecnt, head[N], ccnt, hc[N], tot;
bool yes[N];
inline int R() {
int a = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a;
}
int low[N], dfn[N], num, stk[N], p;
inline void AddEdge(int f, int to) {
e[++ecnt] = {to, head[f]}, head[f] = ecnt;
}
inline void AddC(int f, int to) {
c[++ccnt] = {to, hc[f]}, hc[f] = ccnt;
}
void Tarjan(int x) {
dfn[x] = low[x] = ++num;
stk[++p] = x;
for (int i = head[x], y = e[i].to; i; i = e[i].nxt, y = e[i].to) {
if (!dfn[y]) {
Tarjan(y);
low[x] = std::min(low[x], low[y]);
if (dfn[x] == low[y]) {
AddC(x, ++tot), AddC(tot, x); int z;
do {
z = stk[p--], AddC(z, tot), AddC(tot, z);
} while (y != z);
}
} else low[x] = std::min(low[x], dfn[y]);
}
}
void dfs(int x, int fa) {
for (int i = hc[x], y = c[i].to; i; i = c[i].nxt, y = c[i].to) {
if (y != fa) {
dfs(y, x);
if (y == n) return (void) (yes[x] = 1);
else if (yes[y]) yes[x] = 1;
}
}
}
signed main() {
T = R();
while (T--) {
n = R(), m = R(), tot = n;
for (int i = 1, x, y; i <= m; i++)
x = R(), y = R(), AddEdge(x, y), AddEdge(y, x);
Tarjan(1);
dfs(1, 0);
for (int i = 2; i < n; i++)
if (yes[i]) ans++;
printf("%d\n", ans);
for (int i = 2; i < n; i++)
if (yes[i]) printf("%d ", i);
if (ans) printf("\n");
memset(head, 0, sizeof(head));
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
memset(hc, 0, sizeof(hc));
memset(stk, 0, sizeof(stk));
memset(yes, 0, sizeof(yes));
num = ecnt = ccnt = ans = p = 0;
}
return 0;
}T3:寿司
开始想着会不会是一个类似与Data Backup的贪心思路，推了一段时间开码，码完发现不对，完全失败，这时发现T2有问题去修锅。
修完锅继续想，zzz，想不出来，好像只会打暴力DFS，码码码，没码完到点了，GG
考完看题解，发现我过于Noob，无法看出出题人的显然性质。
我们看到环很自然就破环为链，这时我们枚举从上头选个环的断点。