AGC001 题解 2019-05-26

\ Task Name Time Limit Memory Limit
A BBQ Easy 2 sec 256 MB Submit
B Mysterious Light 2 sec 256 MB Submit
C Shorten Diameter 2 sec 256 MB Submit
D Arrays and Palindrome 2 sec 256 MB Submit
E BBQ Hard 2 sec 256 MB Submit
F Wide Swap 5 sec 256 MB Submit

A

sort然后取max

B

每次操作可以看成把一个平行四边形减掉两个三角形然后就变成另一个平行四边形。设边长为\((x,y)\),那么下次就会成为\((x-y,x)\)。发现这个东西和求gcd有那么点相似,把减法改成取模,然后算一下最后一次的边界问题。

为什么我B题都不会

C

\(k\)是偶数的时候,那么枚举一个点作为根,深度大于某个\(\frac{k}{2}\)的都删掉。如果\(k\)是奇数,就枚举边,然后算一下。

见代码里的sub1和sub2

D

神仙构造题。

题意有点绕:

你有AB这两个序列,满足\(\sum a_i=n,\sum b_i=n\)

这个AB序列满足一个性质:

  • 对于任意长度为n的字符串,如果把它顺次分成长为\(A_1,A_2…A_n\)的子串,这些子串是回文的;而且分成\(B_1,B_2…B_n\)也是回文的;那么这个串的所有字母相同(也就是aaaaa…aaaa)。

你打乱了A序列(给出了你random_shuffle以后的A),弄丢了B序列。

现在让你还原AB序列。无解输出Impossible。

题解:

首先我们可以向下图这样把相等的字符连边。

那么就是要构造一个B使得所有点联通,其实是形成一条链。

首先一个性质

  • 如果A数组的奇数个数大于2一定无解。

    证明:奇数那么中间的那个点在A中无法连边,如果在B中有边那么它的度数为1。一条链显然不存在大于两个度数为1的点。

然后对于A中没奇数,一个奇数,两个奇数分别构造。

(一)A中没奇数

可以错开一位然后根据对称性匹配,我们把B[1]=1,然后\(B[i+1]=A[i]\),最后\(B[n+1]=A[n]-1\)。(如下图)

(二)A中有一个奇数

手玩一下就会发现和上面那个差不多。可以把奇数放到最后一位,构造方法就和上面一样了。

(三)A中有两个奇数

首先如果有两个奇数,那么一定有一个是开头一个是结尾。

这回把B[1]设为A[1]+1,B[i]=A[i],B[n]=A[n-1]。和上面类似。

E

给n个数对\((a_i,b_i)\) \[ \sum_{i=1}^{n}\sum_{j=i+1}^{n}\binom{a_i+b_i+a_j+b_j}{a_i+a_j} \] 吐槽:之前把数据范围看成\(n\leq 2000\)觉得是傻逼题,打完了发现不对。然后发现貌似可以二维FFT一下,但是\(\max a_i\)为2000,FFT复杂度为\(O(1e7 \log1e7)\),然后就自闭了。

正解要考虑到组合数的组合意义。直接做当然是做不了的。

首先n个数看成平面上的点,那么组合数就是从\((-a_i,-b_i)\)每次只能向右走或者向上走然后走到\((a_j,b_j)\)的方案数。

如果前面的\(\sum\)都是从1到n,那么求的就是以任意\((-a_i,-b_i)\)出发,到达任意\((a_j,b_j)\)的方案数。这东西显然可以dp。

然后减掉自己到自己的方案之后除2就是答案了。

F

构造\(a_{pi}=i\)然后会发现求p的字典序最小同时也是求a的字典序最小。

交换变成了如果相邻元素的差大于等于k就可以交换。那么对于那些差小于k的元素对,它们之间的相对位置关系是永远不会发生变化的。也就是b和c差小于k且b在c的前面那么b怎么换都会在c的前面。

那么可以根据相对位置关系建图。a连b代表b一定在a后面。然后用优先队列去topo sort就好了。

做完了?没有。

暴力连边的话复杂度可能到n方级别。

这个时候发现一个性质,如果x在y前面,而y在z前面,显然x到z的那条边是不需要的(前后有传递性嘛)。那么我们找到每个元素的右边的第一个和它有前后关系的连边,边数就是O(n)的了。

找的过程用线段树查一下min:倒过来扫,查一下然后把这个点更新到线段树上去。

summary

写这6个题收获还是很多的其实只会写A其他题都看了题解。确实要练习一下思路题。不是所有题都是能直接上数据结构&FFT这种东西的,而是需要思考和构造。这正是我比较薄弱的环节。