今天被各路神仙吊打，顺利 gg。
在考场上我推了个有后效性的 DP，还以为是高斯消元，然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。
首先，对一个概率为\(p\)的事件，它的期望次数是\(\frac{1}{p}\)（参见这里）。然后，考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。
考虑\(dp[1]\)的求法，首先需要两个级别为\(0\)的武器，然后发现无论失败与否都可以保证至少又一个\(0\)级武器，所以我们只需要注意另外一个武器的花费就可以了：
\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]
这道题在 JZOJ 上面开 10s，遂 AC。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 60100;
struct point
{
int x, y, prop, id;
bool operator<(const point &pt) const { return prop < pt.prop; }
} nodes[MAX_N], *cur[MAX_N];
int n, m;
char opt[10];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &nodes[i].x, &nodes[i].y, &nodes[i].prop), nodes[i].id = i;
sort(nodes + 1, nodes + 1 + n);
for (int i = 1; i <= n; i++)
cur[nodes[i].id] = &nodes[i];
while (m--)
{
scanf("%s", opt + 1);
int x, y, x_, y_, k;
if (opt[1] == 'Q')
{
scanf("%d%d%d%d%d", &x, &y, &x_, &y_, &k);
bool flag = false;
for (int i = 1; i <= n; i++)
if (nodes[i].x <= max(x, x_) && nodes[i].x >= min(x, x_) && nodes[i].y <= max(y, y_) && nodes[i].y >= min(y, y_))
{
k--;
if (k == 0)
{
printf("%d\n", nodes[i].prop), flag = true;
break;
}
}
if (!flag)
puts("It doesn't exist.");
}
else
{
scanf("%d%d", &x, &y), x++, y++;
swap(cur[x]->x, cur[y]->x), swap(cur[x]->y, cur[y]->y);
swap(cur[x]->id, cur[y]->id), swap(cur[x], cur[y]);
}
}
return 0;
}
真的是玄妙重重。
我们先思考正常的暴力搜索：枚举每一次按下的颜色，然后检查继续更新。考虑用 IDA* 优化这个过程，首先估值函数就是剩下的颜色个数，因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。
这道题是一道很考察思维的题目，我在这里介绍 DP 的做法。
我们考虑 DP。大概的方程可以写成：
\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]
其中，\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量，然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\)，也就是每一个点集合的左右端点。这个区间满足一个根本的条件：这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\)，最后做个小 DP 更新数据即可。
这道题我在考场上打了一个错解，还骗到了 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\)就行了。
这道题还没写，是一道数位 DP，推荐记忆化搜索。
这道题是一道相当好的题目。
首先对于\(m = n – 1\)的情况，也就是树的形态下，可以考虑自下向上推，也就是从叶子节点开始推起，参考代码中 Toposort 的写法。然后，对于\(m > n\)的情况可以直接输出\(0\)，因为这个方程组并不存在唯一的解：\(m\)个未知数仅提供\(n\)个条件，这样是不成立的。
最后考虑\(m = n\)的情况。这种情况就是基环树了。首先，Toposort 会把支链上的答案全部统计完毕，并且合并到环上的点。最后，我们唯一要多做的事情，就是处理环上的方程组。考虑一个这样的环：