在题解的最下面放出了每个点的标程。
matthew99的博客
博客
《UOIP十合一》标程已经放出
2016-07-07 16:14:38 By matthew99
《UOIP十合一》解题报告
2016-06-26 19:48:35 By matthew99
题目地址
Q&A
羊芳斐、牛芳斐、马芳斐、欧阳芳斐，黄瓜条以及共价大爷是谁？
羊芳斐、牛芳斐、马芳斐、欧阳芳斐，黄瓜条他们都是WC2015小品《时光2》中的角色，黄瓜条当时是由UOJ创始人之一vfleaking扮演的。
共价大爷的ID是zhangzj，是目前雅礼机房的红太阳，神通广大，无所不能，切题如麻，所向披靡。
“中国国家队以7分钟的罚时之差惜败给俄罗斯国家队”是什么典故？
这里影射WF2016上上海交通大学队以7分钟只差败给圣彼得堡州立大学队，作者出此题时WF2016刚结束不久。
每个点的做法
测试点1
容易发现，对于所有$x \rightarrow y$的边，都有$x \le y$，去掉自环后无论怎么选都不会有环，因此答案显然是2的非自环边数次幂。
测试点2
容易发现这张图是由若干个边数很少的连通块组成的，而连通块之间显然是独立的，因此答案就是每个连通块的答案乘起来，而每个连通块的答案显然可以直接暴力算。
测试点3
容易发现这张图每个连通块都只有一个环，而对于一个大小为$x$的环，答案是$2 ^ x - 1$，答案就是所有环的答案乘起来再乘上2的不在环上的点数次幂。
测试点4
容易发现这张图是由很多层组成的，每层最多4个点，且只有相邻两层之间有连边，因此我们直接状压连通性，对于两层之间的转移，可以枚举边的子集之后用Floyd或者是BFS。
测试点5
这个点如果不进行一些猜测，是很难做出来的，我们可以发现这张图每个强连通分量边数都很少，而连接两个属于不同强连通分量的点的边选和不选是没有影响的，因此可以直接将答案乘2，对于每个强连通分量我们直接暴力然后将答案乘起来即可。
什么你不会求强连通分量？因为点数少的令人感动所以直接按定义用Floyd就行了。
测试点6
这个点是一个有向完全图，对于有向完全图，我们考虑枚举最终DAG中入度为0的点是哪一些，令$a_n$表示$n$个点的有向完全图的生成DAG个数，很容易得到递推式：
$a_n = \sum_{k = 1}^{n}{\binom{n}{k}{(-1)}^{k + 1}2^{k(n - k)}a_{n - k}}$。
设$a_0 = 1$，通过递推容易求出答案。
测试点7、测试点8
这个两个点$n$都非常小，且没有重边和自环，同测试点6的思路，设$\mathrm{dp}_S$表示$S$这个子集中的生成DAG个数，那么有递推式。
$\mathrm{dp}_S = \sum_{S\prime \subset S, S\prime \ne S}{{(-1)}^{|S| - |S\prime| + 1}2^{E_{S\prime, S - S\prime}}\mathrm{dp}_{S\prime}}$。
其中$E_{S_1, S_2}(S_1 \bigcap S_2 = \emptyset)$ 表示从$S_1$中某个点连向$S_2$中某个点的边的条数。
设$\mathrm{dp}_{\emptyset} = 1$，通过递推容易求出答案。然而直接做的话时间复杂度是$O(3 ^ n n)$ 的，瓶颈在于$E$的计算。我们考虑倒过来DP，从枚举子集改成枚举超集，也就是我们用$\mathrm{dp}_{S\prime}$来反过来更新$\mathrm{dp}_S$，这样的话对应的$E$的值就很好计算了。时间复杂度降为$O(3 ^ n)$。8号点最多几分钟就可以出解。
如果时间复杂度过高或者剩余时间不够的话，可能只能做出测试点7。
测试点9、测试点10
这两个点的特点是，一开始有一个大小为$k + 1$的竞赛图，接下来所有点都与前面$k$个两两之间存在边（即要么从$a$连向$b$要么从$b$连向$a$）的点连一条方向任意的边（即要么由这个点连去要么由那个点连过来）。
容易发现进行树分解后的树宽度是$k$，且$k$很小（9号点是2，10号点是3）。
我们容易将图树分解成这样：除了根之外，每个点的集合都与父亲之差了一个点。
根据树分解的性质，我们容易设计状压DP，同测试点4，我们状压两两之间的连通性。两个子树之间的合并就是直接合并连通性。对于非根的节点我们枚举那个不在父亲的集合中的点向其他点连的边的子集然后转移，对于根我们直接枚举边的子集转移。这样就可以做出这两个点了。
如果不熟悉图树分解，直接进行一系列的思考也可以想出这两个点的做法。
程序
测试点1
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int ans = 1;
REP(i, 0, m)
{
int x, y;
scanf("%d%d", &x, &y);
if (x != y) (ans <<= 1) %= Mod;
}
printf("%d\n", ans);
return 0;
}测试点2
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int maxn = 5;
int n, m;
int main()
{
scanf("%d%d", &n, &m), n /= 10, m /= 10;
int ans = 1;
REP(i, 0, 10)
{
vector<pair<int, int> > ed;
REP(j, 0, m)
{
int u, v;
scanf("%d%d", &u, &v), --u, --v, u -= i * n, v -= i * n;
if (u != v) ed.pb(mp(u, v));
}
int tmp = 0;
REP(j, 0, 1 << SZ(ed))
{
static bool f[maxn + 5][maxn + 5];
memset(f, 0, sizeof f);
REP(k, 0, SZ(ed)) if (j >> k & 1) f[ed[k].x][ed[k].y] = 1;
REP(k, 0, n) REP(i, 0, n) if (f[i][k]) REP(j, 0, n) if (f[k][j]) f[i][j] = 1;
bool failed = 0;
REP(i, 0, n) REP(j, 0, i) if (f[i][j] && f[j][i]) { failed = 1; break; }
if (!failed) ++tmp;
}
ans = (LL)ans * tmp % Mod;
}
printf("%d\n", ans);
return 0;
}测试点3
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int maxn = 100000;
int n;
int fa[maxn + 5];
int lst[maxn + 5];
int pw[maxn + 5];
int main()
{
scanf("%d%*d", &n);
REP(i, 0, n) scanf("%*d%d", fa + i), --fa[i];
pw[0] = 1;
REP(i, 0, n) pw[i + 1] = (pw[i] << 1) % Mod;
memset(lst, -1, sizeof lst);
int cur = 0;
int ans = 1;
int cnt = 0;
REP(i, 0, n) if (!~lst[i])
{
int u = i;
while (1)
{
lst[u] = cur++;
u = fa[u];
if (~lst[u])
{
if (lst[u] >= lst[i])
{
cnt += cur - lst[u];
ans = (LL)ans * (pw[cur - lst[u]] - 1) % Mod;
}
break;
}
}
}
ans = (LL)ans * pw[n - cnt] % Mod;
printf("%d\n", ans);
return 0;
}测试点4
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int maxn = 1000, maxk = 4;
int n, m, K = maxk;
int dp[maxn + 5][(1 << ((maxk * (maxk - 1)))) + 5];
int main()
{
scanf("%d%d", &n, &m);
n /= maxk, m /= n - 1;
dp[0][0] = 1;
REP(i, 0, n - 1)
{
vector<pair<int, int> > ed;
REP(j, 0, m)
{
int u, v;
scanf("%d%d", &u, &v), --u, --v;
u -= i * K;
v -= i * K;
ed.pb(mp(u, v));
}
REP(j, 0, 1 << (K * (K - 1)))
if (dp[i][j])
{
static bool f[(maxk << 1) + 5][(maxk << 1) + 5];
REP(k, 0, 1 << SZ(ed))
{
memset(f, 0, sizeof f);
int cur = 0;
REP(u, 0, K) REP(v, 0, K) if (u != v) f[u][v] = (j >> (cur++) & 1);
REP(u, 0, SZ(ed)) if (k >> u & 1) f[ed[u].x][ed[u].y] = 1;
REP(w, 0, K << 1) REP(u, 0, K << 1) if (f[u][w]) REP(v, 0, K << 1) if (f[w][v]) f[u][v] = 1;
bool failed = 0;
REP(u, 0, K << 1) REP(v, 0, u) if (f[u][v] && f[v][u]) { failed = 1; break; }
if (failed) continue;
int nxt = 0;
cur = 0;
REP(u, 0, K) REP(v, 0, K) if (u != v) nxt |= f[u + K][v + K] << (cur++);
(dp[i + 1][nxt] += dp[i][j]) %= Mod;
}
}
}
int ans = 0;
REP(i, 0, 1 << (K * (K - 1))) (ans += dp[n - 1][i]) %= Mod;
printf("%d\n", ans);
return 0;
}测试点5
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int maxn = 110;
int n, m;
bool f[maxn + 5][maxn + 5];
int ori[maxn + 5][maxn + 5];
int N = 0;
int bel[maxn + 5];
int main()
{
scanf("%d%d", &n, &m);
REP(i, 0, m)
{
int u, v;
scanf("%d%d", &u, &v), --u, --v;
f[u][v] = 1;
++ori[u][v];
}
REP(i, 0, n) f[i][i] = 1;
REP(k, 0, n) REP(i, 0, n) if (f[i][k]) REP(j, 0, n) if (f[k][j]) f[i][j] = 1;
int ans = 1;
memset(bel, -1, sizeof bel);
REP(i, 0, n) if (!~bel[i])
{
vector<int> all;
REP(j, 0, n) if (f[j][i] && f[i][j]) all.pb(j), bel[j] = N;
++N;
vector<pair<int, int> > ed;
for (auto x : all) for (auto y : all) if (x != y) REP(j, 0, ori[x][y]) ed.pb(mp(x, y));
int tmp = 0;
REP(j, 0, 1 << SZ(ed))
{
static bool g[maxn + 5][maxn + 5];
memset(g, 0, sizeof g);
REP(k, 0, SZ(ed)) if (j >> k & 1) g[ed[k].x][ed[k].y] = 1;
for (auto w : all) for (auto u : all) if (g[u][w]) for (auto v : all) if (g[w][v]) g[u][v] = 1;
bool failed = 0;
for (auto u : all) for (auto v : all) if (u != v && g[u][v] && g[v][u]) { failed = 1; break; }
if (!failed) ++tmp;
}
ans = (LL)ans * tmp % Mod;
}
REP(i, 0, n) REP(j, 0, n) if (bel[i] != bel[j]) REP(k, 0, ori[i][j]) (ans <<= 1) %= Mod;
printf("%d\n", ans);
return 0;
}测试点6
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int maxn = 110;
int n;
int C[maxn + 5][maxn + 5];
int pw[maxn * maxn + 5];
int a[maxn + 5];
int ans;
int main()
{
REP(i, 0, maxn + 1)
{
C[i][0] = 1;
REP(j, 1, i + 1) (C[i][j] = C[i - 1][j - 1] + C[i - 1][j]) %= Mod;
}
pw[0] = 1;
REP(i, 0, maxn * maxn) pw[i + 1] = (pw[i] << 1) % Mod;
a[0] = 1;
REP(i, 1, maxn + 1)
{
a[i] = 0;
REP(j, 1, i + 1)
{
int tmp = (LL)a[i - j] * pw[j * (i - j)] % Mod * C[i][j] % Mod;
if (j & 1) (a[i] += tmp) %= Mod;
else (a[i] -= tmp) %= Mod;
}
}
scanf("%d", &n);
ans = (a[n] + Mod) % Mod;
printf("%d\n", ans);
return 0;
}测试点7、测试点8
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define clz __builtin_clz
#define ctz __builtin_ctz
#define bcnt __builtin_popcount
#define bpar __builtin_parity
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int maxn = 20;
int n, m;
int from[maxn + 5], to[maxn + 5];
int dp[(1 << maxn) + 5];
int ans = 0;
int nxt[maxn + 5];
int bc[(1 << maxn) + 5];
int oriS;
void dfs(int x, int S, int mul)
{
if (x == n)
{
if (S != oriS) (dp[S] += mul) %= Mod;
return;
}
dfs(nxt[x], S, mul);
dfs(nxt[x], S | (1 << x), ((LL)-mul << (bc[to[x] & oriS])) % Mod);
}
int main()
{
scanf("%d%d", &n, &m);
REP(i, 0, 1 << n) bc[i] = bcnt(i);
REP(i, 0, m)
{
int u, v;
scanf("%d%d", &u, &v), --u, --v;
from[u] |= 1 << v;
to[v] |= 1 << u;
}
dp[0] = 1;
REP(i, 0, 1 << n) if (dp[i])
{
oriS = i;
int now = n;
for (int j = n - 1; j >= 0; --j)
{
nxt[j] = now;
if (~i >> j & 1) now = j;
}
dfs(now, i, -dp[i]);
}
ans = dp[(1 << n) - 1];
(ans += Mod) %= Mod;
printf("%d\n", ans);
return 0;
}测试点9、测试点10
以下是测试点10的程序，测试点9的程序和测试点10的程序的区别参见代码注释。
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int maxn = 1100;
const int per = 3;//测试点9中per = 2
const int maxmask = 1 << (per * (per + 1));
int n, m;
int N;
vector<int> chd[maxn + 5];
vector<int> belong[maxn + 5];
int fa[maxn + 5];
map<int, int> rk[maxn + 5];
vector<int> what[maxn + 5];
int w[maxn + 5];
int dp[maxn + 5][maxmask + 5];
int tr[maxmask + 5];
bool ok[maxmask + 5];
vector<pair<int, int> > rt_ed;
int id[per + 5][per + 5];
inline void deal(int *f)
{
REP(w, 0, per + 1) REP(u, 0, per + 1) if (f[u] >> w & 1) f[u] |= f[w];
}
inline void masktoa(int x, int *f)
{
REP(u, 0, per + 1) f[u] = 0;
REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v && (x >> id[u][v] & 1)) f[u] |= 1 << v;
}
inline int atomask(int *f)
{
int ret = 0;
REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v && (f[u] >> v & 1)) ret |= 1 << id[u][v];
return ret;
}
void dfs(int x)
{
memset(dp[x], 0, sizeof dp[x]);
dp[x][0] = 1;
for (auto y : chd[x]) dfs(y);
static int sum[maxmask + 5];
memset(sum, 0, sizeof sum);
if (~fa[x])
{
REP(i, 0, maxmask) if (dp[x][i])
{
REP(j, 0, 1 << per)
{
static int f[per + 5];
masktoa(i, f);
REP(u, 0, per) if (j >> u & 1)
{
if (w[x] >> u & 1) f[per] |= 1 << u;
else f[u] |= 1 << per;
}
deal(f);
if (!ok[atomask(f)]) continue;
int mask = 0;
REP(u, 0, per) REP(v, 0, per) if (u != v && (f[u] >> v & 1)) mask |= 1 << id[what[x][u]][what[x][v]];
if (ok[mask]) (sum[mask] += dp[x][i]) %= Mod;
}
}
static int nxt[maxmask + 5];
memset(nxt, 0, sizeof nxt);
REP(i, 0, maxmask) if (dp[fa[x]][i]) REP(j, 0, maxmask) if (sum[j] && ok[tr[i | j]]) (nxt[tr[i | j]] += (LL)dp[fa[x]][i] * sum[j] % Mod) %= Mod;
memcpy(dp[fa[x]], nxt, sizeof dp[fa[x]]);
}
else
{
REP(i, 0, maxmask) if (dp[x][i])
{
REP(j, 0, 1 << SZ(rt_ed))
{
static int f[per + 5];
masktoa(i, f);
REP(k, 0, SZ(rt_ed)) if (j >> k & 1) f[rt_ed[k].x] |= 1 << rt_ed[k].y;
int mask = atomask(f);
mask = tr[mask];
if (ok[mask]) (sum[mask] += dp[x][i]) %= Mod;
}
}
memcpy(dp[x], sum, sizeof dp[x]);
}
}
int main()
{
int cnt = 0;
REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v) id[u][v] = cnt++;
REP(i, 0, maxmask)
{
ok[i] = 1;
REP(u, 0, per + 1) REP(v, 0, u) if ((i >> id[u][v] & 1) && (i >> id[v][u] & 1)) ok[i] = 0;
static int f[per + 5];
masktoa(i, f);
deal(f);
tr[i] = atomask(f);
}
scanf("%d%d", &n, &m);
memset(dp, 0, sizeof dp);
REP(i, 0, per * (per + 1) >> 1)
{
int u, v;
scanf("%d%d", &u, &v), --u, --v;
rt_ed.pb(mp(u, v));
}
REP(i, 0, per + 1) belong[i].pb(0), rk[i][0] = i;
fa[0] = -1;
N = 1;
REP(i, per + 1, n)
{
w[N] = 0;
what[N].clear();
REP(j, 0, per)
{
int u, v;
scanf("%d%d", &u, &v), --u, --v;
if (u == i) w[N] |= 1 << j, what[N].pb(v);
else what[N].pb(u);
}
vector<int> &all(what[N]);
assert(!all.empty());
vector<int> now(belong[all[0]]);
REP(j, 1, SZ(all))
{
vector<int> nxt;
set_intersection(ALL(now), ALL(belong[all[j]]), back_inserter(nxt));
now = nxt;
}
assert(!now.empty());
fa[N] = *now.begin();
chd[fa[N]].pb(N);
belong[i].pb(N);
rk[i][N] = SZ(all);
REP(j, 0, SZ(all))
{
int &u = all[j];
belong[u].pb(N);
rk[u][N] = j;
u = rk[u][fa[N]];
}
++N;
}
dfs(0);
int ans = 0;
REP(i, 0, maxmask) (ans += dp[0][i]) %= Mod;
(ans += Mod) %= Mod;
printf("%d\n", ans);
return 0;
}《共价大爷游长沙》解题报告
2016-06-26 19:37:35 By matthew99
题目地址
Q&A
题目名称怎么来的？
本题题名是跟风另外两道题目的，另外两道题目的题目名见题面第一句话。
共价大爷和小L是谁？
共价大爷的ID是zhangzj，是目前雅礼机房的红太阳，神通广大，无所不能，切题如麻，所向披靡。
小L的ID是luoyuchu，他是共价大爷的忠实粉丝。
长沙市真的总是在不断的施工吗？
的确是的，比如说从雅礼到我现在住的地方就有多处施工点。雅礼操场目前在施工，已经挖出了多座古墓，甚至曾经被以为是太守坟。
算法一
直接上暴力，每次对于所有路径将它经过的边边权加一，然后看看询问的路径边权是否为$|S|$，时间复杂度$O(n ^ 2m)$，期望得分10分。
算法二
如果没有加边删边操作和删除点对操作，那么我们可以维护当前的可行路径，每次可以用$O(\log n)$或者$O(1)$时间进行树上路径求交以及判断一条边是否在路径上，如果使用倍增，则时间复杂度为$O((n + m)\log n)$，期望得分20分，结合算法一可以获得30分。
算法三
如果没有加边删边操作，那么我们可以用动态树或者树链剖分等支持链修改单点询问的结构，维护每个点被路径经过的次数，每次看看询问边的两个端点是否都被经过了$|S|$次。如果使用LCT那么时间复杂度$为O((n + m) \log n)$，期望得分40分，结合算法一可以获得50分。
算法四
对于没有加边删边操作的数据，我们还有一种做法，我们对所有点对建一棵线段树，每个节点存子树中所有路径的交，每次操作的时候都很容易在线段树上update解决，如果用ett序或者dfs序加ST表，那么每次可以在$O(1)$的时间内update，总时间复杂度为$O(n \log n + m \log m)$，期望得分40分，结合算法一可以获得50分。
算法五
对于$|S| \le 10$的数据，我们可以每次询问的时候进行和算法三类似的操作，每次暴力加入所有路径维护每个点被经过的次数再用同样的方法询问，期望得分20分，结合前面的算法可以获得70分。
算法六
我们注意到，一条$x$到$y$路径被所有路径经过，当前仅当以$x$为根时，所有路径的端点都恰好有一个在$y$的子树中。这样，我们对每一个路径随机一个权值，然后每次加入删除路径时，将两个段点的点权异或上这个权值，然后用动态树维护子树权值异或和，每次询问对应子树内的权值异或和是否是当前所有路径的权值异或和，权值如果设为$10 ^ 9$级别，就基本不可能出错了。时间复杂度$O((n + m) \log n)$，空间复杂度$O(n)$，可以通过全部数据。
算法七
这题罗哲正同学提出了另外一种做法，我们可以将权值异或在一条链上，新加入一条边的时候，新形成的环上必然有一条边会被删除，假设这条边是$u$和$v$之间的边。我们发现，将这条被删除的边的权值异或到删除这条边后$u$和$v$之间的路径上，就可以更新新树上对应的权值了。时空复杂度均和算法六一样，也可以通过全部数据。
关于“鏖战表达式”错误复杂度算法水过现象的看法
2016-02-27 21:42:39 By matthew99
WC2016鏖战表达式一题，松爷(王逸松，鏖战表达式出题人)在WC上讲了复杂度为每次操作$O(k + \log n)$的做法，即所谓的树(套树)$^*$。然而民间流行一种直接用treap维护的，并把优先级比较定为比较运算符，运算符相同则根据子树大小用概率比较的做法，复杂度为$O(k\log n)$，为什么呢，因为我们先加入一堆1，再加入一堆2，一直到一堆k，每一次新加入一堆运算符，不能改变前面运算符的形态，因此复杂度是$O(k \log n)$，直接提交会得到七十到八十的分数，由于此题数据强度不大，因此稍微根据数据进行修改一些实现细节即可水过。
松爷与我曾多次提到过此事，我也认为此事十分不妥，作为一个很好的数据结构题，留下的却是一堆的水过，以及不断的有新人抱着以为这是正确的做法的心态去写，最后却死活过不去而只能跟着水过的事情。幸运的是考场上并没有人水过。
本题作为一道特殊的题，难以像现在大部分UOJ上的题一样支持hack和extra test，甚至考场数据和grader都使用了特殊的方法加密，因此想要阻止这种现象只要两条路，一是通过@vfleaking等管理员来手工添加一些extra tests强行卡掉复杂度错误的算法，二是靠大家的理解和自觉，理解这种算法的不正确性，并自觉不使用这种算法。
这里我提醒一下大家不要再陷入错误做法的泥潭中。
对于那个$O(k \log n)$的做法，本人也进行了一些改进，可以参见http://uoj.ac/submission/50137 。注意，提交统计里面显示的我的提交是我之前跟着大家水过的程序，并不是这份代码。
我大概是在merge和split的时候进行了一些rotate，具体复杂度无法给出详细证明，但是感觉是$O(k + \log n)$的可能性还是比较大的（当然也有可能是$O(k\log n)$，或者甚至$O(\sqrt{k}\log n)$, $O(k \log k + \log n)$, $O(k \log \log n + \log n)$这些鬼畜的复杂度233，大家还可以继续脑洞），大家可以感受一下我改动的地方。如果觉得我的做法也不靠谱可以学习松爷std程序的做法。如果有谁卡掉了我的做法或者是证明了我的做法的复杂度的确是$O(k + \log n)$，欢迎与我讨论。
清华集训总结
2015-12-11 14:08:29 By matthew99
这是集训队作业的一部分。
我从主观条件和客观条件上来总结一下这次清华集训吧。
首先主观上，我有很多该拿到的分没有拿到。
第一天第二题完全可以注意到精度问题，只要注意到了精度问题，很容易发现精度误差会不断变大，然而我当时只是简简单单的把double改成long double看差异，这是十分naive的做法，看着数从整数掉下去又突变回来而我却习以为常，作为集训队员连简单的精度一时都没有应该感到羞耻......充分的体现出我在考场上考虑的东西实际上有多么欠缺。
第二天的第二题，我势能公式推对了，但是由于我用叉积算面积，没有除以二，而后面推的时候我以为它就是面积。物理功底不行的我在考场上更倾向于怀疑自己的物理水平而不是代码能力，最终否定了自己已经推出来的正确结论，这个时候我莫名其妙的以为提答题是全对才有一个点的分，这个错误我在ZJOI day2也犯过，不然应该能超过标准分。原因都是看到了评分规则，但是由于当时并不想做提答题就没管，等到想做的时候却把这个东西抛到脑后了。所以最后1h挣扎T2，当时很着急也不知道在搞什么，最后当然是只有前一个半小时有得分，最后两个半小时一分没得，由于大部分集训队员恰好这天都考挂了并且比我还惨，我意外的没有大崩盘，如果大家这天都发挥正常的话，我第二天结果应该比第四天更差。总之这一天不仅暴露出我写代码时的粗心，同时还暴露出我非常糟糕的物理能力。实际上我物理考出过100分拿40分的好成绩......
第三天前两题写完之后还有将近2h，觉得自己rank1定了，于是慢悠悠的检查前两题慢悠悠的做T3，而且我又！没！看！到！有！部！分！分！，这次很简单，看到“10个测试点，每个测试点1分”的时候，我想，不是每个测试点10分吗，不然这题满分不是10分？实际上这个指的是每个10分的点有1分的部分分，这说明我当时宁愿怀疑出题人也不怀疑自己的理解能力，这是很不对的，因为如果出题人错了肯定会更正，然而我过了一阵子就不记得有这回事了。T3做了很多分觉得自己肯定能标准分，所以最后都是一种做一个点是一个点的态度，慢慢的做，最后看到榜才如梦初醒，发现我T3基本上是全场花了很长时间的选手中做得最糟糕的，花了别人两倍的时间却比大家少十多分。而且提答题也因为自己的一个粗心大意丢了一个不该丢的1分，如果自己当时抱着一种要AC这道题的态度，以集训队选手的平均速度去做T3，应该完全有时间可以在考场上拿到100(99)分。
第四天是我发挥的十分糟糕的一天，然而导致我出问题的原因，却是我一直以来都犯了的错误。这一天我看T1，然后想了很久，想到一个错误算法开始写的时候就发现错了，然而影响了心情，后面时间过得越久人的思维能力就越差，而且对题目整体把握越糟糕，觉得这是一个很难的题，最后搞得只能写暴力，接近3h过去了却只有暴力分，相反其他人基本上都用了我一半的时间拿到了100分。看完T2我整个人急了，T2是整个清华集训中和第三天的第一题并列的最水的两题之一，然而我却2h多才开始看，就想赶快A掉，然而欲速则不达，最后还剩十多分钟的时候过了考场上的全部数据，这个时候我纠结于是否检查前两题，然而当时我觉得第一题拍过，虽然对拍不是很强但是至少还是拍过的，第二题大数据就是极限数据而且应该属于极限数据强度不错，而且当时由于不知道T3是什么题，就赶紧去看T3，生怕T3是一个所有人都会做的傻逼题，看完之后发现根本没时间做就交样例得了一份。接着还剩一分钟的时候发现第二题写错了，当时我完全被水淹没不知所措，完全属于一种GG的状态，考试便结束了，实际上当时只需要加上几个+1什么的就可以了，冷静下来还是有时间改对的。最后排名非常非常靠后，只能靠前三天的成绩保持一个微弱的优势。第四天最大的问题在于没有开场看三个题并稍微想一下，其实我四天都没有看三个题，但是前三题第一题都是我能很快想出90到100分算法的一个题，第四天我却由于失误没有想出来，这直接导致我后两题看的很晚，也导致了我T2做完不敢检查，因为我怕T3是傻逼题，实际上如果T3真是傻逼题，那么我可能这一天真的会把总名次一下子弄得很差了，而且T1在没看后两题的情况下，死磕那么长时间是非常不划算的，如果后两题都是需要很长时间但是花了时间却很好拿到满分或者高分的题，我这场基本上就没戏了，没有合理考试策略是我最大的问题，前三场完全只是运气，用这种高风险的方法恰好没有出很大问题。其次，第一题我想错了方向，整个人陷了进去，思维没有打开，而且由于紧张基本没法打开，如果第一题是在我平时做题的时候见到，那么想出来的概率还是很大的，考试紧张也是我这天的问题。第二题写错，是我没考虑周全，这也是我很大的一个问题，而且，写代码犯小错误的积累导致效率不高，想题的时候容易分心导致的效率不高，我现在无法具体想起来的许多小失误，也多多少少促进了我的滚粗。
因此，这次清华集训暴露了我许多能力的不足，做事太浮躁也是个主要问题，导致我代码写不对或者调太久，而且比较急的时候思维能力也大打折扣，可能也的确导致了一些simple的东西居然没有在考场上想出来。因此，一定要让自己做事更加冷静，更加沉下心来，每次犯错误，不管是多么小的错误，都要注意并且尽量下次避免，甚至具体到某个具体算法或者具体的常用代码的某个具体的地方，有时候一些无关紧要的习惯的积累，最后就是几十上百分的差距。
接着我再说说客观上我对整个清华集训的看法。
清华集训由于有四场考试，当然能很好的体现出每一位集训队员的水平，这次清华集训的分，当然分为没拿到的分和拿到的分，但是我所有拿到的分，却没有什么非常值得一提的，基本都是看完马上就知道怎么拿了，没拿到的分也基本上是自己的粗心大意或者时间的紧缺所致，如果时间允许，大部分的分应该都能拿到。清华集训的分，基本上要么是trivial的，要么就是会某个东西或者做过某个题就能轻轻松松获得，没做过要获得就难得多。清华集训有两个物理题，体现出了物理以及微积分水平的重要性，比如第三天第二题，会了微积分就是一个很trivial的DP，其实国内的DP题一般都是合成题，就是在DP之前还要用一些别的知识点，再比如NOI的最后一题，DP只是一个部分，网络流是另一个部分，难点往往在于你必须两个东西都会，相比之下Topcoder和Codeforces的DP题，一般都是经过一些转化才能DP，或者DP之后利用一些性质优化，或者需要设计一些特别的状态，总之难点在于有些题，可能你根本不会设状态或者转移，有些题可能方程列出来却效率太低，想AC需要一定的水平。其实不仅限于DP，这归根结底反映出一个国内OI和国际上其他赛事的差异，国内的难题，要么都是代码量特别大的，要么就是很多东西合成起来，或者需要对某个特定算法及其优化很深入的研究，而国际上的难题，很多都是代码短小，考点也只有一两项，最终算法可能非常简单并且不需要什么优化，但是却需要对问题很深入的分析，对于这个差异，个人认为两者各有所长，应该相互借鉴和促进。OI的赛制也与其他competitive programming的比赛有所不同，其他的要么就是必须AC一个题，要么就是分为若干个subtask，而国内通过一个测试点就有分，有时候一个无解就会有10分，一个样例就会有1分，而且其他的比赛，有些要求算法每一个地方都不能写错，不然就相当于什么都没做，而国内相对来说比较良心，比如第三天第二题，只要会势能公式，随便写一个三分就能有很多分，NOI的最后一题，只要算法在随机情况下效率不错，就算在极端情况下可能运行时间很长，也不至于只拿到暴力分，基本上花的时间不容易白白浪费，但是也并不意味着什么都不知道乱写一通就会有分。本次清华集训我也看到了很多新的东西，比如大量的交互题和提交答案题，都十分有趣，我也比较喜欢，突破了传统题太多的枷锁，这一方面得益于UOJ的通用性，另一方面也顺应了IOI等国际赛事上非传统题题多的潮流。
分金币问题
2015-10-26 15:56:32 By matthew99
今天的模拟题给了我们一次刻骨铭心的经历。
题目是这样的，n个人分m个金币，每个金币完整不可分。从第一个人开始，每个人提出一个分金币方案，如果投票同意的人超过半数，那么这个方案就通过，否则这个人将被杀掉。
现在假设每个人都很聪明。每个人尽可能的保证生命。如果可以保证生命，那么他希望自己分到的金币最多。如果不能过获得更多金币，就会希望别人死。如果一个人知道自己肯定要死，那么他对别人的方案会投反对票。
假设有6个人，100个金币。
对于一个人，显然分到所有金币。
对于两个人，显然第二个人必死，第一个人分到所有金币。
对于三个人，他会给自己留100个金币，其他人不分，第二个人想，自己不同意就会死，第一个人显然不会同意，而第三个人自己的方案显然会同意，所以有两个人同意，方案通过。第三个人获得100个金币，前两个人都没有金币。
对于四个人，他会给自己98个金币，第一个人和第二个人各1个金币，前两个人想，如果我不同意而给第三个人决定，那么自己就不会有金币了，因此会同意，而第四个人显然会同意，所以有三个人同意，第四个人获得98个金币，前两个人各1个金币，而第三个人得不到金币。
对于五个人，他会给自己97个金币，第三个人1个金币，第一个或者第二个人2个金币，这样第三个人肯定同意，给了2个金币的那个人也会同意，第五个人自己也同意，所以分金方案是第五个人97个金币，第三个人1个金币，第一个或者第二个人2个金币。
对于第六个人，矛盾就出现了。
考虑给自己留97个金币，第四个人1个金币，第一个和第二个人各1个金币。 自己和第四个人肯定会同意，而第一个和第二个人会不会同意呢。
第一个人和第二个人的想法是，如果自己不同意，那么自己可能一分钱没有，也可能会得到两块钱，如果他们都想保全这一块钱，那么就都会同意，反之如果有人想奋力一搏，觉得还不如不同意，说不定有两块钱，那么大家都不会同意，出现了矛盾。
如果第一个人和第二个人都清楚第五个人的选择，比如第一个人和第五个人关系特别好，他知道第五个人肯定会给他，而第二个人也清楚这一点，那么，如果是上面这样分，只会有第一个人同意，第六个人就会被杀死。
这个时候正确方案应该是自己留96，第二个人留1，第四个人留1，第三个人留2。 如果第六个人想：“唉我还这么年轻，真的不想死啊，钱是身外之物我不想要了！”，那么他就会做出这样的决策：
自己留94，第四个人留1，第三个人留3，第二个人或者第一个人留3，这样给3个金币的人肯定会同意，另外三个也会同意，自己肯定死不了。
五个人的情况似乎是小学奥数的经典内容？因为五个人的情况是没有争议的。
事实上，我考场上实现的，包括出题人的数据，都是第二个想法，就是大家都是先知，都可以预测别人的想法。然而也有相当一部分人写的是第一种想法，而第三种没听说有人写过。
实际上题面也什么也没说清楚，所以才会导致这么大的撕逼。
如果是CF或者TC遇到这种情况当然unrated咯。
但实际上大家为此撕逼了一中午和一下午233333333333333333333。各抒己见，感觉还是很好玩很刺激。
实际上如果大家都可以预测别人的想法，那两个人玩起石头剪刀布，究竟会怎么出呢，估计两个人的大脑都栈溢出咯......
事实上撕逼这种问题也不是第一次，CTSC day2的前夕和吉丽、松爷、猪猪侠和DZY也为此撕逼过。详见http://jiruyi910387714.is-programmer.com/posts/94162.html
公平分配中的争议还真是多。
app管理器的乱搞经历
2015-08-11 09:06:46 By matthew99
昨天下午改完app管理器之后发现dwjshift的程序特别快，然而是个乱搞，便造了个数据hack了。之后觉得他的思路很有趣，便新建了一个dwjshift_fan的账号优化他的算法，代码风格都是我自己的然而并没有多少人认出那是我（大雾。
最后137ms过了那道题，我的hack数据也跑得很快，自己试了试好像也没能hack。算法大概就是每次用dfs实现的SPFA暴力找环然后确定方向之后缩起来，注意重边的处理。加了很多优化之后才跑到137ms。欢迎有兴趣的同学前来hack：http://uoj.ac/submission/24834
...妈妈我终于会做动态仙人掌IV了
2015-05-16 23:10:45 By matthew99
妈妈我终于会做动态仙人掌IV了！！
由于mx此时刚好正在滚粗搞文化课，为了战这道题，可谓历尽辛酸(大雾)。迟到缺交作业忘搞卫生已经把我罚得在班上没脸做人了。
傻逼mx还因为手算算错答案怀疑标程正确性制造了两个恶意hack。看来要被封号了QAQ
不能作为除出题人之外第一个AC的人真是太遗憾了
，膜CHXER！
UPD:出了点奇怪的事情。
mx的仙人掌 题解
2015-03-27 11:59:14 By matthew99
题目地址
算法一
估计大家应该不会被仙人掌吓到而直接$\mathrm{gg}$了，至少先会考虑任意图的情况。
妈妈我不会处理图的问题怎么办？
有$5\%$的数据$n \le 7, \mathrm{tot} \le 7$，可以用各种方法(如枚举所有路径)水过去。
算法二
有$10\%$的数据$n, \mathrm{tot} \le 5000$。
最短路算法
由于时限和数据都很令人感动，这些数据其实用$\mathrm{dijkstra}$甚至$\mathrm{SPFA}$(我多良心没有卡哦！(大雾))都能跑得过去......
更好的做法
考虑仙人掌图的$\mathrm{dfs}$遍历树，有很多条前向边，每条前向边$x \rightarrow y$对应一个环，不妨设这个环的根为$y$，每当我们找到一条前向边$x \rightarrow y$时，通过从$x$不断回到$\mathrm{dfs}$树上的父亲直到到达$y$，我们可以取出这个环上所有点，并且容易得出环的长度，对所有点除了$y$以外的点都标记一下它所在的环编号。
$\mathrm{dfs}$完以后，对每个点考虑他到根的距离，如果他没有环标记那么距离就是父亲到根的距离加上自己到父亲的边的长度。否则就是他到环的根$y$的两条路径长度(一个是$\mathrm{dfs}$树上的距离(这个用两个点离根的距离减一减就求出来了)，另一个是环的长度减去树上距离)中的较小值加上$y$到根的距离。
对每个询问的每个询问点，我们都遍历一遍，时间复杂度为$O(n\times \mathrm{tot})$。
算法三
有$10\%$的数据$Q \le 10$。我们考虑对每一次询问直接$\mathrm{dfs}$一遍求得答案。
用$\mathrm{maxlen}_x$表示从$x$出发到以$x$为根的子仙人掌(即在原图中删去$x$之后不与根相连的点和$x$的导出子图)的某个询问点的最短路的最大值(如果没有询问点可以设为-∞)，对于$x$的某个$\mathrm{dfs}$树上的孩子$y$，如果从$x \rightarrow y$的边$e$是割边那么就直接用$\mathrm{maxlen}_y + w_e$更新$\mathrm{maxlen}_x$，$w_e$表示$e$的权值，否则如果$x$成为了边$e$所在环的根那么我们要把环取出来，直接枚举换上的点然后用他的$\mathrm{maxlen}$加上他到$x$的两条路径长度的最小值更新$\mathrm{maxlen}$即可。
考虑更新答案，所有询问点的$\mathrm{maxlen}$显然可以用来更新答案，对一个点的两个不同的子仙人掌（即在原图中删去$x$之后不与根相连的点的一个连通块和$x$的导出子图)，他们的$\mathrm{maxlen}$之和加显然也可以用来更新答案(求出一个子仙人掌$y$的$\mathrm{maxlen}_y$之后，先用$\mathrm{maxlen}_y + \mathrm{maxlen}_x$更新答案，再用$\mathrm{maxlen}_y$更新$\mathrm{maxlen}_x$即可)。现在还需要考虑经过一个环的路径的情况。
经过一个环的最短路径一定是由两条环以外的路径(可以长度为0)和一条环上的路径组成，我们按顺序取出环上的边，并且复制一份接在后面，形成一条链。对于链上的点$i$，记$mathrm{len}_i$为链的头部到它的路径的长度，$\mathrm{val}_i$为它对应的点的$\mathrm{maxlen}$，那么经过这个环的最长的最短路径即为$\mathrm{max}\{\mathrm{val}_i + \mathrm{val}_j + \mathrm{len}_i - \mathrm{len}_j\}(0 \le \mathrm{len}_i - \mathrm{len}_j \le \frac{\mathrm{cirlen}}{2})$，其中$cirlen$表示该环的长度，容易用单调队列维护，时间复杂度为$O(Qn)$，如果用线段树时间复杂度为$O(Qn\log n)$。
算法四
对于树的情况，可以使用虚树。
虚树的建立方法之一是，对询问点按$\mathrm{dfs}$序排序，然后取出他们相邻节点间的$\mathrm{lca}$，接着再按$\mathrm{dfs}$序排序，接着扫一遍，维护一个栈，如果当前栈顶的节点是当前节点的祖先那么就连一条边，边权为它们之间的距离，否则将栈顶的节点弹出栈。这只是一种建立方法。
然后在虚树上$\mathrm{DP}$即可。
时空复杂度均为$O(n\log n)$(今后视tot = $O(n)$)
此外时间复杂度可以通过更大的代码复杂度降为$O(n\alpha(n))$或者$O(n)$，具体不再赘述，我多良心没有要求大家写这些算法哦！(大雾)。
算法五
对于树的情况，还可以用树分治解决。
一种较方便的树分治的做法是，先建立好树分治结构，然后对每一个询问，先将点去重。接着对于每一个树分治结构中的节点(对应一棵子树$T$)，我们只考虑该询问中所有在$T$中的点。直接用两个属于不同子树的点到根的距离和的最大值更新答案即可(要注意判一下询问点是根的情况)。接着对于它的每一个孩子节点，递归处理下去，注意我们只要保留该询问中在这个孩子节点中的点。
但是这个做法由于要预先存储结构，时间空间常数都比较大。
还有一种做法是，询问和树一起分治，这个很好理解，无非就是把两个过程合并了，每一次要处理的是一棵子树和一个询问序列，这个序列只保留所有存在询问点在该子树中的询问，并且每个询问只保留在该子树中的询问点，然后处理询问的方法如同前面所述。
时空复杂度均为$O(n\log n)$。
UPD:树上迭代两次求最远点即可，最远点可以直接枚举然后$\mathrm{lca}$，呜呜呜我出题的时候怎么就脑抽了，30分送大家吧，前面的算法就当做口胡......
算法六
对于树的情况，如果你只会虚树或者树分治，对于仙人掌你肯定也只能这么做了。
如果我们能建立“虚仙人掌”，肯定可以解决这个问题。
我们想一想就能想清楚虚仙人掌的一种最笨但是也绝对正确并且可以通过这题的建立方法，先按$\mathrm{dfs}$序排序，再求出相邻节点间的$\mathrm{lca}$(注意这里$\mathrm{dfs}$序和$\mathrm{lca}$都是在它的$\mathrm{dfs}$遍历树上做，后面的深度也是)，接着我们取出每一个点所在环的根和环上最深的点，再排序并取一遍相邻节点$\mathrm{lca}$，然后建出$\mathrm{dfs}$树上的虚树，接着再每个环的最浅的点和最深的点之间连边，边权为它们原先连的边的权值(它们原先显然一定连了边)，由于我们要求的是最短路径，其实这里连它们之间在环上走的两条路径的较小值也没有关系，不会对任何最短路径造成影响，这一个画一画图就知道了。
根据上述结论，连虚树上的边时，可以将虚仙人掌上的环边和树边一视同仁，统统连它们两个端点在原仙人掌上的最短路径长度。但是这个最短路径长度和树上不同，树上可以直接用离根的距离减一减，仙人掌上就不是这么简单了，离根的最短路长度不具有可减性。是，我们可以用动态仙人掌。但是这样代码复杂度太高。我们考虑一下，如果树上有一个值也不具有可减性，比如路径边权最小值，你会怎么弄？一种方法就是倍增。对仙人掌也这么弄，考虑动态仙人掌维护生成树法的思想，我们记录每个点到它第$2 ^ i$级祖先的最短路长度，同时如果有一个环不完全包含这条路径，且包含第$2 ^ i$级祖先的父亲(显然这个祖先如果是根就不可能存在满足条件的环)，那么我们就记录一下这条路径上深度最大的在这个环上的点，合并的时候就根据这个环是走树边还是走非树边来求出最短路，非常简单。
UPD:好像可以记录到根的距离，然后用特殊的方法处理一下就可以直接减了。总之实现上有各种技巧优化时间复杂度和代码复杂度，感觉标程就是个逗比啊TAT......
实际上，std的方法和上述方法有细节上的差异，如果$x$本身连了一条非树边，包含了整个路径及$2 ^ i$级祖先的父亲，那么他也将被记录，但是这样合并的时候将会多出一些小麻烦，因为一个环可能会更新一条路径两次，用后一次更新覆盖掉前一次更新即可。但是如果不用这个方法，$\mathrm{dfs}$树的叶子节点连接的非树边也要特判。不过这些东西都是一些细节问题，稍微处理一下即可。
总之这个算法可以非常愉悦的跑出100分， 时空复杂度均为$O(n\log n)。$
提交记录在这里。
算法七
对于树分治，我们显然也可以想办法把它搞到仙人掌上，也就是用仙人掌分治来解决问题，实现细节和树分治大同小异，每一次去掉一个点时，先把它弄成仙人掌的根，然后断开它连的所有割边，以及所有它所在环的环边，每一次选一个进行上述操作后，剩下来的子仙人掌中大小最大的最小的点来分治即可(其实为了方便我写的程序不一定能取出最小，但绝对剩下来的子仙人掌中大小最大的不超过$\frac{n}{2}$)。
处理每个询问时，根可能连着不少的环。对一个点（除了根），如果在某一个环$C$上或者某一个在$C$上的点(除了根)的子仙人掌，那么称这个点属于环$C$。，直接用两个属于不同子仙人掌或者环的点到根的距离和的最大值更新答案即可(同样要注意判一下询问点是根的情况)。但是我们还要注意属于同一个环但不是环上同一个点的子仙人掌的点，他们两两之间也要更新答案，这个用单调队列很好解决。
时空复杂度均为$O(n\log n)$。
解法八
松爷给出了另外一种解法，详见http://wangyisong1996.is-programmer.com/user_files/wangyisong1996/File/zjoi2015/cactus-slides/wys-cactus-slides.html#/6
AC代码：
http://uoj.ac/submission/13387
http://uoj.ac/submission/13388
第一份的空间复杂度是$O(n\log n)$，比第二份多一个$O(\log n)$，但代码量更小。
此外，仙人掌分治和虚仙人掌都可以在线，前者在线情况应该会TLE甚至可能MLE(至少我的写法如此= =b)，后者本身就可以在线。这种做法就没什么简单办法做到在线了= =b。
解法九
waltz给出了另外一种解法：http://uoj.ac/submission/13649
时间空间代码量都完虐我啊orz......
这个做法是对每个环，新建一个点，向环上每个点连长度为它到环的根的最短路径长度的边，如果对新树dfs，那么每个点到它的任意非新建祖先的最短路径长度就是它们之间在树上的距离，对于lca不是新建点的两个点最短路长度就是它们之间在树上的距离，是新建点的话，在树上的距离也不会小于真实距离，但我们可以单独取出环再单调队列来解决环的问题。这道题成功降级为符合人民大众胃口的既无思考难度也无代码难度的傻逼题。跪烂waltz！
基于这个思路，也许很多仙人掌上问题可能会有更简单的做法？
乱搞
我们发现对于树的情况，直径就是任取一个点$a$，求出他的最远点$x$，再求出最远点$y$，$x$到$y$的距离，应用到仙人掌上是不正确的。因为一个大环连上一条小边，只有$a$取到$O(1)$个点时才能求出答案，对于其他点就算不断找最远点迭代∞次答案也不正确。(想知道这个算法能拿多少分吗？写写就知道！
)
另外我们还可以多次枚举点做根，然后设法求得经过根的最长路径，由于答案路径可能很长，一旦取到了一个答案路径上的点做根就可以求出正确答案。但是一旦答案路径比较短，这个算法就不靠谱了。并且这个算法没法较好的判断是否已经是当前答案已经正确。
如果你通过各种方法乱搞过了，你就可以好好感受一下$\mathrm{extra\ test}$和$\mathrm{hack}$的威力了。
后记
其实这个题如果出成每对点的最短距离和的话，是可以避免乱搞的，而且不难实现，但是由于奇怪的原因，我没有把它改成这样。
在出题人想出一个原始的算法之后，算法又其他人不断被改进，长江后浪推前浪。感觉我从这道题的出题经历中感受到了科技的进步。
5s的时限真是太良心了233，主要是为了欢迎各种奇葩做法。
mx的组合数 题解
2015-03-27 11:58:56 By matthew99
题目地址
QAQ我把这题出出来之后，发现以前有一道几乎一样的题，而且我还A过！感觉自己记性真的有点好......
算法一
对于$10\%$的数据，$n, l, r \le 1000$。因此我们直接暴力枚举$x$，然后暴力求组合数即可。
如果你不会模意义下的除法，可以用杨辉三角打出前$1001$行，然后直接查询。
如果你既不会除法也不会杨辉三角(居然能看懂题目？)，存在$5\%$的数据$n, l, r \le 10$，答案可以用各种方法直接算出来= =b。
算法二
对于$20\%$的数据，$n, l, r \le 100000$，我们可以用公式 ${n + 1 \choose m} = \frac{n + 1}{n - m + 1}{n \choose m}$递推出所有组合数。
算法三
对于另外$20\%$的数据，$r - l \le 10000$，我们暴力枚举$x$之后，组合数计算可以根据Lucas定理计算，但是直接枚举计算是会超时的。
首先我不知道有多少人听到这个定理后想到的是这个公式
${a \choose b} \bmod p = {\lfloor\frac{a}{p}\rfloor \choose \lfloor\frac{b}{p}\rfloor}{a \bmod p \choose b \bmod p} \bmod p$
而不是
${a \choose b} \bmod p = \prod\limits_{i \ge 0}{a_i \choose b_i} \bmod p$，其中$a_i$表示$a$在$p$进制下从较低位数起的第$i$位。
前者和后者的等价关系很显然。
用第二个公式，我们对每一位都预处理出所有组合数，复杂度为$p \times 位数$，然后枚举$x$之后可以用$O(位数)$的时间直接查询每一位的组合数值然后算出来，如果每次重新计算$x$的$p$进制，复杂度为每次$O(位数 ^ 2)$，如果每次加$1$并进位，还可以做到$O(位数)$，两种复杂度都可以轻松通过这一部分数据。
算法四
首先问题容易转化为小于等于$r$的$x$个数减去小于等于$l - 1$的$x$个数，我们只要考虑形如$x \le bound$的限制即可。
算法三给了我们启发，我们应该从$p$进制下考虑。
很容易设计出数位DP的状态和转移方程：
$g[i, j]$表示从低位开始前$i$位任意且值为$j$的方案数。 $f[i, j]$表示从低位开始前$i$位对应的$p$进制数不超过$bound$的前$i$位对应的$p$进制数且值为$j$的方案数。
假设$n$的第$i + 1$位为$y$，$bound$的第$i + 1$位为$w$，枚举第$i + 1$位的值$x$，若${x \choose y} = z$则
$g[i + 1, jz \bmod p]$ += $g[i, j]$
若$x \lt w$则$f[i + 1, jz \bmod p]$ += $g[i, j]$
若$x = w$则$f[i + 1, jz \bmod p]$ += $f[i, j]$
时间复杂度为$O(位数 \times p ^ 2)$，结合算法三可以获得$70$分，事实上前$40$分的答案比较稀疏，通过常数优化或许可以直接通过。
算法五
由于$p$是质数那么一定存在原根$g$，在算法四的转移方程中，若$j$，$z$均不为$0$，那么一定存在原根$g$下的关于模$p$的离散对数，通过取离散对数再根据费马小定理，很容易将转移方程中的$jz \bmod p$转化为$g ^ {(ind(j) + ind(z)) \bmod (p - 1)} \bmod p(ind(x)$表示$x$在原根$g$下关于模$p$的离散对数)，从而转移方程可化为卷积的形式，FFT即可。
对于$j = 0$或者$z = 0$的情况，我们可以在转移中忽略，先将$1 \rightarrow p - 1$的答案统计出来，然后用总数减掉即可。
由于模数的特殊性，可以用数论变换解决。
于是这题被完美解决啦。
提交记录在这里。
p = 2挂掉啦！
注意枚举原根要从$1$开始而不是从$2$开始
此外数组要开到$100$左右，而不是$30$或者更少。
太麻烦了
请问你们这些说麻烦的人，都为什么会觉得麻烦？
求原根太麻烦
这题的$p$很小，加上原根很多，直接暴力从$1$到$p$枚举然后直接枚举$1$到$p - 2$次方看有没有提前出现$1$即可，连$p - 1$的约数都不用枚举！
我不想写离散对数的大步小步算法
还是那句话，这题的$p$很小，直接预处理出所有的数的离散对数值即可。
此外逆元也可以预处理，并且还可以使用$O(p \log p)$的算法，不一定要写线性算法。
我不想写高精度
你可以用自带高精度的语言比如$\mathrm{python,java}$等，当然要注意常数问题。
如果你只会$\mathrm{C}$++，UOJ支持$\mathrm{C}$++的__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$)，可以避免高精度。
使用方法可以参考这个提交记录：__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$)
共 23 篇博客
- Universal Online Judge |
鄂公网安备 42010202000505 号
Server time: 2024-04-25 23:11:59