作者查詢 / walker2009
作者 walker2009 在 PTT [ Prob_Solve ] 看板的留言(推文), 共50則
限定看板：Prob_Solve
看板排序：
全部C_and_CPP423SuperStarAve175Beauty112StupidClown90Prob_Solve50Stock48Soft_Job44Android39biker19Gossiping18NTHU_STAT9413Japan_Travel10Jay9Broad_Band8MobileComm8LIU-CHEN7SayLove7FCU_EE97A6FCU_EE97B6Gradol6joke6NDMC-PH276AndroidDev5DYU5KS97-3105sex5TA_AN5Tech_Job5YiGo3115YZU_CN99A5AION4ASIA-uni4Butterfly4FLAT_CLUB4HSNU_9484KTV4Master_D4NCCU08_JAPAN4NTPU-STAT954SSSH-16th-Fk4TCFSHvolley4Bunco3CSMU-D883CTSH963013CYSH97Y3183Facebook3FJU-Family3give3Hate3HSNU_11433iOS3MCU_Talk3NCCU08_Ethno3NCKU_EARTH983NCUFingrad033NDHU-His1003NDMC-D623NTUBIME-1023NTUE-DC993STDM-97-303B3USC3Vocal3ASHS-94sin2BCC_Midnight2Bilk2CCU_ACCGS982Cheer2ck_17_3012cksh84th3222cksh85th3012CodeJob2CPU_7712CSMU-D-SC2CSMU-D972CSMU-HSA962CSMUdancepub2CSU2CYCU_ICE90AB2EEBaseball2FJU-STAT95B2GuessX32HCHS603122HCU2HSNU_10612HSNU_10632HSNU_10982HSNU_11422ILSH-913112ILSH_923122Inference2Key_Mou_Pad2KHCHS_TALK2KS92-3192KS95-3022KS96-3052Little-Games2LTSH-963112NCCU02_Korea2NCHU-FS1002NCHU-Stat972NCU97ME-B2NCUECON962NDMC-N572NDMC-PH232NDU-Talk2NTHU-EE-CAPT2NTOU-AQUA982NTUBSE-B-972NTUEE_Lab4262NTUmed912NTUot972NTUST-ECE2NTUST-EE-B932NTUST-EE-B962NUK_EE100A2NUTN_MS992NUU-EE-97A2Orzhong97cl2pccu_physics2PCSH96_3062PushDoll2SSSH-09th1142STDM-93-3032SuperIdol2Supermission2TigerBlue2TKU-IE942TTU-talk2TTU-Transfer2Viator94Ding2WarHammer2WuLing50-3022YuanLi3042Anti-ramp1AntiVirus1AOSO_Lab1ArabicBasket1ASHS-95RN1B98303XXX1BigShiLin1CCJH-88g-3141CCU_EE961CGU_EE981CH12th3081CHSH-3191CJCU1CJCU_HCA981ck59th3061ck61st3091ck61st3121ck61st3261CKCB1cksh84th3121cksh85th3071cksh85th3101cksh85th3171cksh85th3191CMS_97_S3F1CMU_Talk1coincidence1CPSHS1CPU_FC7611CPU_FS7411CS95Lien1CSHS57th3141CSMU-D981CSMU-HSA951CSMU-HSA971CTSH963021CTSH97EXP1CTSH98EXP1CYCU_Talk1Deserts1DIABLO1ENG_BASE1FacebookBM1facelift1Falcom1Fallinlove1FCU-EES1FCU-PF20061FCU-TTEM93A1FCU_DOP_SB1FCU_MOT1FCUMCAE-SB1FJU-ACCR941FJU-EE-2006A1FJU-EE-COMM1FJU-EE-VLSI1FJU-Stat95A1FJU-Stat96A1FJU_Chiayun1FJU_HA-club1FJU_JCS111FJU_N96b1FJU_SW_SBMan1Geotecheng961GIEE_981GIEE_BASKET1guitar1haoenjiajia1HC-th11-1121hc3141HCHS543021HCHS593051HLHS_10thU1Hsinchu1HSNU_10101HSNU_10651HSNU_10661HSNU_10911HSNU_11061HSNU_11071HSNU_11121HSNU_11171HSNU_11241HSNU_11261HSNU_11461HSNU_11501HSNU_11701HSNU_8751HSNU_NCCU1ILSH-983051image1ISU_CS_93A1kavalan081KGS_Guitar1KHCHS-93-3061KHCHS-93-3091Kids_Sucker1KOF1KOU1KS92-3131KS92-3161KS93-3201KS94-3081KS94-3181KS95-3141KS96-2021KS96-3111KS96-3141KS96-3181KS97-2161KS97-3161KS97-3181KS98-3121KUAS_5890311LD_IM93-21LifeSci_951LineageII1liuyifei1Loan1LOVE-EDDY1LTK1MCUBT97_21MINGDAO1movie1NAOE-861NCCU04_TUR1NCCU06_BA1NCCU07_ETHNO1NCCU07_STGRA1NCCU_DANCE1NCHU-AGR061NCHU-AGR071NCHU-CE-421NCHU-MKT991NCHU_AMpower1NCHUS1NCKU_BMSOFT1NCNUEM1NCUECON971NCYU_BE_96b1NCYU_Fst_991NDHU-Ch1011NDHU-His1021NDHU-His961NDHU_ACC_9th1NDMC-P921NDMC-ROCK1NEHS19th41NFU1NIU-ECE92b1NIU-ECE94b1NKFUST-CCE901NKJH_29_3131NPTU_CaC1NSYSU_math1NTCU-SPE92A1NTHU-MSE111NTHUTL961NTNU_Lin_961NTPU-ECONM961NTPU-STAT961NTU-Karate1NTUBIME-1001NTUE-CS1021NTUE-CS991NTUE-EPC-971NTUE-ME991NTUE_NSE1001NTUE_Nse1011NTUE_Nse1021NTUE_Nse961NTUEE_LAB2061NTUEE_LAB5061NTUEOE_R4021NTUGIEE_AMTG1NTUGIEE_EDA1NTUHorti961NTUphy981NTUPP-871NTUST-EE-A971NTUST_ME1NTUT_EE493A1NTUT_IPET4951NUK_AC1001NUU-EO-97A1NUU_CLL1NUU_Electric1NYUST97_IEM1NYUST_EE98A1OIT_main1ONE_PIECE1pal1PCSH_94_3101PHI_Baseball1Physics1PSWO3rd1PttLifeLaw1Sangokumusou1Scout1SCU_ACCM951SCU_ACCM971SCU_Chin96C1SCU_Law101D1SCU_Talk1scutran_city1Seiya1share1SSSH-10th3121SSSH-16th3131SSSH_17th3141Stephen1StraightMH1STU1TaichungBun1TallClub1TCFSH67TH101tcfsh69th3041TFSHS65th3151TFSHS66th3191TFSHS67th3161TFSHS67th3211TFSHS68th3161TFSHS69th3071TFSHS69th3181THU-HIS971TKU_EW94B1TNFSH96121TNFSH98th1TodaErika1Touhou1transgender1TSH96_SM1TTSH12th3091TTU-AFL1TTU-AMath1TTU-EE991UFO1UKN1Whitney1WuLing50-3031WuLing50-3171XiangSheng1YHSH96011YoungDotx31YP95-3121Yup01-061YZU_EE96B1ZLSH1ZQ-Physics1<< 收起看板(382)
首頁
上一頁
1
下一頁
尾頁
8F推:嗯嗯@@ 是要找 suhorng大說的那個06/09 13:04
9F→:yau大的作法看起來是 O(nm)~06/09 13:18
10F→:我不確定有 linear time 的解啦XD 只是一開始看到06/09 13:19
11F→:這問題, 看起來很簡單, 我跟幾個朋友都覺得應該可以06/09 13:19
12F→:但後來卻都想不出 linear time 的解, 因此想說問看看06/09 13:19
13F→:有沒有人處理過類似問題, 或是有關鍵字可以提供查詢@@06/09 13:19
28F推:嗯@@ 我有想過 suffix tree, 但最後還是會轉回06/09 23:33
29F→:don't care matching, 掉到 O(n log m)06/09 23:33
43F推:可以這麼想, 因為我只 care X 這個 character06/12 00:44
44F→:所以我把其他 character 都換成 O 也沒關係,不影響答案06/12 00:45
45F→:因此這個問題可以想成只有 2 種 character06/12 00:45
1F推:感謝 t大~ 參悟中!06/08 13:29
2F推:這樣省到的只有尾巴的長度為 m 的那一小段06/08 13:32
4F→:痾...不對...我想說的是...這個做法好像不太對@@06/08 13:33
5F→:XD06/08 13:33
6F→:真的耶...06/08 13:33
8F→:第一個 X 可以 cover 到的範圍之內, 也是需要考慮06/08 13:35
9F→:pattern 其他 X 的位置, 因為他們的 shift 會導致06/08 13:35
10F→: pattern 的起始點不一樣06/08 13:36
11F→:oh... 我大概知道我語病在哪了... 可能又要改題目了QQ06/08 13:36
12F推:我要的是...pattern在 shift 到哪一個位置時, 會有XX對06/08 13:43
13F→:也就是所有 shift 的值06/08 13:43
14F→:我稍微改一下題目了...Q_Q 這樣還有語病嗎06/08 13:43
15F→:嗯嗯 所有配對成功的 shift~06/08 14:09
16F→:一般而言是不能超過,但是允許超過也無所謂~不影響big O06/08 14:09
17F→:嗯~ 我要的是不允許超過的~06/08 17:17
18F→:就是要 pattern 可以每個位置都對到 text 的~ 不能凸出06/08 17:18
1F→:題外話~ 覺得如果 ptt 多個'演算法'版還不錯耶 ~_~06/08 12:47
3F→:XD 我轉過去試試看~ 謝謝06/08 12:52
8F→:只要任意一個位置有 X 對到就可以~ 不用全部對到~06/08 13:01
10F→:!!!!!!!!!!!!!!!! (期待中)(興奮)06/08 13:24
1F推:喔喔喔!!! k大懂我的點XDD 原來這部份用歸納法比較好證04/23 04:20
2F→:感謝感謝, 心裡的大石頭總算放下了XDDD04/23 04:21
1F推:感謝回應! 乍看之下還不太能理解...待我思考幾分鐘先04/20 18:28
2F→:還附上證明了 Orz 實在太麻煩大大了04/20 18:29
4F推:照這演算法下去coding 程式已經AC...但小弟資質駑鈍04/20 19:50
5F→:還在思考為什麼這樣會是正確的04/20 19:50
6F→:而且這作法好像是 greedy...XDDD 所以根本不是 DP04/20 19:51
7F→:至少有一最佳解是載重量由小到大這個我可以理解了04/20 19:53
8F→:但為什麼在超過當前載重量時是拿上面最重的而不是其他04/20 19:53
9F→:關於這點還在想辦法證明中 囧rz04/20 19:54
10F推:應該是說 要怎麼確定拿掉的箱子不會在最佳解裡04/20 20:09
11F推:Orz太感謝了!有些地方還要再思考一會!但大方向都知道了04/20 21:51
12F→:馬上去wiki一下什麼是strongly NP-Hard XDDD 學藝不精04/20 21:52
13F推:C_and_Cpp 版有大大回文了! greedy解似乎不對,好像要DP04/21 00:53
2F→:喔喔喔喔! 3q04/20 14:21
6F→:XD04/20 18:04
7F→:以最下面那個箱子而言 的確上面感覺像是 0-1背包問題04/20 18:05
8F→:但以第二個箱子而言 上面又是另外一個 0-1背包問題04/20 18:05
9F→:提供了我一個思考方向 感恩!04/20 18:06
首頁
上一頁
1
下一頁
尾頁