A. Sereja and Coat Rack
傻逼才错的题。不幸中枪。
没什么可说的。直接看代码就好。
B. Sereja and Suffixes
关键思想在于统计A[i...n-1]中有多少互不相同的数。
使用离线思想，把查询按greater<int>排序，然后使用Hash表进行统计，简单题。
C. Sereja and Algorithm
思路题。
我们容易想到如果可以交换相邻两个字母的位置，我们就可以获得这个字符串所有的排列。
所以我们只需要统计出A[i...j]中x, y, z的个数。
然后进行排列。
我们可以推出，稳定的排列（即可以使算法停下来的排列）只有如下几种情况。
zy[xzy][xzy]...
xz[yxz][yxz]...
yx[zyx][zyx]...
//[]中的是循环节
所以只需要数学上的一点计算就可算出我们可不可以生成以上的排列。
D. Sereja ans Anagrams
坑题。
一个简单的双端队列 + Hash表统计。
坑有两处，一是最后的结果需要去重。这个是我做法的问题，用一个Hash表判重，如果qa满足条件，后续就不需要枚举qa这个点了。
二是一些中间结果会爆int，所以要实时估计数据规模。
E. Sereja and the Arrangement of Numbers
欧拉路径。
先科普一下。（好吧，其实大家都知道，只有我忘记了。。。）
对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？
这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个环或者一条链），如果路径闭合（一个圈），则称为欧拉回路。
我们来简化一下问题。如果我们有k个numbers，若要生成一个符合条件的序列。则这k个数字的相邻关系必然能构成一个欧拉路径。
连通的无向图 G 有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。
所以我们容易求出在有k个点时，图中应该有多少条边，也就意味着我们的序列应该有多长。
回到我们的问题上来，我们限定了序列的长度，所以图中边的数目也有了限制。于是我们由边数使用二分枚举反推点数。
然后选取价格最高的t个点数，并算出总花费。
参考自liyishuai
代码
仅供参考：戳我
Comments
comments powered by Disqus