AtCoder Grand Contest 031 小记

前言

打过之后便明白了AGC大致就是这样一个比赛——便是前半小时切完AB题后面两小时就不知道干什么了…

这场是昨天晚上跟gyx老哥一起打的。哎,研究C题那个格雷码的时候他那个索尼的电子书真好用…

在这里写一些题解吧。

A – Colorful Subsequence

分析

考虑这个子序列的性质:每个字母只出现一次,所以我们对每个字母考虑它是不出现或者出现在哪个位置就可以计数了。

B – Reversi

分析

我们对于某种颜色的每个位置考虑,对于中间没有其他位置的两个位置不妨称它们是“相近的”。这种颜色上的一些变换就是由两个相近的变换组合而成,注意到两个相邻的位置如果是相近的那么这种变换是无效的。

考虑对于以某个位置结尾的序列计数,设到这个位置的结果方案数为 \text{DP}[i]. 对于这个位置:

  • 什么都不做,那么方案数是 \text{DP}[i – 1]
  • 选择以这个位置结尾的颜色变换,设在这个颜色前面且与它相近的位置是l_i,这样方案数是 \text{DP}[l_i]

答案就是这两个加起来。

C – Differ by 1 Bit

这个问题看起来很容易让人联想到格雷码,但是正是因为联想到了格雷码所以我没做出来…

分析

我们抱着AGC不可能出结论题的心态取看这题。

注意到 P_iP_{i+1} 在二进制下仅一位不同,那么 P_iP_{i+1} 在二进制下1的位数奇偶性不同。从 AB 一共是 2^N-1 次,所以 AB 在二进制下1的位数奇偶性不同。这样我们就判别了无解的情况,接下来我们归纳证明当 A,B 在二进制下奇偶性不同时,问题总是有解的。

  • 首先对于 N = 1,显然成立
  • 考虑当 N=K-1 时,可以构造;当 N=K 时,因为 AB 在二进制下1的位数奇偶性不同,那么我们一定可以找到二进制下某一位 i(从右往左,从0开始),使得 AB 在这一位上不同。我们删去这一位,设新得到的数分别为 A’,B’,这两个数二进制下1的位数奇偶性相同。翻转 A’ 的最低位,设得到的数是 C,由假设可知我们可以构造 A’\to CC\to B’ 的方案。于是通过在方案的对应位上插入与AB原来删除的相同位就可以得到当前的解

于是实现的时候也可以按这种方式写一个递归的函数来解决。

拓展

通过这题我们知道了格雷码并不是唯一的遍历。

分析这题的时候,也可以把它看做是一张图,每个点度为 \log,然后我们求从给定起点到给定终点是否存在经过所有点的简单路径,这个问题似乎被称作汉密顿路,它是NP的。

D – A Sequence of Permutations

这是一道关于排列的问题。

在考虑这个问题之前,我们不妨来引入一些关于排列的知识。

排列

定义 一个排列 p1 ~ n 中自然数的某个排列方式,对于它的第 i 个元素记作 p_i.

合成 排列的合成也是一个排列,记 p\circ q 为排列 pq 的合成,简记为 pq,有(pq)_i=p_{q_i}. 注意,它不满足交换律

排列的逆 记排列 p 的逆排列为 p^{-1},有 p^{-1}_{p_i}=i.

且对于排列的逆,有 (pq)^{-1}=q^{-1}p^{-1}. 同理,对于排列 a_1,a_2,…,a_n,有 (a_1a_2…a_n)^{-1}=a_n^{-1}a_{n-1}^{-1}…a_2^{-1}a_1^{-1}.

或者,我们也可以将排列看做是作用于1..n的置换,容易理解上面的定义。

分析

我们知道,f(p,q)=qp^{-1}.

通过这个式子,我们展开前几项,寻找规律。

如果设 B=qp^{-1}q^{-1}p,那么当 i>6 时,满足 a_i=Ba_{i-6}B^{-1} . 利用这个简单的规律,我们就可以快速算得答案了(合成运算满足结合律,快速幂)。

E – Snuke the Phantom Thief

分析

我们不妨先考虑一维的限制,也就是只有LR限制的时候。

因为 N 较小,我们设置一个值 K,表示thief必须要偷 K个宝物,以此简化问题。我们将这 K 个宝物按 x 坐标从小到大排序,并标号 1,2,…,k,考虑限制:

  • L,这意味着标号 b_i+1 的宝物横坐标至少为 a_i+1
  • R,这意味着标号 K-b_i 的宝物横坐标至多为 a_i-1

这样对于这 K 个宝物中的每一个,我们都得到了它的横坐标范围限制,接下来就是考虑如何选择使得总贡献最大了。

鉴于此题的范围,我们可以用较暴力的费用流解决。考虑对 1,2,..,k 每一个宝物都设一个代表点,从S到它连流量为1、费用为0的边;该点向满足它范围的宝物连流量为1、费用为这个宝物价值的相反数的边;然后每个宝物再向T连流量为1、费用为0的边。使用最小费用流算法即可。

我们很容易将它拓展到二位情况,对于纵坐标的限制我们可以类似的考虑。至于建图,我们需要将每个宝物拆为两个点,然后在他们之间连负的价值的边;另外在从拆出来的后一个点,向纵坐标的代表点连边就可以了。

这道题补的时候WA了十多发,原因竟是数组下标搞错了…

小结

这个建模应该是挺套路的。

F – Walk on Graph

F还没打算补…

搁着吧,我保证填坑!

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注