马英九到底有没有绿卡大选吵翻天 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

马英九到底有没有绿卡大选吵翻天

马英九到底有没有绿卡大选吵翻天# Joke - 肚皮舞运动

H*e2011-09-06 07:09

1 楼

两个题目
1.
Given an array of integers, find out number of ways in which you can select
increasing subsequences of length k(k<=n).e.g.array is 1 4 6 2 5 & k=3 then
the answer is : 1 4 5, 1 2 5,1 4 6, 1 2 6,所以总数是4
2.
Given a sorted array of n integers, pick up k elements so that the minimal
difference between consecutive elements is maximized (that is choose the
elements to maximize the quantity min(a[i+1] - a[i]))

d*f2011-09-06 07:09

2 楼

绿绿的智慧真是没有下限的
根据维基揭密网站最近公布的美国外交电文显示，2008年台湾总统大选时，美国驻台官
员曾表示，有关绿卡效力的问题相当复杂，民进党指出，这显示马英九的绿卡仍然有效
，否则美国官员可以直接予以否认。国民党方面则表示，有关绿卡问题早已进行澄清，
民进党是在炒冷饭。
2008年台湾总统大选前夕，有关马英九是否拥有绿卡以及绿卡是否自动失效的问题吵得
沸沸扬扬。3年后，由于维基揭密公布的几则美国外交机密电文，马英九的绿卡问题再
次浮上台面。
根据电文内容，在2008年6月总统大选过后，民进党主席蔡英文与当时的美国在台协会
台北办事处处长杨苏棣会晤，提到有关马英九的绿卡效力问题，杨苏棣的答复是，“一
般说来，有关绿卡效力的问题都是相当复杂的。”
另一封电文显示在大选前，马英九外交顾问冯寄台曾经转交一封马英九信函给杨苏棣，
要求美国公开确认马英九既不是美国公民，也不具有永久居留身份。杨苏棣在电文中表
示，马英九明显对这件事感到紧张，要美国政府尽早说明。
当时与马英九竞选总统的民进党候选人谢长廷表示，他当年也曾经在大选前会晤杨苏棣
，询问有关马英九的绿卡问题。
谢长廷说：“因为我们已经知道(马英九)有绿卡，所以我也把(绿卡)号码告诉杨处长，
我们是用一个方式，说这个档案好像消失了，他说档案不会消失，所以他间接证明是有
。”
谢长廷表示，当时国民党用了很多管道，希望美国证实马英九绿卡已经失效，但是美国
好像拒绝了。
面对民进党的批评，马英九竞选办公室发言人李佳霏表示，马总统在1980年代后期进出
美国，都是使用非移民签证，绿卡已经因为长期不使用，被视为放弃而失效。李佳霏强
调，马英九对此事公开坦荡，希望美国主管机关能够出面澄清。
美国在台协会星期二并没有就维基揭密再次掀起绿卡争议一事发表看法。
与此同时，民进党顾问律师徐国勇引述美国国务院外交事务手册的准则，指马英九绿卡
自动失效的说法是卸责、说谎。
徐国勇说：“它说，观光签证的取得，对于它的永久居留权并不会造成负面的影响，既
然没有影响，马英九硬要扯说它是无效，甚至还要冯寄台给一封信，要求美国政府来做
出绿卡已经失效的回应，美国当然觉得这是非常复杂的，因为这牵涉到台湾的选举。”
台湾外交部发言人章计平则表示，马英九总统曾经多次入、出境美国，都是持非移民签
证。在这部分，根据美国法律规定，所谓的绿卡或永久居留权，就已经失效、不存在。
国民党方面批评民进党再吵绿卡问题，是冷饭热炒。国民党发言人赖素如表示，希望民
进党不要再打乌贼战，还给选民一个高格调的选举。
国民党立法委员吴育升表示，对民进党的作法感到遗憾。
吴育升说：“利用维基揭密来作为台湾内部斗争的工具或者是总统大选的一种手段，我
对于民进党的作法感到遗憾，老狗玩不出新花样，又在旧菜新炒，我觉得民进党没有进
步，反而退步。”
台湾行政院长吴敦义表示，马英九总统多年来都是以中华民国国民身份进出美国，且持
绿卡并没有违法，在实务、法律面都没有问题，绿卡议题应该不会成为选举炒作话题。
不过，台湾东华大学原住民学院教授施正锋表示，维基揭密的电文显示美国政府在这起
事件中的尴尬角色，也凸显了马英九的绿卡问题仍然是台湾选民关注的焦点。
施正锋说：“如果照我目前感觉，两位候选人的差距不大，如果传统思维还没有改变，
我想一定还会有人去吵(这个议题)。在候选人差距不大的情况下，一点点的波动还是会
有影响的。”
民进党立法委员蔡煌榔呼吁马英九尽快到美国在台协会，办理放弃绿卡的手续，让相关
争议落幕。

s*n2011-09-06 07:09

3 楼

第一题：(修订后）
n*k的matrix，m(i,k)表示第i个元素结尾，长度为k的结果个数
m(i,k) = sum{m(j,k-1), where a[j]得O(k*n^2)，有更好的办法么？

s*n2011-09-06 07:09

4 楼

第二题,搞个升序的dequeue, dequeue[0]表示当前k个连续元素最小difference。
每来一个元素diff[i]，把dequeue上所有比diff[i]大的扔掉，如果dequeue[0]=diff[i
-k]则把dequeue[0]也扔掉。

A*u2011-09-06 07:09

5 楼

你的dp水平真不是盖的

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

: 第二题,搞个升序的dequeue, dequeue[0]表示当前k个连续元素最小difference。
: 每来一个元素diff[i]，把dequeue上所有比diff[i]大的扔掉，如果dequeue[0]=diff[i
: -k]则把dequeue[0]也扔掉。

i*d2011-09-06 07:09

6 楼

第二题可以用binary search来做。lo = 0, high = (a[len-1]-a[0])/(k-1)+1
然后对于任意一个Mid，考察是否存在k个数，使得minimum的值大于等于mid。

s*n2011-09-06 07:09

7 楼

给个解法吧，我这抛砖引玉

【在 A**u 的大作中提到】

: 你的dp水平真不是盖的

A*u2011-09-06 07:09

8 楼

这好像不对吧
m(i,k) 不是以第i个元素结尾
m(i,k) 应该是 sum{m(j,k-1),where a[j]
【在 s******n 的大作中提到】

: 给个解法吧，我这抛砖引玉

s*n2011-09-06 07:09

9 楼

恩。不过这样是O(k*n^2)，有更好的做法吗？

【在 A**u 的大作中提到】

: 这好像不对吧
: m(i,k) 不是以第i个元素结尾
: m(i,k) 应该是 sum{m(j,k-1),where a[j]

s*a2011-09-06 07:09

10 楼

第二题好像是GREEDY，不用DP

H*e2011-09-06 07:09

11 楼

我做法跟swanswan一样，只不过M[i,k]定义要改成前i个元素里符合条件的长度为k的
子数组数目。
为啥第一项没有了？ M[i-1,k] 不是分成以a[i]结尾和不以a[i]结尾两种情况吗？

【在 A**u 的大作中提到】

: 这好像不对吧
: m(i,k) 不是以第i个元素结尾
: m(i,k) 应该是 sum{m(j,k-1),where a[j]

H*e2011-09-06 07:09

12 楼

第二题，
定义M[i,k]为以a[i]为结尾的，长度为k的符合条件的，则
M[i,k] = max_over_j( min ( M[j,k-1], a[i] -a[j]) ) , 0帮看看有问题么？

select
then

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

: 两个题目
: 1.
: Given an array of integers, find out number of ways in which you can select
: increasing subsequences of length k(k<=n).e.g.array is 1 4 6 2 5 & k=3 then
: the answer is : 1 4 5, 1 2 5,1 4 6, 1 2 6,所以总数是4
: 2.
: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximized (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))

H*e2011-09-06 07:09

13 楼

怎么greedy呢》

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

: 第二题好像是GREEDY，不用DP

s*n2011-09-06 07:09

14 楼

你这个定义有问题，推不出M[i,k]=sum{M[j,k-1] a[j]
【在 H***e 的大作中提到】

: 我做法跟swanswan一样，只不过M[i,k]定义要改成前i个元素里符合条件的长度为k的
: 子数组数目。
: 为啥第一项没有了？ M[i-1,k] 不是分成以a[i]结尾和不以a[i]结尾两种情况吗？

i*o2011-09-06 07:09

15 楼

第一题:
"where a[j]can be improved to:
"where a[j]And when k is close to n, the complexity is close to O(n^2) instead of
O(n^3
).
How should we describe this in O notion?

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

: 恩。不过这样是O(k*n^2)，有更好的做法吗？

x*32011-09-06 07:09

16 楼

第二题我想是可以用greedy的。我基本的思路是首尾两项肯定是在选的elements中的。
初始化是选择的序列是0,1,2..k-2,n-1（从0开始计）。循环从倒数第二项开始决定他
应该所在的index的位置，直到正数第二项为止。中间的调整的过程有点复杂，可能可
以简化。下面是我随便写的代码。写得蛮差的，欢迎大家测试指正。
$k = 4;
$a = Array(1, 2, 5, 6, 11, 16, 17);
$records = Array();
for ($i = 1; $i < $k - 1; $i++)
{
$record = new Record($a[$i] - $a[$i - 1], $i);
$records[$i - 1] = $record;
}
$records[$k - 2] = new Record($a[count($a) - 1] - $a[$k - 2], count($a) - 1);
for ($last = $k - 2; $last > 0; $last--)
{
for ($i = $records[$last - 1]->index + 1; $i < $records[$last]->index; $
i++)
{
$newDiff = $a[$i] - $a[$records[$last - 1]->index];
$minDiff = PHP_INT_MAX;
$minIndex;
for ($j = 0; $j <= $last - 1; $j++)
{
if ($records[$j]->diff < $minDiff)
{
$minIndex = $j;
$minDiff = $records[$j]->diff;
}
}
$tmp = $a[$records[$last]->index] - $a[$i];
if ($tmp > $minDiff)
{
if ($newDiff > $minDiff)
{
array_splice($records, $last, 0, array(new Record($newDiff,
$i)));
$records[$minIndex + 1]->diff += $records[$minIndex]->diff;
array_splice($records, $minIndex, 1);
$records[$last]->diff = $tmp;
}
else
{
$records[$last - 1]->index = $i;
$records[$last - 1]->diff += $newDiff;
$records[$last]->diff = $tmp;
}
}
}
}
printf("0\n");
foreach ($records as $record) printf("%d\n", $record->index);
class Record
{
public $diff;
public $index;
public function __construct($diff, $index)
{
$this->diff = $diff;
$this->index = $index;
}
}

select
then

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

l*n2011-09-06 07:09

17 楼

why not 2 4 5, 2 4 6....etc..??
if no, then why is 1 2 6 an answer?
1 2 6 is not in subseq order. I don't get the last output for the first
problem.

select
then

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

H*e2011-09-06 07:09

18 楼

sorry typo
已改

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

: why not 2 4 5, 2 4 6....etc..??
: if no, then why is 1 2 6 an answer?
: 1 2 6 is not in subseq order. I don't get the last output for the first
: problem.
:
: select
: then

i*h2011-09-06 07:09

19 楼

首尾两项肯定是在选的elements中的 ==> 这是错误的。
比方说选3个from 2,3,4,6,8,9,
选择2，6，9和3，6，9一样，minimal difference between consecutive elements
都是3.

【在 x********3 的大作中提到】

: 第二题我想是可以用greedy的。我基本的思路是首尾两项肯定是在选的elements中的。
: 初始化是选择的序列是0,1,2..k-2,n-1（从0开始计）。循环从倒数第二项开始决定他
: 应该所在的index的位置，直到正数第二项为止。中间的调整的过程有点复杂，可能可
: 以简化。下面是我随便写的代码。写得蛮差的，欢迎大家测试指正。
: : $k = 4;
: $a = Array(1, 2, 5, 6, 11, 16, 17);
: $records = Array();
: for ($i = 1; $i < $k - 1; $i++)
: {

c*e2011-09-06 07:09

20 楼

Is there a final conclusion for 1?

select
then

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

x*32011-09-06 07:09

21 楼

虽然这两个是一样的，但是你还是可以选择2，6，9，不是？题目只是说让你选择k个
elements就可以了。

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

: 首尾两项肯定是在选的elements中的 ==> 这是错误的。
: 比方说选3个from 2,3,4,6,8,9,
: 选择2，6，9和3，6，9一样，minimal difference between consecutive elements
: 都是3.

H*e2011-09-06 07:09

22 楼

我说的是你修改前的
用我的定义是有第二项的，也就是你删除的。
其实两个定义很象，复杂度也一样。

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

: 你这个定义有问题，推不出M[i,k]=sum{M[j,k-1] a[j]

H*e2011-09-06 07:09

23 楼

编了下method 1(swanswan说的 ) and method 2(我说的）,
没太狂调。
/*
* Given an array of integers, find out number of ways in which you can
* select increasing subsequences of length K(K<=n).e.g.array is 1 4 6 2
5 &
* K=3 then the answer is : 1 4 5, 1 2 5,1 4 6, so total is 3
*/
// define M[i,k] is the # of k-length sequences that ends at i, i.e.
that sunseq ends at i.
public int numOfIncreasingSubSeq(int[] data, int K) {
// boundary
if (data == null || data.length == 0) {
return 0;
}
int[][] M = new int[data.length][K + 1];
// initialization
for (int t = 0; t < data.length; t++) {
for (int f = 0; f <= K; f++) {
M[t][f] = 0;
if (f == 1) {
M[t][f] = 1;
}
}
}
for (int i = 1; i < data.length; i++) {
for (int k = 2; k <= K; k++) {
int sum = 0;
for (int q = 0; q < i; q++) {
if (data[q] < data[i]) {
sum = sum + M[q][k - 1];
}
}
M[i][k] = sum;
}
}
int result = 0;
for (int p = 0; p < data.length; p++) {
result = result + M[p][K];
}
return result;
}
//method 2
// define M[i,k] is the # of length-k sub sequences within a sunstring
// ending at i(the increasing subseq not necessarily ends at i)
public int numOfIncreasingSubSeq2(int[] data, int K) {
// boundary
if (data == null || data.length == 0) {
return 0;
}
int[][] M = new int[data.length][K + 1];
// initialization
for (int t = 0; t < data.length; t++) {
for (int f = 0; f <= K; f++) {
M[t][f] = 0;
if (f == 1) {
M[t][f] = t + 1;
}
}
}
for (int i = 1; i < data.length; i++) {
for (int k = 2; k <= K; k++) {
if (k > i + 1) {
continue;
}
int sum = 0;
//the result comes from two parts: the subseq ends at i, or
not;
for (int b = 0; b < i; b++) {
sum = sum + M[b][k];
}
for (int q = 0; q < i; q++) {
if (data[q] < data[i]) {
sum = sum + M[q][k - 1];
}
}
M[i][k] = sum;
}
}
return M[data.length - 1][K];
}

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

: Is there a final conclusion for 1?
:
: select
: then