AtCoder Grand Contest 001

A - BBQ Easy

题目大意：

有\(2N\)个正整数，要两个一组分成\(N\)组，每组的价值为两个整数中较小的一个，现在要求最大化总价值。

题解：

因为\(\min(a,b)=(a+b-|a-b|)/2\)，因此，问题等价于最小化每组的两个整数差的绝对值之和。

排序后\(2k-1\)与\(2k\)一组即可。

B - Mysterious Light

题目大意：

有一边长为\(N\)的正三角形\(ABC\)，在\(AB\)边上有一点\(P\),\(AP=X\)，从点\(P\)沿\(BC\)方向出射一条光线，光线遇到三角形边界或者它自己的轨迹，都会发生反射，当光线再次回到\(P\)时将被吸收。求光线轨迹的长度。

\(2\le N\le 10^{12},1\le X<N\)，\(N,X\)均为整数。

题解：

光线的方向始终平行于正三角形某一条边，并会不断重复一个过程：从边长为\(a,b\)的平行四边形某边经过邻边的反射射向内部。

令\(f(a,b)\)表示这一过程的轨迹长度，则答案为\(N+f(N-X,X)\)。

不妨令\(a\le b\)，则\(f(a,a)=a\)，\(f(a,b)=2a+f(b,b-a)\)，这样就得到了\(O(N)\)的递推。

考虑用类欧几里得算法来加速计算，令\(f(0,a)=-a\)，则当\(0<a\le b\)时，有\(\displaystyle f(a,b)=2a\times\lfloor\frac{b}{a}\rfloor+f(b\mod{a},a)\)。

时间复杂度\(O(\log{N})\).

C - Shorten Diameter

题目大意：

给出一棵\(n\le2000\)的树，问至少删除多少个节点（与之相关的边也一同删去），使得剩下的节点仍是一棵树，并且直径不大于\(K\)。

题解：

设一棵树的直径为\(D\)：

• 若\(D\)为偶数，则任意点到重心的距离不大于\(\displaystyle\frac{D}{2}\)；

• 若\(D\)为奇数，则任意点到两个重心中较近的一个的距离不大于\(\displaystyle\frac{D-1}{2}\)；

因此可以枚举删除点后的树作为重心的点（边），则到其距离不满足上述限制的点必须删去。

取\(n\)种情况中最优的即可。

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

D - Arrays and Palindrome

题目大意：

有两个正整数数列\(a\)和\(b\)，满足\(\sum a=\sum b=N\)。

并且，如果一个长度为\(N\)的字符串满足：

• 按\(a_1,\cdots,a_m\)分成不相交的\(m\)段，则每段都是回文串；

• 按\(b_1,\cdots,b_k\)分成不相交的\(k\)段，则每段都是回文串；

上述两个条件，则其一定是由单一字符组成的字符串。

现在只知道数列\(a\)是给定数列\(A\)的一个排列，请给出一个合法的\(a,b\)数列，或者判断其不可能。

\(1\le N\le10^5,1\le m\le 100\).

题解：

对于\(M=1\)的情况：显然\(N=1\)的时候\(a,b\)都是\(\{1\}\)，当\(N>1\)时，取\(b=\{N-1,1\}\)即可。

对于\(M=2\)的情况：若\(a={a_1,a_2}\)，显然\(b=\{a_1-1,a_2+1\}\)满足条件。

对于\(M\ge3\)的情况：

如果\(A\)中奇数项多于\(2\)，无解，证明如下：

设\(a\)中奇数项有\(O_a\)个，\(b\)中奇数项有\(O_b\)个，则一共有\(\displaystyle\frac{N-O_a}{2}+\frac{N-O_b}{2}\)条边，要使图连通，则边数不能小于\(N-1\)，因此有\(O_a+O_b\le2\)。

如果\(A\)中奇数项不多于\(2\)，我们尽量将奇数项移动到首尾两个位置，然后令\(b=\{a_1-1,a_2,\cdots,a_{M-1},a_M+1\}\)，这样恰好有\(N-1\)条边且不存在环，证明如下：

\(a_i=b_i,2\le i\le M-1\)，且\(a_i\)为偶数，两段错开一位，用这部分的边可以将\(a_i+1\)个点内部连通，形成以首尾两个点为端点的一条链。

\(a_1,b_1\)和\(a_M,b_M\)两段，\(a,b\)奇偶性不同，将内部的点的也连成一条链，一个端点是首尾，另一个是奇数段的中点。

这样\(M\)段首尾相连成为一条长链，端点为首尾两段奇数段的中点。

注意特判\(a_1=1\)的情况，\(b\)的实际长度为\(M-1\)而不是\(M\)。

E - BBQ Hard

题目大意：

有\(n\le2\times10^5\)包物品，第\(i\)包物品中有\(A\)类物品\(1\le A_i\le2000\)个，\(B\)类物品\(1\le B_i\le2000\)个，同类的物品个体之间不存在差异。

现在要从中取出两包物品，将其中的物品都取出，再将其中的物品按某种顺序排列，问有多少种不同的方案。

两种方案不同当前仅当选择的两包物品不同，或者其中物品的排列顺序不同。

题解：

如果确定选择第\(i\)包和第\(j\)包物品，则不同的方案共有\(\displaystyle \frac{(A_i+A_j+B_i+B_j)!}{(A_i+A_j)!(B_i+B_j)!}\).

这个几何意义可以是从只能向上和向右走的网格中从\((-A_i,-B_i)\)走到\((A_j,B_j)\)的方案数。

因此可以用dp求出从\((-A_1,-B_1),\cdots,(-A_n,-B_n)\)中任意位置出发走到\((A_i,B_i)\)的方案数求和，再减去从\((-A_i,-B_i)\)走到\((A_i,B_i)\)的方案数之和，最后再除以\(2\)消序即可。

时空复杂度\(O(n+m^2)\)，其中\(m\)为坐标范围。

F - Wide Swap

题目大意：

给出一个\(1,\cdots,n\)的排列\(P\)和常数\(K\)，\(1\le K<n\le5\times10^5\)。

如果\(P\)中存在两个位置\(1\le i<j\le n\)，且\(j-i\ge K\)，\(|P_i-P_j|=1\)，那么可以选择交换\(P_i\)和\(P_j\)。

可以经过任意次上述操作，求最终排列中字典序最小的。

题解：

首先证明，若\(|i-j|<K\)且\(P_i<P_j\)，在最终排列\(P^{'}\)中，一定有\(P^{'}_i<P^{'}_j\)。

令\(Q\)为\(P\)的逆运算，即\(Q_{P_i}=i\)，则对\(P\)的操作等价于对\(Q\)的操作：若\(Q\)中相邻的两个位置\(|Q_i-Q_j|\ge K\)，则可以交换\(Q_i,Q_j\)。

因此如果\(|i-j|<K\)且\(P_i<P_j\)，则在\(Q\)中有\(i<j\)，\(|Q_i-Q_j|<K\)，而要改变相对位置，必须发生一次它们在相邻位置的交换，而这是不可能的。

有了上述性质，原问题就转化为了，一个\(n\)个点的有向图，若\(|i-j|<K\)且\(P_i<P_j\)，则图中存在一条从\(i\)到\(j\)的出边，求该有向图的字典序最小拓扑序。

这个问题的做法很简单，每次贪心的找到编号最大的出度为\(0\)的点，将它添加到逆拓扑序的下一位，然后删掉该点和它所有的入边，不断重复直到所有点都被加入逆拓扑序。

因为边数很多，达到了\(O(n^2)\)级别，我们不可能真的去建出图来，但是根据本题的性质可以得到，\(i\)没有出度，当且仅当区间\([i-K+1,i+K-1]\)的最大值等于\(P_i\)。

因此可以用线段树维护单点修改和区间查询最值，来\(O(\log{n})\)删除一个点，以及check一个点是否没有出度。

然后将原序列按大小\(K\)分块，每一块中没有出度的点只可能是块内\(P\)最大的点，而删去一个点只会影响最多\(3\)块的情况。

再顺便用priority_queue维护一下没有出度的点的编号大小即可。

时间复杂度\(O(n\log{n})\).