我不行了
我爆炸了
The contest is so nat!!!
[TG – A]
[A]
我发现我不会最短路。
暴力是简单的(?)，考虑枚举每一条边作为反转，朴素 dijkstra 处理最短路，时间复杂度是 O(n ^ 2 + m n ^ 2) 的，但是容易写挂。
然后考虑正解。
我们发现 dijikstra 实在是被调用太多次了，考虑什么时候才真正需要调用。
如果一条边 (u, v) 反转了，但是这条边不在最短路上，显然这时候可以直接利用前面的结果。
因此在前面做 4 次最短路，分别代表从 1 \rightarrow i， 从 i \rightarrow n， 从 n \rightarrow i，从 i \rightarrow 1 分别的结果。
我们称上述四次最短路所经过的边为关键边。
对于关键边，我们反转当前边，用 dijkstra 直接暴力重新计算结果。
对于非关键边，我们直接利用现有结果，具体见代码。
由于关键便的条数不会超过 4n， 即最差情况下 dijkstra 所用复杂度大概是 O(n ^ 3) 级别，可以通过。
#include
using namespace std;
const int N = 205, M = 1e5 + 5;
typedef long long LL;
const LL INF = 1e10;
int n, m, st[N];
LL dist[5][N];
LL G[N][N], Gp[N][N];
int EOT[N][N], pre[N], visited[N][N];
struct node
{
int a, b;
LL c, d;
}E[M];
void dijkstra(int S, LL *dist, int op, int keep)
{
for (int i = 1; i <= n; i ++)
{
dist[i] = INF;
st[i] = 0;
}
dist[S] = 0;
for (int i = 0; i < n; i ++)
{
int t = -1;
for (int j = 1; j dist[j])) t = j;
}
st[t] = 1;
for (int j = 1; j dist[t] + ((op) ? G[j][t] : G[t][j]))
{
dist[j] = dist[t] + ((op) ? G[j][t] : G[t][j]);
if (keep)pre[j] = t;
}
}
}
if (keep)
{
for (int i = 1; i <= n; i ++)EOT[pre[i]][i] = 1;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
if (i != j) G[i][j] = Gp[i][j] = INF;
else G[i][i] = Gp[i][i] = 0;
}
}
for (int i = 1; i c)
{
Gp[a][b] = G[a][b];
G[a][b] = c;
}
else if(Gp[a][b] > c)Gp[a][b] = c;
E[i] = {a, b, c, d};
}
// for (int i = 1; i <= n; i ++)
// {
// for (int j = 1; j i)
dijkstra(n, dist[1], 1, 1);// 1 == (i -> n)
dijkstra(n, dist[2], 0, 1);// 2 == (n -> i)
dijkstra(1, dist[3], 1, 1);// 3 == (i -> 1)
LL res = INF;
res = min(res, dist[0][n] + dist[2][1]);
for (int i = 1; i n
ans += dist[4][n];
dijkstra(n, dist[4], 0, 0);// 4 temporary n->1
ans += dist[4][1];
res = min(res, ans);
//recover (a,b)
G[a][b] = tab;
G[b][a] = tba;
visited[a][b] = 1;
}
else res = min(res, d + min(dist[0][n], dist[0][b] + c + dist[1][a]) + min(dist[2][1], dist[2][b] + c + dist[3][a]));
}
printf("%lld", (res == INF) ? -1 : res);
return 0;
}
[T2]
奇奇怪怪的神秘 DP。。。
然后……不会……
为什么会有人想到双指针啊[精神崩坏]
[T3]
不行了不行了我已经调最短路调两个小时了我不要线段树合并……
救救我救救我救救我。
直到看到 TJ 有一个极为绝妙的做法。
太感动了。
考虑 DP，定义f_{u,t} 表示在 u 这个节点， t 这个时间点前收割最大收获，有一个我也能写出来的式子(?)
$$f_{u,t} = \max(\sum f_{v, i}, w_i + \sum f_{v, d_u}) $$
其中 v 是 u 的儿子， i \geq d_u。
转移的时候，用 map 维护，考虑用第二个式子去减去第一个式子（换言之，把 map 的部分值前移到 d_u）
我们感性理解一下这个东西的正确性：
如果二式大于/等于一式， 那么本身就应该这样操作。
如果二式小于一式，那么到最后一定在末尾有留存，结合定义，这是不影响结果的。
代码可能是线段树合并的 \frac{1}{5} 不到。
#include
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
map f[N];
int n, m, k;
int par[N], d[N], w[N], root[N];
void merge(int &x, int y)
{
if (f[x].size() < f[y].size())swap(x, y);
for (auto it : f[y])f[x][it.first] += it.second;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 2; i <= n; i ++)scanf("%d", &par[i]);
while (m --)
{
int x;
scanf("%d", &x);
scanf("%d%d", &d[x], &w[x]);
}
for (int i = 1; i second) > w[u])
{
(it -> second) -= w[u];
break;
}
w[u] -= (it -> second);
auto tp = it ++;
f[root[u]].erase(tp);
}
merge(root[par[u]], root[u]);
}
LL res = 0;
for (auto it : f[root[1]])res += it.second;
printf("%lld", res);
return 0;
}
简直就是神！
[T4]
救命啊出题人不要在题目里面杂糅害我搜出来的结果全都是某款六字游戏的结果
有一张点带标号的简单无向连通图（简单无向图指无重边、自环的无向图），已知节点数量 n 和割边数量 k ，求出这张图有多少种不同的可能，对 P 取模。
两张图不同，当且仅当至少存在一对节点 i,j ，恰好在一张图中节点 i,j 间有边。
输出 n 行，每行一个整数。设 F(n,k) 表示 n 个节点 k 条割边时的答案（对 P 取模后的结果），第 i 行你需要输出：
(F(i,0) \oplus B) \oplus (2(F(i,1) \oplus B)) \oplus (3(F(i,2) \oplus B))⋯ \oplus (i(F(i,i−1) \oplus B))
注意这里运算时没有取模。
好像是神秘多项式，占一个坑，说不定之后补了呢