比赛链接

给定 $n$ 个数，要求将它们分组。每组可以有 $1\sim 2$ 个数，每组的权重为这组里面的所有数的和。

要求最小化权重最大的组和权重最小的组的权重差。

首先考虑如果强制每组必须有两个数，则对任意两组 $(a_1,a_2),(a_3,a_4)$，设 $a_1$ 是这四个数中的最小值，则必有 $a_2$ 是这四个数中的最大值。

否则假定 $a_4$ 是这四个数中的最大值，考虑分组 $(a_1,a_4),(a_2,a_3)$。

则有 $\max(a_1+a_4,a_2+a_3)\le a_3+a_4,\min(a_1+a_4,a_2+a_3)\ge a_1+a_2$，显然更优。

于是设所有数为 $a_1\le a_2\le \cdots a_{2k}$，则最优分组为 $(a_1,a_{2k}),(a_2,a_{2k-1})\cdots (a_{k},a_{k+1})$。

一个数一组相当于这个数和 $0$ 一组。于是可以枚举向原序列中加入 $0\sim n$ 个 $0$ 的情况，然后按上述方法分组计算答案。

时间复杂度 $O(n^2)$。

const int MAXN=5e3+5,inf=2e9;
int a[MAXN<<1];
int main()
{
	int n=read_int();
	_for(i,0,n)a[i]=read_int();
	sort(a,a+n);
	int ans=inf;
	_rep(i,n,n*2){
		if(i%2==0){
			int maxv=-inf,minv=inf;
			for(int j=0;j<i/2;j++){
				maxv=max(maxv,a[j]+a[i-1-j]);
				minv=min(minv,a[j]+a[i-1-j]);
			}
			ans=min(ans,maxv-minv);
		}
		int pos=0;
		while(pos<i&&a[pos]<=0)pos++;
		for(int j=i-1;j>=pos;j--)
		a[j+1]=a[j];
		a[pos]=0;
	}
	enter(ans);
	return 0;
}

给定一棵 $n$ 个结点的树，问有多少个 $1\sim n$ 的排列 $P$ 满足 $p_i$ 不是结点 $i$ 在树上的祖先结点(不包括自己)。

设 $\text{dp}(u,i)$ 表示结点 $u$ 为根的子树中钦定 $i$ 个结点的 $p_i$ 是其祖先结点且该祖先结点位于结点 $u$ 为根的子树的方案数。

给定祖先结点必须位于结点 $u$ 为根的子树是为了防止子树背包合并时的冲突。

首先假定 $p_u=u$，然后进行树形背包合并。

然后考虑 $p_u\neq u$ 的贡献，发现此时可以选择任意一个没有钦定的结点 $v$，然后令 $p_u=p_v,p_v=u$，这样不合法的结点数加一。