作者查詢 / aaaaajack

總覽項目：發文 | 留言 | 暱稱

作者 aaaaajack 在 PTT [ Prob_Solve ] 看板的留言(推文), 共53則

限定看板：Prob_Solve

看板排序：

首頁

尾頁

[問題] totally monotone matrix

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: DJWS - 發表於 2017/01/18 09:10(7年前)

1^F推aaaaajack: 最小值的tiebreaker有定好的話(沒定好大概也不會對) 抓01/18 19:15

2^F→aaaaajack: 每個2x2的子矩陣就可以了吧01/18 19:15

least commom ancestor in general graph

[ Prob_Solve ]11 留言, 推噓總分: +4

作者: DJWS - 發表於 2017/01/05 14:51(7年前)

9^F推aaaaajack: 我覺得點順序還是要符合拓樸排序才合理吧(同SCC內隨意)01/09 15:32

10^F→aaaaajack: 不然假設x可到y但x比y大 y就直接被x吃掉了01/09 15:33

Re: [問題] 可停留的路線安排程式

[ Prob_Solve ]6 留言, 推噓總分: +2

作者: hcsoso - 發表於 2016/12/18 15:38(7年前)

3^F推aaaaajack: 我覺得有問題最短路徑不保證是最佳路徑假設整張數值12/19 00:49

4^F→aaaaajack: 差不多僅有一些值異常小的格子最佳解必然會繞過這些格12/19 00:49

5^F→aaaaajack: 子12/19 00:49

6^F→aaaaajack: 至於何為最佳路徑，在不清楚終點為何的情況下無法保證12/19 00:53

Re: [問題] 可停留的路線安排程式

[ Prob_Solve ]77 留言, 推噓總分: +18

作者: DJWS - 發表於 2016/12/14 08:46(7年前)

20^F推aaaaajack: 枚舉終點把weight改成終點值-原值做最短路徑可以做到12/18 00:36

21^F→aaaaajack: O(n^4 log n)不受天數影響不過我不知道怎麼做到更快12/18 00:36

26^F→aaaaajack: 是邊長沒錯沒注意原題的n是天數12/19 00:51

36^F推aaaaajack: 負值直接忽略，證得終點必為最大值否則改停在最大值12/19 07:49

37^F→aaaaajack: *路徑上最大值12/19 07:49

45^F→aaaaajack: 你可能沒看懂我意思終點值-原值算的就是「虧多少」12/19 09:40

46^F→aaaaajack: 確實算n^2天即可我本來是打算找找看有沒有單調性可以12/19 09:41

47^F→aaaaajack: 利用但情況似乎比我想的複雜12/19 09:42

48^F→aaaaajack: 總之就是已知最後要去哪裡賺就挑虧最少的路徑過去12/19 09:50

49^F→aaaaajack: 天數只影響要挑哪個終點12/19 09:52

57^F推aaaaajack: 抱歉，你說的沒錯，確實有問題12/19 10:37

58^F推aaaaajack: 我誤解你原先天數的疑慮是optimality12/19 10:41

59^F→aaaaajack: 但事實上feasibility就爆了Orz12/19 10:42

66^F→aaaaajack: 一維路就只有一條還不如直接枚舉 Orz12/19 19:19

68^F→aaaaajack: 囧二維simple path有無窮多條啊12/20 09:15

69^F→aaaaajack: 說錯指數多條12/20 09:16

70^F→aaaaajack: 現在問題不就是一維輕鬆線性二維只能平方嗎12/20 09:21

74^F→aaaaajack: 至多算n天就不對了12/20 22:06

75^F→aaaaajack: 就像hcsoso那篇做法的問題直達不會是最賺的12/20 22:07

76^F→aaaaajack: 你可以設一些weight極小的格子強迫蛇行達到n^2/2左右12/20 22:07

77^F→aaaaajack: 天數還是太難處理或許DP O(n^4)真的是最佳解12/20 22:56

[問題] Letter Lock Picking Puzzle

[ Prob_Solve ]13 留言, 推噓總分: +3

作者: FRAXIS - 發表於 2016/11/27 13:31(7年前)

6^F推aaaaajack: 找二分圖是否包含給定大小完全圖似乎是NP-complete12/02 01:08

7^F→aaaaajack: 所以應該N=2就很難做了 (假設字母集跟K很大)12/02 01:09

10^F→aaaaajack: 不過字母集是常數的case可能可以考慮但我還沒有想法12/03 01:29

12^F→aaaaajack: 沒有吧窮舉是c^N ?12/03 18:58

[問題] Maximum Independent Set(Greedy method)

[ Prob_Solve ]11 留言, 推噓總分: 0

作者: cutekid - 發表於 2016/10/16 18:02(7年前)

2^F→aaaaajack: priority queue10/16 20:14

3^F→aaaaajack: 欸不對這樣會跟邊數相關還是n^210/16 20:15

4^F→aaaaajack: 如果E<<V^2的話就是拔點的時候把鄰居degree-1丟進去10/16 20:19

5^F→aaaaajack: 可以做到O(E log V) 我猜可能可以再壓到O(E)10/16 20:19

6^F→aaaaajack: 要比O(E)再低可能就不是很合理啦畢竟圖大小就那樣了10/16 20:20

7^F→aaaaajack: 每個degree建個list(vector) 點丟到list裡10/16 20:33

8^F→aaaaajack: 刪點的時候把鄰居degree-1，丟到他該去的list裡10/16 20:34

9^F→aaaaajack: 維護當前最小degree值刪點頂多-1 所以至多回退V10/16 20:34

10^F→aaaaajack: 每個點只會出現在(移除時degree~原degree)的lsit中10/16 20:35

11^F→aaaaajack: 總數O(E) 所以整體來說應該是O(E)10/16 20:35

[問題] SPOJ VFDIV

[ Prob_Solve ]2 留言, 推噓總分: 0

作者: pttworld - 發表於 2016/09/30 15:26(7年前)

1^F→aaaaajack: 維基百科上有個做法是牛頓估divisor倒數10/12 22:58

2^F→aaaaajack: 然後變成乘法再FFT找quotient 不過我也沒試過10/12 22:59

[問題] 數列問題

[ Prob_Solve ]42 留言, 推噓總分: +13

作者: williamd4112 - 發表於 2015/01/31 17:44(9年前)

11^F→aaaaajack: 先排序一遍找每個人的排位02/01 02:29

12^F→aaaaajack: 然後用fenwick tree倒著作回來應該可以做到O(QlogQ)02/01 02:30

13^F→aaaaajack: 又或者簡單一點用priority_queue維護最小k個數02/01 02:37

14^F→aaaaajack: 怎麼做到O(Q)我就比較沒概念了，一時之間沒想法02/01 02:37

[問題] DFS recursive algorithm

[ Prob_Solve ]12 留言, 推噓總分: +1

作者: jb679123 - 發表於 2014/12/30 01:02(9年前)

9^F→aaaaajack: 現在回好像有點遲XD 總之需要考慮各種edge的特性01/05 23:01

10^F→aaaaajack: forward跟back edge滿足一個是另一個的ancestor01/05 23:02

11^F→aaaaajack: d跟f可以幫助你判斷這件事01/05 23:02

12^F→aaaaajack: 然後pi幫助你判斷他是不是tree edge01/05 23:02

首頁

尾頁