USACO2024 OPEN

Silver A

先用随便一个优先队列求出最短时间（怎么分配面试官对总时间没影响）。

赛时的想法是用并查集维护所有曾同时间结束的面试官，但是是错的。

Hack：若面试官 \(a\) 与面试官 \(b\) 同时结束，之后 \(b\) 又与 \(c\) 同时结束。用并查集会认为 \(a,b,c\) 都是绑定的整体。但如果 \(a\) 可以，不一定能推出 \(c\) 可以。

那怎么做？如果牛 \(i_1\sim i_m\) 同时结束了面试，同时 \(m\) 头牛的面试官又面试了牛 \(j_1\sim j_m\)。令 \(i_1\sim i_m\) 向一个中间结点 \(P\) 连边，\(P\) 向 \(j_1\sim j_m\) 连边。则 \(u\) 可达 \(v\) 说明 \(u,v\) 能被同一个面试官面试。

则面试官 \(i\) 能面试 \(n+1\) 就等价于牛 \(i\) 可达 \(n+1\)。

Silver B

难点只在于怎么把多边形的顶点排序。如果排好序了就套个前缀和就行了。

怎么排序？对于同一 \(x\) 上的一些点 \(p_1\sim p_m\)，一定有竖向边 \((p_1,p_2),(p_3,p_4),\dots\)

横向边也同理。这样就能找出所有边，自然也能排序。

Silver C

题意简化：给定字符串 \(s\)。对于 \((K,L)\)，从 \(s\) 中取出每个长度为 \(K\) 的子串，再从每个子串中取出长度为 \(L\) 的字典序最小的（字典序相同选左边的）子串。设 \(|P(K,L)|\) 表示有多少个位置不同的长度为 \(L\) 的子串被选择了。

对于每个 \(i=1\sim n\)，求有多少个 \(|P(K,L)|=i\)。\(1\le n\le 3000\)。

注意当有多个字典序最小的，会选择最靠左的。

用 \(O(n^2)\) 的时间预处理出这两个数组：\(l_{L,i}\) 是最大的 \(<i\) 的且 \([l_{L,i},l_{L,i}+L-1]\) 的字典序 \(\le\) \([i,i+L-1]\) 的字典序的数。

\(r_{L,i}\) 是最小的 \(>i\) 的且 \([r_{L,i},r_{L,i}+L-1]\) 的字典序 \(<\) \([i,i+L-1]\) 的字典序的数。

则一个字符串 \([A,B]\) 会以 \([i,i+L-1]\) 作为其字典序最小的最靠左的子串的要求，就是 \([A,B]\) 包含 \([i,i+L-1]\)，且不包含 \([l_{L,i},l_{L,i}+L-1]\) 和 \([r_{L,i},r_{L,i}+L-1]\)。

显然可得 \(L\le B-A+1\le r_{L,i}-l_{L,i} + L - 2\)。

所以每个 \([i,i+L-1]\)，会给所有满足 \(L\le K\le r_{L,i}-l_{L,i} + L - 2\) 的 \((K,L)\) 贡献 \(1\)，用差分即可统计出所有