前言
题单整理好了，算是留下遗产，给自己将来用了（
反正今天就是一堆学过但是忘了的算法与数据结构复健。
正文
最小斯坦纳树
简介
就是一个在 n 个点的图里面保证让其中给定的 k 个点联通的神秘算法。
具体做法也很简单，定义 f_{u, S} 表示以 u 为根，目前 k 个点的覆盖情况是 S 的最小代价。
转移有：
$f{u,S} = \min{T \subset S}f{u, T}+f{u,S – T}（这个是显然的，就是以u$ 为根把两个集合并起来）
还有：
$f{u,S} = \min f{v,S} + w_{v,u}$（这个其实就是最短路的 “松弛” 操作，大部分 dijkstra / spfa 二选一，少部分用 floyd 提前处理）
然后就没了。
题目
[P4294]
有意思，但主要难点集中在对方案的查询，还有对板子一个递推式的修改。
由于这道题从边权变成了点权，所以合并的时候上述的第一个式子大概长成这样：
$f{u,S} = \min{T \subset S}f{u, T}+f{u,S – T} – w_u， 其中w_u表示u点点权，很好理解，就是合并时候不要合出两个u$ 点点权。
至于方案记录，考虑无数记录最短路方案里的做法，即记录前驱节点 pre，用 pre 不断递归往前。但这里注意有可能从一个点分出两条路，类似二叉树结构，详情见代码。
#include
using namespace std;
typedef pair PII;
const int N = 101, K = 11, INF = 0x3f3f3f3f;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};
int n, m, p, k, root;
int w[N], f[N][1 << K], st[N], res[N];
PII pre[N][1 << K];
priority_queue<PII, vector, greater >q;
inline int get(int x, int y){return x * m + y;}
void dijkstra(int S)
{
memset(st, 0, sizeof st);
while (q.size())
{
PII u = q.top();
q.pop();
int ver = u.second;
if (st[ver])continue;
st[ver] = 1;
int x = ver / m, y = ver % m;
for (int i = 0; i < 4; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx = n || ny = m)continue;
int j = get(nx, ny);
if (f[j][S] > f[ver][S] + w[j])
{
f[j][S] = f[ver][S] + w[j];
pre[j][S] = {ver, S};
q.push({f[j][S], j});
}
}
}
}
void dfs(int u, int S)
{
if (!pre[u][S].second)return;
res[u] = 1;
dfs(pre[u][S].first, pre[u][S].second);
if(pre[u][S].first == u)dfs(pre[u][S].first, S ^ pre[u][S].second);
}
int main()
{
scanf("%d%d", &n, &m);
p = n * m;
for (int i = 0; i < p; i ++)
{
for (int j = 0; j < (1 << K); j ++)f[i][j] = INF;
}
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
int id = get(i, j);
scanf("%d", &w[id]);
if (!w[id])f[root = id][(1 << (k ++))] = 0;
}
}
for (int S = 1; S < (1 << k); S ++)
{
for (int i = 0; i f[i][T] + f[i][S ^ T] - w[i])
{
f[i][S] = f[i][T] + f[i][S ^ T] - w[i];
pre[i][S] = {i, T};
}
}
if(f[i][S] != INF)q.push({f[i][S], i});
}
dijkstra(S);
}
printf("%d\n", f[root][(1 << k) - 1] == INF ? 0 : f[root][(1 << k) - 1]);
dfs(root, (1 << k) - 1);
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
int id = get(i, j);
if (!w[id])putchar('x');
else if(res[id])putchar('o');
else putchar('_');
}
puts("");
}
return 0;
}
[ABC395G]
当你有了一个模板的时候，你大多数时候并不会对模板做根本性的改进，对于很多算法都是这个道理。
可惜，这题需要改进。
我们考虑我们最初设了个什么东西。
以 u 为根的覆盖情况。
也就是在如果这个题只有新加一个点，原来的做法是天然可行的。
如何处理两个点呢？
再加一个维度。
其实就相当于把板子复制一遍并在外面套上一层循环。(bushi
注意把控数组大小。
#include
using namespace std;
typedef long long LL;
const int N = 85, K = 10;
const LL INF = 1e14;
int n, k;
LL f[N][N][1 << K];
LL G[N][N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
scanf("%lld", &G[i][j]);
for (int S = 0; S < (1 << (k + 1)); S ++)f[i][j][S] = INF;
}
}
for (int k = 1; k <= n; k ++)
{
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
}
for (int i = 1; i <= n; i ++)
{
for (int j = 0; j < k; j ++)f[i][j + 1][1 << j] = 0;
f[i][i][1 << k] = 0;
}
for (int S = 1; S < (1 << (k + 1)); S ++)
{
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
for (int T = S & (S - 1); T; T = S & (T - 1))f[i][j][S] = min(f[i][j][S], f[i][j][T] + f[i][j][S ^ T]);
}
for (int j = 1; j <= n; j ++)
{
for (int k = 1; k <= n; k ++)f[i][j][S] = min(f[i][j][S], f[i][k][S] + G[k][j]);
}
}
}
int q;
scanf("%d", &q);
while(q --)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%lld\n", f[x][y][(1 << (k + 1)) - 1]);
}
return 0;
}
树链剖分
简介
具体地，其实本质上只是一种处理树形结构的方法，即把一棵树断成若干条链，变成线性结构，这样才好使用数据结构处理。
做法不想写了，这玩意比最小斯坦纳树常见多了。(bushi
题目
[LOJ6669]
What an amazing interactive problem!
首先看到题的第一眼没有任何证据指向剖分。
好吧其实关系和剖分不是很大，只是借鉴了重儿子这一特性。
首先把每一个点都和 1 进行询问，得到每一个点的深度 d_u
得到之后枚举层数 dep 和当前层的点 u。
①在以下操作开始前，先 DFS 一遍本树已有的部分，得到每个点沿重儿子往下走的最深点。
② 令 v 最开始为 1，设 v 沿重儿子往下走的最深点 w，询问 (u, w)，得到的结果称为 dist
显然地，LCA 有一个特性：$d_u + dw – 2 \times d{lca(u, w)} = dist$，
根据本式得到 d_{lca(u, w)} 。
显然地，lca(u,w) 一定在 v \rightarrow w 的这一条重链上，
让 v 移动到 lca(u, w) 后，由于本树是二叉树，选择另一条链（即轻链）往下走一步，重复 ②，直到 d_u – d_v = 1。
然后做完了，跑了 10s。
#include
using namespace std;
const int N = 3005;
int n, d[N], son[N][2], Size[N], lds[N], par[N];
vector P[N];
void add(int u, int v)
{
par[v] = u;
if(son[u][0])son[u][1] = v;
else son[u][0] = v;
}
void dfs(int u)
{
Size[u] = 1;
lds[u] = u;
if (son[u][0])
{
dfs(son[u][0]);
Size[u] += Size[son[u][0]];
}
if(son[u][1])
{
dfs(son[u][1]);
Size[u] += Size[son[u][1]];
if(Size[son[u][1]] > Size[son[u][0]])swap(son[u][0], son[u][1]);
}
if (son[u][0])lds[u] = lds[son[u][0]];
}
int ASK(int a, int b)
{
int x;
printf("? %d %d\n", a, b);
fflush(stdout);
scanf("%d", &x);
return x;
}
void work(int u)
{
int v = 1;
while (d[u] - d[v] > 1)
{
int dist = ASK(u, lds[v]);
// d[u] + d[lds[v]] - 2 * d[lca(u, lds[v])] = dist
// => d[lca(u, lds[v])] = (d[u] + d[lds[v]] - dist) / 2
int gd = (d[u] + d[lds[v]] - dist) / 2;
while (d[u] - d[v] > 1 && d[v] < gd)v = son[v][0];
if (d[u] - d[v] == 1)break;
v = son[v][1];
}
add(v, u);
}
int main()
{
scanf("%d", &n);
for (int i = 2; i <= n; i ++)P[d[i] = ASK(1, i)].push_back(i);
for (int dep = 1; dep <= n; dep ++)
{
dfs(1);
for (int u : P[dep])work(u);
}
printf("! ");
for (int i = 2; i <= n; i ++)printf("%d ", par[i]);
puts("");
fflush(stdout);
return 0;
}
原本应该还有CDQ/整体二分和带花树的题目，但是没法，就不写了。
复健了一些，自我感觉好多了，狠狠弥补了昨天只获得了 3pts 的现实（逃