UVA-10635, Prince and Princes

這題真是魂淡

看起來一副LCS的模樣

殊不知寫LCS會TLE

於是在下很不爭氣的爬了攻略

發現其實是要把他轉成LIS

因為數字不會重複出現

所以把第一個陣列重新編號

定義a[0]=0, a[1]=1......

然後另一個陣列就轉換下去

如果找不到對應就設一個鬼東西表示絕對不會採用

code就不上了  寫得有點醜

[心得]小心LCS

LCS有時候其實並不是LCS

先看看複雜度

如果pq真他媽的大

那他就絕對不是LCS

不管看起來有多像...

關鍵在元素是否重複

[轉貼][整理] 約瑟夫問題

約瑟夫問題

n個人排成一圈
每數到第m個人就剔除，然後繼續數
請問最後剩下的人的編號?

在網路上看到幾種解法
下面是自己整理的心得

一、遞推

踢掉第一個人以後
剩下的人可以重新從零編號
然後從零再一次進行踢人的動作

因此四個人踢掉一人的狀況
其實就是五個人踢掉第二人的狀況
只不過編號需要轉換一下:
"這一輪的第i號(剩k人時)" 是 "上一輪的第(i+m)%(k+1)"

理由是這樣的:
因為每一輪都從0開始數，所以第m號就是下一輪的第0號
因此每一輪依次轉換上去就可以得到任意初始人數下的最終結果

舉個例子，如果m=3(每數三人):
那剩下一人時的第0號 (也只有第0號)
就是剩下二人時的第(0+3)%(k+1) = 1號

二、逆推

總共有n個人，每數第m個人就剔除

所以第k個被剔除的人另一個角度上就是第(k*m)-1號

然後就一圈一圈往上看

看他上一次報數時到底是幾號

當號碼落在 0~n-1 之間時就是答案了

而上一次報數和下一次報數的號碼差

剛好等於那一圈剩下的人數

要逆推回去的話就是

上一圈編號 = 這一圈編號(N) - 上一圈人數

而某一圈剩下的人數為: n-N/m 

以M代表下一圈的編號，N代表這一圈

則 M = N + n - (N/m)

=>

N = (M-n)*m/(m-1)

因此可以做下面編寫:

1 for(ans=k*m-1 ; ans>=n ; ans=(ans-n)*m/(m-1) );

ans最後存的值就是第k個被剔除的人的編號

以上就是對約瑟夫問題的小小研究心得

參考:
http://maskray.me/blog/2013-08-27-josephus-problem-two-log-n-solutions
程式碼是我自己重寫的  不知道到底對不對 改天試一下......