111qqz的小窝

老年咸鱼冲锋!

leetcode 60. Permutation Sequence (求第k个排列)

The set [1,2,3,,<i>n</i>] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

 

思路:还是根据leetcode 31 解题报告 中的算法搞一下就好了。。

 

leetcode 47. Permutations II (生成全排列,有重复元素)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
思路:和leet code 46 类似,最后用set去个重即可。。

 

leetcode 46. Permutations (生成全排列,无重复元素)

Given a collection of distinct numbers, return all possible permutations.

思路:调用n-1次 leetcode 31 解题报告 中提到的算法即可。。。

 

leetcode 31. Next Permutation (in-place 生成下一个全排列)

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

 

思路: 参考了wiki_Permutation

有一个算法完美解决了这个问题,空间复杂度O(1),时间复杂度O(n)

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l greater than k such that a[k] < a[l].
  3. Swap the value of a[k] with that of a[l].
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

 

hdu 2049 不容易系列之(4)——考新郎 (错排公式,注意精度)

hdu 2049 题目链接
题意:n个妹子和n个汉子对应。。然后让每个汉子取选一个妹子,不能重复,问恰好有m个汉子选错妹子的可能的方案数。

思路:从n个中选n-m个,然后做剩余m个错排即可。

答案就是c[n][n-m]*d[m]  c[]为组合数公式,d为错排公式。
然而wa到死。。。

因为我用了double….有毒。。。

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

Screenshot from 2016-07-27 19-49-40

我自杀去了,世界再见(x

 

 

 

 

hdu 2048 神、上帝以及老天爷 (错排公式)

hdu2048 题目链接

题意:n个人不放回的从一个有n个每个人对应id的卡片的盒子取一张卡片,取的正好和自己的对应就算中奖。求所有人都没有中奖的概率。

思路:错排。。。

复习了一下错排公式。。。d[n] = (n-1)*(d[n-1]+d[n-2])  (d[1]=0,d[2]=1)

然后求概率的时候。。惊讶得发现概率稳定在了36.79%(1/e)附近。。。

这是因为。。。错排还有一个公式:D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

求概率每次把n!除掉了。。剩下的。。其实就是e的泰勒展开,当x=-1时的值。

因为当n越大时。。这个概率越接近1/e

这道题里。。。在保留百分数的小数点两位的精度的条件下。。当n为7的时候。。答案就已经是36.79保持不变了。。。

 

 

 

 

bzoj1600 [Usaco2008 Oct]建造栅栏 (排列组合)

勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n(4<=n<=2500)的木板,他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意: *只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况,go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

思路:排列组合。。减法原则。长度为n的木板,有n-1个切点,那么n-1个切点切三刀的方案数就是C(n-1,3) ,但是这里面有不能构成四边形的。

构成四边形的条件是:任意三边之和大于第四边。也就是任意a+b+c>d,可以得到d<n/2

为方便描述,我们不妨认为从左往右切,先且最左边,再切最右边。

并且先讨论最右边的木板是长度最长的。

所以我们最后一刀一定切在n/2之后的地方。

此时无论之前的两刀是怎么切的,由于切完出现的三块的长度和是一定的,所有都一定能构成四边形。

多算的部分就是从n/2点,最左边可以切到3点的方案数。

如果最后一刀切在点i,那么左边还剩下i-1个点,选两个点切,方案数为C(i-1,2)

将多切的方案数sad按照最后一刀的切点累加。

需要注意的是,我们之前为了方便讨论,设最后一个木板是最长的,然而实际上四块木板都有可能是最长的。 所以多切的方案数sad=sad*4

 

哦,听说这题dp也能过。。。。?反正我是想不到。

bc #77 div 2 B ||hdu 5651 xiaoxin juju needs help (排列组合,逆元)

题目链接
题意;给出一个字符串,只由小写字母组成,可以任意排列,但是不能减少字符,问最多能得到多少个回文串,答案%1E9+7

思路:排列组合题。 首先考虑无解的情况。统计出每个字母出现的次数,当字符串长度为奇数而且出现次数为奇数的字母的个数多于1个时无解,或者当字符串长度为偶数,出现次数为奇数的字母的个数多于0个时无解。
接下来,由于是回文串,只需要考虑len/2的情况,另一半是一一对应的。
其实就是一共有len/2的元素,其中有一些重复的,然后全排列。 多重元素的排列问题。
答案为(len/2)! % (cnt[1]!)% (cnt[2]!)…即可
哦要先把cnt降序排一下,只考虑cnt[i]>1的元素,然后因为是要考虑一半长度,所以每个cnt[i]/2
那一堆阶乘直接逆元搞就好了。。。。

比赛的时候手滑,把cnt[i]!写成了cnt[i],wa了一发。。。