Abstract

XC 说最近要我们把 USACO 的月赛题刷一遍，所以就开了这个坑。

United Cows of Farmer John G

设 \(\texttt{last}_i,\texttt{next}_i\) 分别为第 \(i\) 头奶牛前、后第一个与它品种相同的奶牛的指标。

枚举合法区间的左端点 \(i\)，显然右端点只能在区间 \((i,\texttt{next}_i)\) 内。

设 \(i<j<\texttt{next}_i\)，则 \(j\) 是合法的右端点的充要条件为 \(\texttt{last}_j<i\)。

于是我们就将这题转化为了一道主席树的板子题。

Portals G

将每个点 \(u\) 拆成两个点 \(u_1,u_2\)，\(u_1\) 与边 \(p_{u,1},p_{u,2}\) 相连，\(u_2\) 与边 \(p_{u,3},p_{u,4}\) 相连。

因为拆除来的所有点度数均为 2，所以建出来的图的每个连通块都是一个环，而我么需要将所有环连起来。

对于点 \(u_1,u_2\)，若它们分属两个不同的连通块，我们可以以 \(c_u\) 的代价将这两个连通块合并。

所以我们借鉴 Kruskal 算法的思想，将每个点对 \(c_u\) 从大到小排序，依次考虑每个点拆除来的两个点当前是否在同一连通块中，若否，将 \(c_u\) 计入答案，再将这两个连通块合并即可，用并查集实现。

Permutation G

对于一个排列，它的前三个点连成 1 个三角形，第 4 个点要么在三角形内部，要么与前三个点中的 2 个连成的三角形包含了第 3 个点；

更一般的，第 \(k+1(k>3)\) 个点要么在前 \(k\) 个点中的三个点所构成的三角形内部，要么与前 \(k\) 个点中的 2 个点构成的三角形包含了其他 \(k-2\) 个点。

设 \(f_{T}\) 表示填完了三角形 \(T\) 内部的所有点，在 \(T\) 外的点的合法排列数。

转移考虑一个更大的三角形 \(T'\)，它与 \(T\) 有 2 个公共点，设在 \(T\) 外的点有 \(x\) 个，在 \(T'\) 的点有 \(y\) 个，则有 \(x-y-1\) 个点在 \(T\) 和 \(T'\) 之间。

\(T\) 和 \(T'\) 之间的点有 \(P(x-1,x-y-1)\) 种排列方式，\(T'\) 之外的点有 \(f_{T'}\) 种排列方式，根据乘法原理，\(f_{T'}\) 对 \(f_T\) 有 \(P(x-1,x-y-1)f_{T'}\) 的贡献。

考虑每个合法排列的前 3 个点，答案即为 \(\sum_{T}3!f_T=6\sum_{T}f_T\)。

United Cows of Farmer John P

考虑一个具有启发性的 \(\mathcal O(n^2)\) 算法：枚举合法区间的右端点 \(r\)，再枚举在区间 \((\texttt{last}_r,r)\) 内的左端点 \(l\)，显然 \(l\) 对答案的贡献为 \(l\) 是否在该区间重复乘上区间 \([l+1,r-1]\) 的不同的奶牛的品种数。

在 \(\mathcal O(n\log n)\) 的算法中，我们依旧枚举合法区间的右端点 \(r\)，我们发现每个左端点对答案的贡献可拆为一个 0/1 系数与某个值相乘，写一个线段树维护之。