AtCoder Beginner/Regular Contest 097


Colorful Transceivers

题意

给出 \(a,b,c\) 的坐标,距离 \(\le k\) 的能沟通,问 \(a,c\) 能否沟通。

分析

沟通的方式只有两种:

  • \(a,c\) 直接沟通, \(|a-c|\le k\) ;
  • \(a,c\) 通过 \(b\) 沟通, \(|a-b|,|c-b|\le k\) 。

Exponential

题意

找一个 \(b^p\le x\) 其中 \(b\ge 1,p\ge 2\) 。

分析

因为 \(x\le 1000\) ,暴力枚举 \(b,p\) 即可。

K-th Substring

题意

将字符串的所有子串去重排序,求字典序第 \(k\) 小的子串。

分析

因为 \(k\le 5\) ,考虑字典序 \(k\) 小的,长度一定不会超过 \(k\) (即使全部一样,也可以通过某一位开始截取 \(k\) 个不同的得到)。

于是从每一位开始分别截取长度 \(\le k\) 的子串,去重排序输出字典序 \(k\) 小的即可。

Equals

题意

允许交换其中的一些位置,要求任意交换以后最大化 \(p_i=i\) 的位置。

分析

因为可以任意交换,所以如果存在 \((a,b)\) 可以交换、\((b,c)\) 可以交换,则显然 \(a,b,c\) 可以任意的互换位置。

于是对于给出的关系,我们相当于可以得到,好几类的位置,同一类中的位置可以任意交换。

而对于同一类中的位置,我们有两个信息,一个是位置信息,一个是位置上的排列信息,我们可以用一个 set 来帮助获得最大的匹配量。

Sorted and Sorted

题意

每次可以交换任意的两个相邻位置。要求在全部交换完成后,同一种颜色的信息要保证相对有序。

分析

我们可以知道,如果只有一种颜色的话,其实就是求逆序对的个数。

而且如果要输出方案的话,暴力的从前往后将每一个数回归到他所在的位置即可。

我们可以观察到,暴力的从前往后将每一个数归位,一定是将一个数从口后的位置依次相邻交换到他所在的位置上,而其中,除了正在向前挪动的数,其余数的相对顺序是不会变化的。也就是说,如果我们确定了两种颜色的数分别已经排列到了哪里,下一个数要归位的,我们可以通过排在之前数直接得到。

我们用 \(f[i][j]\) 表示当前处理到第 \(i\) 个位置,且黑色的排列到 \(j\) 号。显然,此时白色的排列到 \(i-j\) 号。

每次我们可以放入黑色的 \(j+1\) 号或者白色的 \(i-j+1\) 号。

对于即将放入的黑色的 \(j+1\) 号,需要挪动的位置为下列两个之和:

  • 黑色的,需要 \(> j+1\) 的且排在 \(j+1\) 号之前的;
  • 白色的,需要 \(> i-j\) 的且排在 \(j+1\) 号之前的。

这两个信息,显然可以通过预处理得到,于是就可以 \(O(1)\) 转移了。

Monochrome Cat

题意

给一棵树,树的每个节点是白色或者是黑色。

可以选择一个位置出发,有以下两种操作:

  • 反转当前所在位置的颜色;
  • 走到一个相邻的位置,并改变其颜色。

求最小的操作次数,使得整棵树变成黑色。

分析

显然,如果节点是黑色的而且是叶子结点,可以直接删除。

经过一些叶子结点删除以后,可能会产生新的黑色的叶子结点,循环删除,直到不存在这样的黑色叶子结点。

对于剩下的树,如果要求出发结点和结束节点必须要相同的话,可以发现,因为要遍历到所有的叶子结点,所以最小的次数就是把整棵树的所有边和节点遍历一遍。

那么对于度数为偶数的节点,会经过偶数次,如果这个点是白色的话,则需要依次额外的操作反转。

度数为奇数的节点,因为经过奇数次,本来为黑色的,现在需要额外的一次反转让其恢复黑色。

那么现在是可以其实节点和最终节点不同的,也就是相当于在之前的基础上,删除一条从起点到终点的路径。

相当于路径上的点,都少经过一次:

  • 对于本来需要一次额外操作反转的点,少经过一次,且不在需要额外的反转,则从原来的答案中 \(-2\) ;
  • 对于本来不需要额外反转的点,少经过一次,但需要一次额外的反转来还原状态,则所需要的操作不变。

现在的问题就变成了要找一条链,包含最多的本来需要一次额外操作反转的点。

显然就是求树上的带权直径,两次 dp 即可。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 123,357

Categories

Archive

Comments