20联赛集训day3 题解
因为某些原因晚了半小时打，然后就疯狂挂题，从前二（或许？）挂到了倒一A可以考虑哈希。这里可以给每个值随机一个哈希值，合并操作定义为异或。考试的时候写的N模好像 T 飞了。。事实上这个数据一模数就能过#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define s...
因为某些原因晚了半小时打，然后就疯狂挂题，从前二（或许？）挂到了倒一A可以考虑哈希。这里可以给每个值随机一个哈希值，合并操作定义为异或。考试的时候写的N模好像 T 飞了。。事实上这个数据一模数就能过#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define s...
赛时T1 是个带环的博弈，我比较菜不会做 写了无环和有自环的点就跑了。 T2 这种题一看就很 $O(n^2)$ 可是我只会暴力 就跑了 $n$ 遍最短路，拿到了一点点暴力分 T3 一开始不会，发现 Sub1 可做 Sub2 可做 Sub5 可做。。。写了一场然后发现 Sub5 套个cdq 就过了，可惜这是在比赛结束前一分钟发现的 [流泪]最后 T1 不知道为什么爆零了 0+25+50=75...
题目链接题解首先我们尝试把不能被车经过的边删掉，得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序，用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就可以了。 但是这题目要求强制在线怎么办？我们可以使用可持久化并查集来维护这个东西。 可持久化并查集用可持久化线段树来实现，非常简单。代...
这道题甚至不如 T2 难...放在 T3 真的合适吗...题目链接题目描述一张无向带权图，需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中，有 $ p_i $ 的概率选择点 $ d_i $，有 $ 1-p_i $ 的概率选择点 $ c_i $ ，每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现在求出所有选择的路线方案中的最小期望值。
题意描述给定一张无向图，定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路，求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。题目链接推荐大家去 uoj 多交一些题目，上面有很多 hack 数据。（像我之前认为 dij 就是 spfa+priority_queue）。