【P5994 [PA2014]Kuglarz】题解

题目链接

题目

魔术师的桌子上有 \(n\) 个杯子排成一行，编号为 \(1,2,…,n\)，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。

花费 \(c_{ij}\) 元，魔术师就会告诉你杯子 \(i,i+1,…,j\) 底下藏有球的总数的奇偶性。

采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

思路

前缀和建图+最小生成树。

对于查询区间 \([i,j]\)，我们其实知道了区间 \([1, j]\) 和区间 \([1, i]\) 的差为多少。

既然如此，我们可以在 \(j\) 和 \(i-1\) 之间建边。

当所有的点连起来的时候，我们就可以确定所有解。

总结

这是一道很不错的前缀和建图题。

这道题的核心在于对于询问一段区间的奇偶，可以用前缀和表示，通过建图，再求最小生成树，可以构建唯一解。

Code

// Problem: P5994 [PA2014]Kuglarz
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5994
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 2010
struct node
{
	int x, y, z; 
}d[N*N]; 
int n, m, i, j, k; 
int f[N], u, v, ans; 

void cun(int x, int y, int z)
{
	d[++m].x=x; d[m].y=y; 
	d[m].z=z; 
}

bool cmp(node x, node y)
{
	return x.z %lld %lld %lld\n", d[i].x, d[i].y, d[i].z); 
			f[u]=v; 
			ans+=d[i].z; 
		}
	}
	printf("%lld", ans); 
	return 0; 
}