请问一下一般做presentation那个放大和屏幕标记的软件是哪个？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Hardware - 计算机硬件

请问一下一般做presentation那个放大和屏幕标记的软件是哪个？

请问一下一般做presentation那个放大和屏幕标记的软件是哪个？# Hardware - 计算机硬件

w*k2012-11-09 08:11

1 楼

考古得到一个今年的google面试题(dawenxi88):已知一个长度为n的数组。假设一个子
集有k个数，则我们有k(k-1)/2个pair(x,y)。定义pair difference为|x-y|，子集的半
径为最小的pair difference。现在要求长度为k的半径最大的子集。原题在
http://www.mitbbs.com/article/JobHunting/31540541_3.html
大家讨论了很多，基本思路是DP。如果要求从A[i,j]中选k个数，则一定是从A[i,m]中
选p个数，A[i,m]中选k-p 个数，遍历所有的m和p，求一个最大值，就可以完成DP的一
步。这个命题看似正确，但是经不住推敲,因为这样组合起来不一定是半径最大的长度
为k的子集。假设
A[] = {0, 25, 49, 51, 75, 100 }
k= 4,p=2.
则{0, 25, 49}的半径最大子集是{0,49},{51, 75, 100 }的半径最大子集是{51,100 }
，但是{0, 25, 49, 51, 75, 100 }的最大半径子集显然不是{0, 49, 51, 100

p*n2012-11-09 08:11

2 楼

经常参加matlab的siminar，人家玩matlab的时候可以放大屏幕，还可以在屏幕上做标
记，怎么实现的？

s*a2012-11-09 08:11

3 楼

if given k number, find the minimum |x-y|
sort first, minimum distance = minimum difference of two neighbor numbers
a(i,j) choose K, I think we should also sort first and do DP

a*a2012-11-09 08:11

4 楼

zoomit
http://technet.microsoft.com/en-us/sysinternals/bb897434.aspx

h*62012-11-09 08:11

5 楼

这种题，可以二分的。
把数组排序后，找出最大值和最小值之差。然后在这个范围内判断，是否存在pair
distance至少为d的子集，存在则增加d，不存在则减小d。

s*a2012-11-09 08:11

6 楼

If now we have N numbers, and we want to choose k number with minimum radius
. P(N, k) on array A
sort the N numbers, the minimum distance is |Aj-Aj+1|, we know
either Aj or A(j+1) must not be in the k number
so the problem becomes P(N-1, k) on array without Aj, or without Aj+1

l*e2012-11-09 08:11

7 楼

应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
A[i], A[m], A[j]必然被选中

【在 w*****k 的大作中提到】

: 考古得到一个今年的google面试题(dawenxi88):已知一个长度为n的数组。假设一个子
: 集有k个数，则我们有k(k-1)/2个pair(x,y)。定义pair difference为|x-y|，子集的半
: 径为最小的pair difference。现在要求长度为k的半径最大的子集。原题在
: http://www.mitbbs.com/article/JobHunting/31540541_3.html
: 大家讨论了很多，基本思路是DP。如果要求从A[i,j]中选k个数，则一定是从A[i,m]中
: 选p个数，A[i,m]中选k-p 个数，遍历所有的m和p，求一个最大值，就可以完成DP的一
: 步。这个命题看似正确，但是经不住推敲,因为这样组合起来不一定是半径最大的长度
: 为k的子集。假设
: A[] = {0, 25, 49, 51, 75, 100 }
: k= 4,p=2.

t*a2012-11-09 08:11

8 楼

I think that is the right solution.

【在 l******e 的大作中提到】

: 应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
: A[i], A[m], A[j]必然被选中

h*62012-11-09 08:11

9 楼

可以化简一下：
A[i,m]中选2个数，A[m,j]中选k-1个数
A[i], A[m], A[j]必然被选中

【在 l******e 的大作中提到】

: 应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
: A[i], A[m], A[j]必然被选中

t*j2012-11-09 08:11

10 楼

同意这个思路，总的distance就是两个distance的min。

【在 l******e 的大作中提到】

: 应该是从A[i,m]中选p个数，A[m,j]中选k-p+1个数
: A[i], A[m], A[j]必然被选中

s*a2012-11-09 08:11

11 楼

这样和 brutal force 有区别吗？

【在 t*****j 的大作中提到】

: 同意这个思路，总的distance就是两个distance的min。

h*k2012-11-09 08:11

12 楼

brutal force 是exponecial的。
DP是O(kn)的

【在 s****a 的大作中提到】

: 这样和 brutal force 有区别吗？

B*n2012-11-09 08:11

13 楼

这里的m是任意的都可以吗？还是得遍历所有的m？
比如例子
A[] = {0, 25, 49, 51, 74, 96 }
选m=3的话就有问题
在A[1,3]={0,25,49}选2个数，即{0，49}， d=49
在A[3,6]={49,51,74,96}选k-1=3个数，即{49，74，96}, d=22
合并起来就是 {0，49，74，96}，d=22
然而最大子集应该是{0,25,49,96}, d=24
不知道理解的对否？谢谢

【在 h**6 的大作中提到】

: 可以化简一下：
: A[i,m]中选2个数，A[m,j]中选k-1个数
: A[i], A[m], A[j]必然被选中

h*62012-11-09 08:11

14 楼

必须遍历所有的m，然后取最大值。
同楼上larrabee的算法相比，我省略了 p 这个参数。

【在 B***n 的大作中提到】

: 这里的m是任意的都可以吗？还是得遍历所有的m？
: 比如例子
: A[] = {0, 25, 49, 51, 74, 96 }
: 选m=3的话就有问题
: 在A[1,3]={0,25,49}选2个数，即{0，49}， d=49
: 在A[3,6]={49,51,74,96}选k-1=3个数，即{49，74，96}, d=22
: 合并起来就是 {0，49，74，96}，d=22
: 然而最大子集应该是{0,25,49,96}, d=24
: 不知道理解的对否？谢谢

A*r2012-11-09 08:11

15 楼

为了这道题，专门复习了一下dp,并且把两个帖子的回复都仔细研读了一遍，现在来总
结一下吧。
原题：给定M个数字的从1到N的整数数组，找出一个大小为K的子集，这个子集
的半径定义为最小的pair Distance，让找出最大半径的这样的子集。
首先说如果是brute force, 要从M个数中选出K个数，然后计算每个K子集的半径，找到
最大的那个，复杂度为 C(M,K), 算是exponential的了。。
然后很显然这是个optimization problem (maximize the radius),所以可以考虑用DP.
用DP的最重要的就是找到如何从已知的optimal subproblem, 推导出当前的optimal
state. 对于这个题，就是如何从已知的optimal (K-1)元素的子集的，得到含有K元素
的optimal的子集。
在回复很多人都知道这一点，如果没有特殊的约束条件，这两个子集可以完全不一样，
也构不成DP中的subproblem了。所以我们要先sort输入数组，这样保证了每一个pair
distance involving i and previo

【在 w*****k 的大作中提到】