我们用一个数列 \(\{a_n\}\) 来表示这些杯子，\(a_n=1\) 表示第 \(n\) 个杯子下藏有小球，\(a_n=0\) 表示没有。那么第 \([l,r]\) 个杯子底下藏有球的总数的奇偶性就可以用这一段上的异或和 \((a_l \text{xor} a_{l+1} \cdots \text{xor} a_r)\) 来表示。设 \(\{a_n\}\) 的异或前缀和为 \(\{b_n\}(b_n=a_1 \text{xor} a_2 \text{xor} a_3 \cdots \text{xor} a_n)\)。
花费 \(c_{i,j}\) 元，魔术师就会告诉你杯子 \(i,i+1,…,j\) 底下藏有球的总数的奇偶性。
也即每询问一次 \([l, r]\)，我们可以得到 \(b_r \text{xor} b_{l-1}\) 的结果。
如果我们求出了 \(\{b_n\}\)，便可以很快求出 \(\{a_n\}\)，“保证猜出哪些杯子底下藏着球”。显然 \(b_0 = 0\)，而 \(b_1∼b_n\) 是未知的。我们每询问一次，都可以得到一个方程。要解出这 \(n\) 个未知数，就需要 \(n\) 个方程联立。也就是说我们总共需要询问 \(n\) 次。
将 \(\{b_n\}\) 看作一系列的点，将询问看作连接边 \((l-1,r)\)，那么我们所要求的就变成了用 \(n\) 条边连通 \(0∼n\) 这 \(n+1\) 个点，使得边权总和最小，即求最小生成树。该题给出的是稠密图，适合使用 prim 进行求解，复杂度为 \(O(n^2)\)。
代码如下。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2010;
int n,t;
int e[MAXN][MAXN],dist[MAXN];
ll ans;
bool book[MAXN];
void prim(){
memset(dist,0x3f,sizeof(dist));
dist[0]=0;
for(int i=0;i<n;++i){
int x=-1;
for(int j=0;j<=n;++j){
if(book[j]) continue;
if(x==-1 || dist[j]<dist[x]) x=j;
}
book[x]=true;
for(int y=0;y<=n;++y){
if(!book[y]) dist[y]=min(dist[y],e[x][y]);
}
}
}
int main(){
scanf("%d",&n);
memset(e,0x3f,sizeof(e));
for(int i=0;i<=n;++i) e[i][i]=0;
for(int l=1;l<=n;++l){
for(int r=l;r<=n;++r){
scanf("%d",&t);
e[l-1][r]=e[r][l-1]=t;
}
}
prim();
for(int i=1;i<=n;++i) ans+=dist[i];
printf("%lld",ans);
return 0;
}