题解：P5994 [PA 2014] Kuglarz

若已知 各自的球数奇偶性，其差距 ，且奇偶性在加法运算上表现为异或，同时同起点区间查 是前缀和，则可用已知确定 位置是否有球。

由异或前缀和，易得 ，这意味着所需的 可以通过其他已有的关系间接推导出来。这种间接的关系显然地构成了一张图：

• 点是杯子序号；
• 边是已知信息 奇偶性；
• 边权是实现这个推导所需信息的代价；
• 连通性是两个点经过推导的可解性，吗？

那么问题来了，连通性是可解性，如何解决直接点对点查询？显然它并不连通，但是它具有可解性。怎么办？需要让特例融入一般。

由于一般的可解性来自于对第 个点的连通性，可以想到拆点，等效于在 上安装一个给 准备的接口 ，接口与目标之间没有代价因为是人为设置的，代价在于 的连接上，这个问题就被解决了。

注意到构成稠密图，稠密图上 的 prim 很好用，而且时间复杂度依赖点数，所以可以压缩点，把接口直接压在 上，则出现重边，根据贪心策略，g[i][i-1] = g[i-1][i] = min(read(), g[i][i-1])。注意初始化。

小彩蛋：我们注意到输入是 级别的。

代码：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 2005;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n;
LL g[MAXN][MAXN];

LL mst;
LL dis[MAXN];
bitset<MAXN> vis;

inline LL read();

inline void build() {
    n = read();
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            g[i][j] = INF;
    for (int i = 1; i <= n; ++i) {
        LL weight, u = i - 1, v;
        for (int j = i; j <= n; ++j) {
            weight = read(), v = j;
            g[u][v] = g[v][u] = min(g[u][v], weight);
        }
    }
    return;
}

inline void prim() {
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0;
    for (int i = 0; i <= n; ++i) {
        LL add = 0, minDis = INF;
        for (int j = 0; j <= n; ++j)
            if (!vis[j] && dis[j] < minDis)
                add = j, minDis = dis[j];
        mst += minDis;
        vis[add] = true;
        for (int j = 0; j <= n; ++j)
            dis[j] = min(dis[j], g[add][j]);
    }
    cout << mst;
    return;
}

int main() {
    build();
    prim();
    return 0;
}