我等蒟蒻爆零之后，问LincHpin大爷：“此等神题可有甚么来头？”
LincHpin:“此三题皆为当年ZXR前辈所留。”
固名之，ZXR专场，233~~~
T1 勤奋的YouSiki
这个题在BZOJ和HDU上都有身影，一样不一样的吧，反正意思差不多，想法也很相近。
首先就是发现mex函数的一个性质——当左端点固定时，函数值随右端点单调，即$mex(i,j) \leq mex(i,j+1)$。
然后，我们这么做：先$O(N)$求出以1位左端点，右端点分别为$i=1..n$的mex函数值，然后不断将左端点向右移动。
当左端点从$i$移动到$i+1$时，会使得$num_{i}$从维护序列中消失，考虑对那些mex函数值的影响。
首先，$mex_{1}$到$mex_{i}$的函数值已经没用了，可以忽略。
如果我们已经知道$num_{i}$下一次出现的位置是$next_{i}$，那么从$i$到$next_{i}-1$区间内的所有mex值都应当对$num_{i}$取min。
又因为mex函数值一直保持单调性，所有可以二分出来需要修改的区间，然后就变成了区间修改，区间求和，那就是线段树了。
#include <cstdio>
#include <cstring> inline char nextChar(void)
{
static const int siz = << ; static char buf[siz];
static char *hd = buf + siz;
static char *tl = buf + siz; if (hd == tl)
fread(hd = buf, , siz, stdin); return *hd++;
} inline int nextInt(void)
{
register int ret = ;
register bool neg = false;
register char bit = nextChar(); for (; bit < ; bit = nextChar())
if (bit == '-')neg ^= true; for (; bit > ; bit = nextChar())
ret = ret * + bit - ''; return neg ? -ret : ret;
} typedef long long lnt; const int siz = ; int n, num[siz]; int nxt[siz];
int lst[siz];
int mex[siz]; bool vis[siz]; inline void prework(void)
{
for (int i = ; i <= n; ++i)
lst[i] = n + ; for (int i = n; i >= ; --i)
{
nxt[i] = lst[num[i]];
lst[num[i]] = i;
} memset(vis, false, sizeof(vis)); int ans = ; for (int i = ; i <= n; ++i)
{
vis[num[i]] = true; while (vis[ans])
++ans; mex[i] = ans;
}
} lnt sum[siz << ];
lnt tag[siz << ];
int son[siz << ]; void build(int t, int l, int r)
{
tag[t] = -; if (l == r)
sum[t] = son[t] = mex[l];
else
{
int mid = (l + r) >> ; build(t << , l, mid);
build(t << | , mid + , r); son[t] = son[t << | ];
sum[t] = sum[t << ] + sum[t << | ];
}
} inline void addtag(int t, lnt v, lnt k)
{
son[t] = v;
tag[t] = v;
sum[t] = v * k;
} inline void pushdown(int t, int l, int r)
{
int mid = (l + r) >> ;
addtag(t << , tag[t], mid - l + );
addtag(t << | , tag[t], r - mid);
tag[t] = -;
} lnt query(int t, int l, int r, int x, int y)
{
if (l == x && r == y)
return sum[t];
else
{
if (~tag[t])
pushdown(t, l, r); int mid = (l + r) >> ; if (y <= mid)
return query(t << , l, mid, x, y);
else if (x > mid)
return query(t << | , mid + , r, x, y);
else return
query(t << , l, mid, x, mid)
+ query(t << | , mid + , r, mid + , y);
}
} int query(int t, int l, int r, int v)
{
if (son[t] <= v)
return n + ; if (l == r)
return l; if (~tag[t])
pushdown(t, l, r); int mid = (l + r) >> ; int s = son[t << ]; if (s > v)
return query(t << , l, mid, v);
else
return query(t << | , mid + , r, v);
} void change(int t, int l, int r, int x, int y, lnt v)
{
if (l == x && r == y)
addtag(t, v, r - l + );
else
{
if (~tag[t])
pushdown(t, l, r); int mid = (l + r) >> ; if (y <= mid)
change(t << , l, mid, x, y, v);
else if (x > mid)
change(t << | , mid + , r, x, y, v);
else
{
change(t << , l, mid, x, mid, v);
change(t << | , mid + , r, mid + , y, v);
} son[t] = son[t << | ];
sum[t] = sum[t << ] + sum[t << | ];
}
} inline void solve(void)
{
lnt ans = 0LL; prework(); build(, , n); for (int i = ; i <= n; ++i)
{
ans += query(, , n, i, n); int pos = query(, , n, num[i]); // first > num[i] if (pos <= nxt[i] - )
change(, , n, pos, nxt[i] - , num[i]);
} printf("%lld\n", ans);
} signed main(void)
{
freopen("mex.in", "r", stdin);
freopen("mex.out", "w", stdout); n = nextInt(); for (int i = ; i <= n; ++i)
num[i] = nextInt(); for (int i = ; i <= n; ++i)
if (num[i] > n)
num[i] = n; solve(); fclose(stdin);
fclose(stdout); return ;
}
网上还有一个比较神的算法，复杂度据说是有保证的，小伙伴说是$O(NlogN)$的，我等蒟蒻目瞪口呆。
令$sum_{i}=\sum_{1 \leq j \leq i}{mex_{j,i}}$，发现这东西也具有单调性，及$sum_{i} \leq sum_{i+1}$。
然后另i从1不断变大，即sum的右端点不断右移。每次考虑新加入$num_{i}$对当前$sum$的影响。只需要计算出有多少个sum值需要+1即可，还需要暴力枚举数字，不知道为什么复杂度是有保证的，跑得还迷之快~~~
#include <cstdio> const int siz = ; int n, num[siz], lst[siz], pos[siz]; signed main(void)
{
freopen("mex.in", "r", stdin);
freopen("mex.out", "w", stdout); scanf("%d", &n); for (int i = ; i <= n; ++i)
scanf("%d", num + i); long long ans = 0LL, now = 0LL; for (int i = , p; i <= n; ++i, ans += now)
if (num[i] < n)
{
p = lst[num[i]];
lst[num[i]] = i; for (int j = num[i]; j < n; ++j)
{
pos[j] = lst[j];
if (j && pos[j] > pos[j - ] )
pos[j] = pos[j - ];
if (pos[j] > p)
now += pos[j] - p;
else break;
}
} printf("%lld\n", ans); return fclose(stdin), fclose(stdout), ;
}
T2 贪玩的YouSiki
贪心思想。首先左边一列点是行，右边一列点是列，中间连线表示点。然后不断找交错路，在上面交错染色。注意染色的顺序即可。别问为啥，证明请找大爷。
#include <cstdio>
#include <algorithm> const int siz = ; int n, X[siz], Y[siz]; int mapX[siz], totX;
int mapY[siz], totY; int hd[siz], to[siz], nt[siz], tot = , ans[siz]; inline void add(int a, int b)
{
nt[++tot] = hd[a]; to[tot] = b; hd[a] = tot;
nt[++tot] = hd[b]; to[tot] = a; hd[b] = tot;
} void dfs(int u, int k)
{
int e = hd[u];
while (e && !to[e])
e = nt[e];
hd[u] = nt[e];
if (e)
{
to[e ^ ] = ;
ans[e >> ] = k;
dfs(to[e], !k);
}
} signed main(void)
{
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout); scanf("%d", &n); for (int i = ; i <= n; ++i)
{
scanf("%d%d", X + i, Y + i);
mapX[++totX] = X[i];
mapY[++totY] = Y[i];
} std::sort(mapX + , mapX + + totX);
std::sort(mapY + , mapY + + totY); totX = std::unique(mapX + , mapX + + totX) - mapX;
totY = std::unique(mapY + , mapY + + totY) - mapY; for (int i = ; i <= n; ++i)
{
X[i] = std::lower_bound(mapX + , mapX + totX, X[i]) - mapX;
Y[i] = std::lower_bound(mapY + , mapY + totY, Y[i]) - mapY;
} for (int i = ; i <= n; ++i)
add(X[i], Y[i] + totX - ); for (int i = ; i <= totX + totY - ; ++i)
for (int j = ; hd[i]; j = !j)dfs(i, j); for (int i = ; i <= n; ++i)
printf("%d", ans[i]); return fclose(stdin), fclose(stdout), ;
}
T3 另一个YouSiki
首先发现，这和数字大小没什么关系，只需要看是不是0就行，毕竟一个正数再怎么乘，再怎么加也还是正数。
然后把01矩阵看成邻接矩阵，$A^{K}$就是走$K$步，从$i$到$j$的路径方案数。题目又保证有至少一个自环，所以只需要关心连通性问题，即这个图是否满足从任意一个点都能到达其他所有点。这个，tarjan吧。
#include <cstdio>
#include <cstring> inline char nextChar(void)
{
static const int siz = << ; static char buf[siz];
static char *hd = buf + siz;
static char *tl = buf + siz; if (hd == tl)
fread(hd = buf, , siz, stdin); return *hd++;
} inline int nextInt(void)
{
register int ret = ;
register bool neg = false;
register char bit = nextChar(); for (; bit < ; bit = nextChar())
if (bit == '-')neg ^= true; for (; bit > ; bit = nextChar())
ret = ret * + bit - ''; return neg ? -ret : ret;
} const int siz = ; int n, hd[siz], to[siz], nt[siz], tot; inline void add(int u, int v)
{
nt[++tot] = hd[u]; to[tot] = v; hd[u] = tot;
} int dfn[siz], low[siz], tim, flag; inline void Min(int &a, int b)
{
if (a > b)a = b;
} void tarjan(int u)
{
dfn[u] = low[u] = ++tim; for (int i = hd[u]; i; i = nt[i])
if (!dfn[to[i]])
tarjan(to[i]), Min(low[u], low[to[i]]);
else
Min(low[u], dfn[to[i]]); if (low[u] == dfn[u])
flag &= (u == );
} signed main(void)
{
freopen("another.in", "r", stdin);
freopen("another.out", "w", stdout); for (int cas = nextInt(); cas--; )
{
n = nextInt(); memset(hd, , sizeof(hd)), tot = ;
memset(dfn, , sizeof(dfn)), tim = ; for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j)
if (nextInt())add(i, j); flag = true; tarjan(); for (int i = ; i <= n; ++i)
flag &= (dfn[i] != ); puts(flag ? "YES" : "NO");
} return fclose(stdin), fclose(stdout), ;
}
@Author: YouSiki