PA2014 Kuglarz

最小生成树

BZOJ

设 $S_i$ 为前 $i$ 个杯子底下小球总数的奇偶性

那么每次告诉一个区间 $[l,r]$ 中的总数的奇偶性就等于告诉了 $S_r \oplus S_{l-1}$，这样子的话只要知道其中的一个就能知道另外一个。

为了能够猜出每个杯子底下是否有球，就得求出每一个 $S_i \oplus S_{i-1}$ 也就是求出所有的 $\{S\}$。这样，对于每个 $C_{i,j}$ 从 $i$ 到 $j$ 连一条边权为 $C_{i,j}$ 的无向边，然后以 $0$ 为根跑 MST 就行了。

貌似要用 Prim 以及要开 long long。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define int long long
const int INF = 0x3f3f3f3f;
const int MAXN = 2000 + 5;
int N, Ans, Edge;
int D[MAXN], FT[MAXN];
bool Vis[MAXN];
std::priority_queue < std::pair < int, int > > Q;
struct Linker
{
    int to, w, nxt;
    Linker(){}
    Linker(int x, int y, int z)
    {
        to = y;
        w = z;
        nxt = FT[x];
    }
} E[4200000 + 5];
inline int read()
{
    register int x = 0, v = 1;
    register char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') v = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * v;
}
inline void AddEdge(int x, int y, int z)
{
    E[++Edge] = Linker(x, y, z);
    FT[x] = Edge;
}
void Prim()
{
    memset(D, INF, sizeof(D));
    D[0] = 0;
    Q.push(std::make_pair(0, 0));
    for(int i = 1; i <= N; ++i)
    {
        std::pair < int, int > from;
        do
        {
            from = Q.top();
            Q.pop();
        }
        while(Vis[from.second]);
        Vis[from.second] = 1;
        for(int k = FT[from.second]; k; k = E[k].nxt)
        {
            int to = E[k].to, w = E[k].w;
            if(!Vis[to] && D[to] > w)
            {
                D[to] = w;
                Q.push(std::make_pair(-w, to));
            }
        }
    }
    for(int i = 1; i <= N; ++i) Ans += D[i];
}
signed main()
{
    N = read();
    for(int i = 1; i <= N; ++i)
    {
        for(int j = i; j <= N; ++j)
        {
            int w = read();
            AddEdge(i - 1, j , w);
            AddEdge(j, i - 1, w);
        }
    }
    Prim();
    printf("%lld\n", Ans);
    return 0;
}