A Kyoya and Colored Balls

题意真难懂虽然不长。

题意:在放置最后一个 k 颜色的球的时候 要保证所有的1~k-1的球都放上。问有多少种这样的排列。

思路:模拟一下整个过程应该就可以得出思路。以第一组样例为例子描述一下过程。

首先放两个1,肯定随便放,两个1,1. 再放两个2的时候。 首先肯定要在最后位置放个2无疑。那么现在的序列就是1 1 2.

如果再放一个2. 有多少种方法呢? _1_1_2. 三个空位放一个2. 自然是三种方法。 放3的时候。因为只有一个 所以只能放在最后。

其实我们可以发现。在整个过程中。我们就是每次先把一个k颜色的球放在最后。然后把剩下的球放在那些空位上有多少种方法。

简化一下就是 n 个相同球 放在m 个不同的箱子(位置不同)里, 有多少种方法。

这个可以参考:http://wenku.baidu.com/link?url=nN7n_lGYZ5UBAwIxgJhvKTaHRnW6Y_WJNOLLP6cHDnsZts7oRAdyrj3IV2aM6tjXbPJNnGn0jPPHOT8IEdYJl6GgWyA-80don2U2bO-yWNW

最后乘法原理即可。

B Kyoya and Permutation

题意:题意太难描述了。基本就是对于多少循环的圈,在排序之后得到一个新的序列,求第k种原序列=新序列的序列。

思路:这个题自己想出来还是有难度的,但是会了之后,发现略水。。。首先第一步 最重要的是要证明能满足上面条件的序列。任何一个圈的大小都小于等于2。也就是说形成的各个圈的两个元素是要相邻的。 因为只有是相邻的在交换之后在排序是原排列。

证明看原文吧。

Here’s a proof for why this is. Consider the cycle that contains n. Since n is the largest number, it must be the last cycle in the sequence, and it’s the first element of the sequence. If this cycle is length 1, then we’re obviously ok (we can always append (n) to the end). If the cycle is of length 2, we need n to be involved in a cycle with n - 1. Lastly, if the cycle is of length 3 or more, we will see we run into a problem. We’ll only show this for a cycle of length 3 (though this argument does generalize to cycles of larger length). Let (nxy) be the cycle. So that means, n is replaced by x, x is replaced by y and y is replaced by n. So, in other words, the original permutation involving this cycle must look like

position:  … y x n

number:   … n y x

However, we need it to look like (nxy) so this case is impossible.

有这个证明之后。 我们要求出 当长度为n的时候 有多少种排列,以次为判断来判断是否发生了交换。

那么d[n] 也比较容易递推。

1.如果第n项和第n-1项发生了交换,那么d[n] += d[n-2],

2.如果第n项和第n-2项没有交换,那么d[n] += d[n-1].

即 d[n] = d[n-1] + d[n-2]。307的时候最终也是推出了fib…

下面就是求序列了。

判断第1项是否发生过交换,那么就需要判断后面的d[n-1]是否小于k。 如果 d[n-1] < k 的话说明 仅仅凭n-1项不足以达到有k种排列,

所以第1项一定发生了交换。。 以此种思想递推一下即可了。。

 

Codeforces Round #340 (Div. 2) 解题报告

好久没写一整套cf的解题报告了。自从区域赛完之后就没打,但是不能放下! A.Elephant 题意:初始位置为0,每次可以走1,2,3,4,5步,问到达位置n最少需要多...

阅读全文

Codeforces Round #323 (Div. 2) A,B,C,D

太弱了。E题至今看不懂题解意思。。 A。水题, 题意:太难读了!输入n个交点,输出所有没有经过过的交点的位置。 思路:标记一下直接判就行了。 ...

阅读全文

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] (A,B,C)

A。A Problem about Polyline 直接求/二分 题意:有一中图形 结构为 /\/\/\/\ 这样,给你一个点(a,b)让你求最小的x使得该点在这种图形上。 思路1. 当然可...

阅读全文

3 条评论

欢迎留言

*