首页 > 代码库 > Codeforces Round #414

Codeforces Round #414

A

=w=

B

qvq

C(贪心)

题意:

Alice和Bob分别有长度为n(n<=1e5)的字符串,Alice先手,每次从自己的字符串中抽出一个字母放到新字符串的某个位置,一共轮流n次,也就是说最后新字符串长度为n。Alice的决策时希望最后结果字典序最小,Bob则是希望最大,他们都是聪明的,请输出最后会得到怎样一个字符串。

分析:

先对A和B的字符串排序,A的字符串从小到大排序,B的字符串从大到小排序,并且舍去他们各自的后一半字符,这些肯定用不到

轮到A,A希望字符串字典序小

  1)最直观的贪心就是把我现在手里最小的甩到最前面

  2)但是考虑到一点,就是如果B手中所有字符比A手中最小的那个字符还要小,那其实A不需要把东西甩到最前面,最前面让B去补,那么结果会更小;所以就是如果遇见这种情况,那么A就把自己最大的一张丢到序列的最后面

轮到B,B希望字符串字典序打

  1)最直观的贪心就是把我现在手里最大的甩到最前面

  2)但是考虑到一点,如果B手中所有字符比A手中最小的那个还要小,那其实A不需要把东西甩前面,最前面让A去补,那么结果会更大;所以如果遇见这种情况,那么B就把自己最小的一张丢到序列最后面

具体实现就两个指针移一移

D(缩点)

题意:

给你一个联通的无向图(n<=3e5),你需要给每个点一个编号,要满足:任意一对相邻的点对,那么点的编号差<=1,;任意一对不相邻的点对,那么点的编号差>1

分析:

我们可以把那些“等价的点”全部编号设为一样的

什么样的点是等价的呢?

如果有一些点相邻的点(加上自己)都是一模一样的,那么它们就是等价的

具体来看,就是一个完全子图,他们的编号应该是一样的(除了连出去边的个边点)

所以可以对vector排序,挑出那些邻接表情况相同的点,全部缩点

然后很容易发现对于那些分叉的情况是没有解的,也就是所有点的度数必须<=2

那么度数<=2就是一个链或者一个环,经检验,环也是不符合的,只有链是符合的

输出方案就从链的一端直接从1开始递增填数字就行了

Codeforces Round #414