征求下意见：关于先trap独生女小猫 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

征求下意见：关于先trap独生女小猫

征求下意见：关于先trap独生女小猫# pets - 心有所宠

p*22011-07-01 07:07

1 楼

两个整数1－n的permutation, S和T
每次可以进行一种操作，把S最后一个数字拿出来放在S的任意一个位置。
问通过这种操作把S转变为T的最少操作数。
例如
3 2 1
1 2 3
ans:2
1 2 3 4 5
1 5 2 3 4
ans:1
1 5 2 3 4
1 2 3 4 5
ans:3
1<=n<=2*10^5, n很大，所以基本需要O(n)的复杂度

t*u2011-07-01 07:07

2 楼

同事突然提了一句，说如果我逮住小猫，做了手术，他考虑养小猫……哦，outdoor的
。我想，总比没人家好。不过前提是，小猫得跟人亲。
不过这也remind我的担忧了，就是小猫大了就更不容易tame了，所以她现在能自己吃猫
粮了，肯定可以提前带走了。
但是，怎么才能先trap小猫呢？要是trap母女，是不是一般都会先把大猫trap住了？要
是都能trap了也行，就怕先逮住大猫，小猫被吓跑了，出事。
另外，要是唯一的孩子被带走了，大猫会不会很伤心啊？我将心比心……

w*x2011-07-01 07:07

3 楼

顶兔爷

Z*i2011-07-01 07:07

4 楼

小猫需要SOCIAL才能被收养
大概几周了？
通常8周以上难SOCIAL了。。。。

j*n2011-07-01 07:07

5 楼

2爷你自己都能出题了？牛翻天了。

t*u2011-07-01 07:07

6 楼

啊，这么小就不行了！
那完了
小猫都会吃干粮了……

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

: 小猫需要SOCIAL才能被收养
: 大概几周了？
: 通常8周以上难SOCIAL了。。。。

C*U2011-07-01 07:07

7 楼

为什么第一个例子答案是2

两个整数1－n的permutation, S和T每次可以进行一种操作，把S最后一个数字拿出来放
在S的任意一个位置。问通过这种操作把S转变为T的最少操作数。例如3 2 11 2 ......
..
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

【在 p*****2 的大作中提到】

: 两个整数1－n的permutation, S和T
: 每次可以进行一种操作，把S最后一个数字拿出来放在S的任意一个位置。
: 问通过这种操作把S转变为T的最少操作数。
: 例如
: 3 2 1
: 1 2 3
: ans:2
: 1 2 3 4 5
: 1 5 2 3 4
: ans:1

v*e2011-07-01 07:07

8 楼

12周甚至16周都没问题

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

: 小猫需要SOCIAL才能被收养
: 大概几周了？
: 通常8周以上难SOCIAL了。。。。

w*x2011-07-01 07:07

9 楼

n -最长公共子序列

f*y2011-07-01 07:07

10 楼

alley cat allies上说小于8周最好和妈妈在一起，最理想的socialize的时间是小于12周

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

: 12周甚至16周都没问题

j*e2011-07-01 07:07

11 楼

不对吧，这样第3个例子的答案就是2，而不是3了。
最长公共子序列是234

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

: n -最长公共子序列

y*u2011-07-01 07:07

12 楼

小猫比较傻，很好trap，
最近几次的经验告诉我，
小猫也能踩的动trap，
赶紧去抓吧，
再晚就来不及了
小猫抓了直接让你同事带走
等大点再kc

w*x2011-07-01 07:07

13 楼

哦,只能是最后一个

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

: 不对吧，这样第3个例子的答案就是2，而不是3了。
: 最长公共子序列是234

t*u2011-07-01 07:07

14 楼

下trap就是不知道是不是应该借两个来？一起上
可是，抓住了大猫怎么办？
小猫其实我可以直接交到shelter，让他们kc，打针，然后送出去领养
大猫肯定不行。大猫属于feral cat，很多vet根本都不接受的
怕逮住大猫没逮住小猫，一个是不好处理大猫，一个是大猫不在了，小猫可怎么办？

j*e2011-07-01 07:07

15 楼

这个算法呢？
从左往右扫描S，对S的第一个数a，从T开始扫，直到T里面碰到a，记下T
里的位置Pa，那么至少需要(Pa-1）次操作。然后取S里的第二个数b,从
T的Pa+1位置继续找b，找到位置Pb后，(Pb-2)是至少的操作数。如此继续，
直到T为空。
int scan(int S[], int T[], int N) {
int p = 0;
int max = 0;
if(!S || !T) return 0;
for(int i=0; iwhile(p < N && T[p] != S[i])
p++;
if(p == N) {
break;
}
max = p - i;
p++;
}
return max;
}

【在 p*****2 的大作中提到】

Z*i2011-07-01 07:07

16 楼

估计还是得看猫
我这边RESCUE的主席说过了8周就比较困难了

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

: 12周甚至16周都没问题

h*62011-07-01 07:07

17 楼

第一个数列左起最多连续前x项是第二个数列的子序列，这x项可以保留，因此需要移动
n-x次。

f*y2011-07-01 07:07

18 楼

我上回给你的信里提到的另一个组织http://www.thecatscradle.net/about.htm
他家网页上写着服务包括绝育帮助。你要不打电话说明一下情况，问问他们是不是有低
收费甚至免费的给流浪猫的绝育的地方。大猫绝育后恢复了就放归，恢复很快的。我看
我们这里的一般都是第二天就放归了，快的当天放归的都有。小猫如果吃猫粮了就没问
题，不会饿坏的。

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

: 下trap就是不知道是不是应该借两个来？一起上
: 可是，抓住了大猫怎么办？
: 小猫其实我可以直接交到shelter，让他们kc，打针，然后送出去领养
: 大猫肯定不行。大猫属于feral cat，很多vet根本都不接受的
: 怕逮住大猫没逮住小猫，一个是不好处理大猫，一个是大猫不在了，小猫可怎么办？

p*22011-07-01 07:07

19 楼

复杂度什么样子的？

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

: 第一个数列左起最多连续前x项是第二个数列的子序列，这x项可以保留，因此需要移动
: n-x次。

p*22011-07-01 07:07

20 楼

复杂度如何呢？

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

: 这个算法呢？
: 从左往右扫描S，对S的第一个数a，从T开始扫，直到T里面碰到a，记下T
: 里的位置Pa，那么至少需要(Pa-1）次操作。然后取S里的第二个数b,从
: T的Pa+1位置继续找b，找到位置Pb后，(Pb-2)是至少的操作数。如此继续，
: 直到T为空。
: int scan(int S[], int T[], int N) {
: int p = 0;
: int max = 0;
: if(!S || !T) return 0;
: for(int i=0; i

p*22011-07-01 07:07

21 楼

..
3 2 1
变为 1 3 2
变为 1 2 3
所以是两次

【在 C***U 的大作中提到】

: 为什么第一个例子答案是2
:
: 两个整数1－n的permutation, S和T每次可以进行一种操作，把S最后一个数字拿出来放
: 在S的任意一个位置。问通过这种操作把S转变为T的最少操作数。例如3 2 11 2 ......
: ..
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

j*e2011-07-01 07:07

22 楼

O(N)吧，han6和我的好像是相同的算法

【在 p*****2 的大作中提到】

:
: ..
: 3 2 1
: 变为 1 3 2
: 变为 1 2 3
: 所以是两次

p*22011-07-01 07:07

23 楼

好像O(n), 我做一下。

【在 p*****2 的大作中提到】

:
: ..
: 3 2 1
: 变为 1 3 2
: 变为 1 2 3
: 所以是两次

p*22011-07-01 07:07

24 楼

膜拜两位大牛。是对的。
n=int(raw_input())
l1=map(int,raw_input().split())
l2=map(int,raw_input().split())
i=0
j=0
while jif l1[i]==l2[j]:
i+=1
j+=1
else:
j+=1
print n-i

w*x2011-07-01 07:07

25 楼

这个怎么证明啊

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

: 第一个数列左起最多连续前x项是第二个数列的子序列，这x项可以保留，因此需要移动
: n-x次。