A – 调整 Tweak
这道题我在考场上打了一个错解，还骗到了 30 分。
正常的思路是：在最短路图上找到几个边进行修改。然而，最优的解决方案并不一定出现在最短路图上的边上，也可以通过修改次优边进行解决。所以，这道题其实跟最短路没什么太大关系，即使后面会用到 Djisktra 来求最短路。
我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份，然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\)，可以生成一个副本来连接下一层的目标点，也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\)，当最后求最短路时，经过这样的一条边可以被认为是修改一条边，且，这个边是单向向下的，所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路，然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。
// A.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>
using namespace std;
const int MAX_N = 1100;
int n, m, c, dist[MAX_N * MAX_N], current, head[MAX_N * MAX_N];
bool vis[MAX_N * MAX_N];
struct edge
{
int to, nxt, weight;
} edges[1010 + MAX_N * MAX_N];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void djisktra()
{
memset(dist, 0x3f, sizeof(dist));
priority_queue<pr> q;
q.push(make_pair(0, 1));
dist[1] = 0;
while (!q.empty())
{
int u = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (dist[edges[i].to] > dist[u] + edges[i].weight)
dist[edges[i].to] = dist[u] + edges[i].weight, q.push(make_pair(-dist[edges[i].to], edges[i].to));
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d%d", &n, &m, &c);
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
for (int layer = 0; layer < n; layer++)
addpath(layer * n + u, layer * n + v, w);
for (int layer = 0; layer < n - 1; layer++)
addpath(layer * n + u, (layer + 1) * n + v, 0);
}
djisktra();
for (int layer = 0; layer < n; layer++)
if (dist[layer * n + n] <= c)
{
printf("%d", layer);
return 0;
}
return 0;
}
B – 树 A
sb 题，树链剖分板子题，不讲。
// B.cpp
#include <bits/stdc++.h>
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
const int MAX_N = 31000;
int head[MAX_N], current, pt_weight[MAX_N], dfn[MAX_N], antidfn[MAX_N], m;
int top[MAX_N], son[MAX_N], siz[MAX_N], dep[MAX_N], fa[MAX_N], dfntot, n, opt;
int tree[MAX_N << 2];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void build(int l, int r, int p)
{
if (l == r)
return (void)(tree[p] = pt_weight[antidfn[l]]);
build(l, mid, lson), build(mid + 1, r, rson);
tree[p] = tree[lson] + tree[rson];
}
void update(int qx, int l, int r, int p, int val)
{
if (l == r && qx == l)
return (void)(tree[p] = val);
if (qx <= mid)
update(qx, l, mid, lson, val);
else
update(qx, mid + 1, r, rson, val);
tree[p] = tree[lson] + tree[rson];
}
int query(int ql, int qr, int l, int r, int p)
{
if (ql <= l && r <= qr)
return tree[p];
int ans = 0;
if (ql <= mid)
ans += query(ql, qr, l, mid, lson);
if (mid < qr)
ans += query(ql, qr, mid + 1, r, rson);
return ans;
}
int query(int x, int y)
{
if (dep[top[x]] > dep[top[y]])
swap(x, y);
int ans = 0;
while (top[x] != top[y])
{
ans += query(dfn[top[y]], dfn[y], 1, n, 1);
y = fa[top[y]];
if (dep[top[x]] > dep[top[y]])
swap(x, y);
}
if (dep[x] > dep[y])
swap(x, y);
ans += query(dfn[x], dfn[y], 1, n, 1);
return ans;
}
void dfs1(int u)
{
siz[u] = 1, dep[u] = dep[fa[u]] + 1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[u])
{
fa[edges[i].to] = u, dfs1(edges[i].to);
siz[u] += siz[edges[i].to];
if (siz[edges[i].to] > siz[son[u]])
son[u] = edges[i].to;
}
}
void dfs2(int u, int org)
{
dfn[u] = ++dfntot, antidfn[dfntot] = u, top[u] = org;
if (son[u] == 0)
return;
dfs2(son[u], org);
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[u] && edges[i].to != son[u])
dfs2(edges[i].to, edges[i].to);
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= n - 1; i++)
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; i++)
scanf("%d", &pt_weight[i]);
build(1, n, 1);
while (m--)
{
int A, B;
scanf("%d%d%d", &opt, &A, &B);
if (opt == 1)
update(dfn[A], 1, n, 1, B);
else
printf("%d\n", query(A, B));
}
return 0;
}
C – 树 B
也是一道 SB 题，要不是我边的数组开小了，我考场上就能多 A 一题，那至于只有 50 分。
这道题很显然是一道树形 DP，考虑对要隔离的点进行标记，然后树形 DP 方程如下：
\[ \begin{cases} dp[u][0] = \sum_{v \in son(u)} min\{ dp[v][0], dp[v][1] \}[tag[v] = false] + dp[v][1][tag[v] = true] \\ dp[u][1] = e(e, fa[u]).weight \end{cases} \]
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, head[MAX_N], current, fa[MAX_N], upward[MAX_N];
int dp[MAX_N][2];
bool tag[MAX_N];
struct edge
{
int to, nxt, weight;
} edges[MAX_N << 1];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].weight = weight;
edges[current].nxt = head[src], head[src] = current++;
}
void preprocess(int u)
{
dp[u][1] = edges[upward[u]].weight;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[u])
{
fa[edges[i].to] = u, upward[edges[i].to] = i;
preprocess(edges[i].to);
if (tag[edges[i].to])
dp[u][0] += dp[edges[i].to][1];
else
dp[u][0] += min(dp[edges[i].to][0], dp[edges[i].to][1]);
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1, u, v, c; i <= n - 1; i++)
scanf("%d%d%d", &u, &v, &c), addpath(u, v, c), addpath(v, u, c);
for (int i = 1, tmp; i <= m; i++)
scanf("%d", &tmp), tag[tmp] = true;
preprocess(1);
printf("%d", dp[1][0]);
return 0;
}
D – 跨时代
这道题真的毒瘤。
最开始的做法：考虑状态压缩，所有的木棍拼接成的长度的情况都存在桶中，然后枚举两边长度，枚举当前长度下的木棍状态，然后 AND 判断，也就是这样：
// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 20;
int n, li[MAX_N], mxlen, S = -0x3f3f3f3f, sizes[20 * 15];
int bucket[20 * 15][20 * 150];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &li[i]), mxlen += li[i];
for (int i = 0; i < (1 << n); i++)
{
int len = 0;
for (int j = 1; j <= n; j++)
if (i & (1 << (j - 1)))
len += li[j];
bucket[len][sizes[len]++] = i;
}
for (int lenA = mxlen; lenA >= 1; lenA--)
{
int sizA = sizes[lenA];
if (sizA == 0)
continue;
if (lenA * mxlen <= S)
break;
for (int lenB = mxlen; lenB >= 1; lenB--)
{
int sizB = sizes[lenB];
if (sizB == 0)
continue;
if (lenA * lenB <= S)
break;
for (int x = 0; x < sizA; x++)
{
int statX = bucket[lenA][x];
for (int y = 0; y < sizA; y++)
{
int statY = bucket[lenA][y];
if ((statX & statY) != 0)
continue;
for (int z = 0; z < sizB; z++)
{
int statZ = bucket[lenB][z];
if((statX & statZ) != 0 || (statY & statZ) != 0)
continue;
for (int w = 0; w < sizB; w++)
{
int statW = bucket[lenB][w];
if ((statW & statX) != 0 || (statW & statY) != 0 || (statW & statZ) != 0)
continue;
S = max(S, lenA * lenB);
}
}
}
}
}
}
if (S < 0)
printf("No Solution");
else
printf("%d", S);
return 0;
}
然后，嗯，TLE 了。
最后我看别人的做法是这样的：考虑状态压缩一套边，也就是一对长或者是一对宽，状压的时候进行背包 DP 判断这一套边是否能被拆成两部分，如果能的话打一个标记。然后，进行搜索：DFS 的时候，时间复杂度是\(O(3^n)\)的，因为每一条边都有选或者是不选的状态，然后考虑分配长和宽就行了。
// D.cpp
#include <bits/stdc++.h>
const int MAX_N = 17;
using namespace std;
int n, ai[MAX_N], dp[MAX_N * 20], ans = -1;
bool flag[(1 << MAX_N)];
void dfs(int dep, int statA, int lenA, int statB, int lenB)
{
if (dep == n)
{
if (flag[statA] && flag[statB])
ans = max(ans, (lenA * lenB) / 4);
return;
}
dfs(dep + 1, statA, lenA, statB, lenB);
dfs(dep + 1, statA | (1 << dep), lenA + ai[dep + 1], statB, lenB);
dfs(dep + 1, statA, lenA, statB | (1 << dep), lenB + ai[dep + 1]);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]);
for (int stat = 1; stat < (1 << n); stat++)
{
int sum = 0;
for (int i = 1; i <= n; i++)
if ((stat >> (i - 1)) & 1)
sum += ai[i];
if (sum & 1)
continue;
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= n; i++)
if ((stat >> (i - 1)) & 1)
for (int k = sum; k >= ai[i]; k--)
dp[k] |= dp[k - ai[i]];
if (dp[sum >> 1])
flag[stat] = true;
}
dfs(0, 0, 0, 0, 0);
if (ans > 0)
printf("%d", ans);
else
puts("No Solution");
return 0;
}