解题思路

1. 问题分析：

   • 给定所有灌木丛两两之间的距离，需要恢复出灌木丛的位置序列。
   • 计算相邻灌木丛之间的距离的乘积P。
   • 如果无法唯一确定位置序列，则输出“No solution”。

2. 关键步骤：

   • 距离排序： 输入的距离已经按非递减顺序排列。
   • 位置恢复： 使用回溯法尝试从距离中恢复灌木丛的位置序列。
   • 乘积计算： 如果位置序列唯一，计算相邻距离的乘积P；否则，输出“No solution”。

3. 算法选择：

   • 采用回溯法来解决“收费站重建问题”（Turnpike Reconstruction Problem）。
   • 从最大的距离开始，逐步确定灌木丛的位置，验证其合法性。

解决代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include <string.h>
using namespace std;

#pragma comment (linker , "/STACK:102400000,102400000")
const int maxn = 500000;
int dis[maxn];
int cnt[maxn];
int hk[maxn];
int loc[1010];
int sz , n , ans , node_sum;


void init()
{
	sz = 0;
	ans = 1;
	memset(cnt,0,sizeof(cnt));
}

void input()
{
	int x;
	for (int i = 0 ; i < n ; ++i)
	{
		scanf("%d",&x);
		if (sz==0 || dis[sz-1]!=x)
		{
			dis[sz] = x;
			cnt[sz++]++;
		}
		else ++cnt[sz-1];
		hk[i] = sz-1;
	}
}

int Bisearch(int left,int right,int x)
{
	int mid = (left+right)>>1;
	while (left<=right)
	{
		if (dis[mid]==x) return mid;
		else if (dis[mid] < x) left = mid+1;
		else right = mid-1;
		mid = (left+right)>>1;
	}
	return -1;
}

bool dfs(int cur,int rest,int node_cnt)
{
	if (rest==0)
	{
		ans = loc[0];
		for (int i = 1 ; i < node_cnt ; ++i)
			ans *= loc[i]-loc[i-1];
		return true;
	}
	if (cur > n) return false;
	int x = hk[cur];
	bool ok = true;
	loc[node_cnt++] = dis[x] , --cnt[x];
	int *stk = new int [node_cnt+10];
	if (cnt[x] < 0 || (node_cnt > 1 && loc[node_cnt-2]==dis[x])) ok = false;
	int top = 0;
	for (int i = 0 ; i < node_cnt-1 && ok; ++i)
	{
		int dif = loc[node_cnt-1]-loc[i];
		int p = Bisearch(0,sz-1,dif);
		if (cnt[p]==0) ok = false;
		stk[top++] = p;
	}
	if (ok)
	{
		for (int i = 0 ; i < top ; ++i) --cnt[stk[i]];
		if (dfs(cur+1,rest-node_cnt,node_cnt))
		{
			delete [ ]  stk;
			return true;
		}
		for (int i = 0 ; i < top ; ++i) ++cnt[stk[i]];
	}
	delete [ ] stk;
	--node_cnt , ++cnt[x];
	if (dfs(cur+1,rest,node_cnt)) return true;
	return false;
}

void solve()
{
	if (dfs(0,n,0))
		printf("%d\n",ans);
	else
		printf("No solution\n");
}

int main()
{
	//	freopen("input.in","r",stdin);
	while (scanf("%d",&n)==1)
	{
		init();
		input();
		solve();
	}
}