A

假设我们以i为分界点，选取i以前的为J组，i以后的为S组(规定第i个被分到J组)
J组还可以选\([1,i-1]\)这个区间里的i?1个人，方案为 \(2^{i-1}\)
那么S组可以选\((i,n]\)区间里的n?i个人，去掉一个都不选的不合法方案，其总方案数为 \(2^{n-i}-1\)

i号点的贡献为：$2^{i-1}\times(2^{n-i}-1) $
i的取值范围是\([1,n]\)(n号点可以取，因为\(2^{n-1}\times(2^{n-n}-1)=0\)）
那么答案就为\[\sum_{i=1}^{n}\ (2^{n-i}-1)\times (2^{i-1})\]
打开括号：\[\sum_{i=1}^{n}\ (2^{n-1}-2^{i-1})=\sum_{i=1}^{n}\ 2^{n-1}-\sum_{i=1}^{n}\ 2^{i-1}\]
整理得：\[Ans = (n-2)\times (2^{n-1})+1\]

此题规模巨大，注意使用快速乘

由于上次OB学长模拟题的影响，我想了半天的组合数，推来推去推了2h结果什么都没推出来，结果最后是这个，难受
就算得到了第一个式子我也没有化简，难受\(++\)
化简完了我也想不到要快速乘，难受\(+=inf\)

B

建一个虚拟的n+1号点,然后把这个点和每个要塞点连Len=0的边
以n+1号点为起点跑Dijkstra，由于它和要塞点们的距离为0，这就相当于跑了一个多起点的最短路
用P[i]记录第i号点的起点是哪一个要塞点，在更新dis[i]的时候更新P（需要特判从n+1号点更新的情况），对于要塞点，P[a[i]]=a[i]

之后用一个结构体存下来再依次讨论每条边。
设这条边的长度为z，两个端点分别为x,y
如果 p[x]!=p[y] ,即存在一条p[x]→p[y]的长度为dis[x]+dis[y]+z的路径
用ans[]存下来然后取个min

1009-自闭++

原文：https://www.cnblogs.com/qwqq/p/11649949.html