[ACM ]10125

看板C_and_CPP作者 (UnlimitedMidtetmWorks)時間15年前 (2010/03/07 23:58), 編輯推噓6(6推 0噓 33→)
留言39則, 4人參與, 最新討論串1/1
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 ) ( 未必需要依照此格式，文章條理清楚即可 ) 題號：10125 SumSets 遇到的問題：一直WA，使用他人寫好的程式(上傳已accepted) 跟我的程式作亂數測資的結果比對也沒發現有錯誤 有問題的code： (請善用置底文的標色功能) code:http://www.box.net/shared/do1a3ap3t4 補充說明： 我是先將(a+b) (d-c)的所有可能找出後sorting再找可能解 再將最大解印出 想請各位大大幫個忙，已經de了4個鐘頭了Orz -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.235.177
→
03/08 13:50, , 1F
這題不就sort後跑4層for迴圈就可以解了？ 不拼速度的話
03/08 13:50, 1F
→
03/08 13:50, , 2F
sort可以用algorithm裡的幫你排，code不到60行
03/08 13:50, 2F
→
03/08 13:55, , 3F
03/08 13:55, 3F
→
03/08 14:00, , 4F
這樣做O(n)=n^4=10^12 不會被uva判斷超時嗎?
03/08 14:00, 4F
→
03/08 14:07, , 5F
最壞的情況應該超時，不過沒那種測資，AC 0.264s
03/08 14:07, 5F
→
03/08 14:12, , 6F
請稍等片刻，我試試看你的方式寫code，方法理論上應該OK
03/08 14:12, 6F
推
03/08 14:13, , 7F
INT_MAX...
03/08 14:13, 7F
推
03/08 15:02, , 8F
用 long 不夠存吧
03/08 15:02, 8F
→
03/08 15:36, , 9F
照這方式寫怎麼都TLE，你怎麼判斷fR[0]是最大的d呢？
03/08 15:36, 9F
→
03/08 15:38, , 10F
而且d-c和a+b相等有一個區間，所有都要比對
03/08 15:38, 10F
→
03/08 15:38, , 11F
而不是只比對i和i - 1
03/08 15:38, 11F
→
03/08 16:26, , 12F
try this test case
03/08 16:26, 12F
→
03/08 16:26, , 13F
8
03/08 16:26, 13F
→
03/08 16:26, , 14F
我印出的是fR裡最大的值 比對也是一直比到值不相同為止
03/08 16:26, 14F
→
03/08 16:26, , 15F
0 -1 1 2 -2 9 -4 5
03/08 16:26, 15F
→
03/08 16:28, , 16F
輸出:5
03/08 16:28, 16F
→
03/08 16:29, , 17F
long應該沒有overflow問題 另一個程式只宣告到int
03/08 16:29, 17F
推
03/08 16:39, , 18F
嗯, 那你可能要先了解一下 long 的範圍和 int 的範圍各在哪
03/08 16:39, 18F
→
03/08 16:40, , 19F
他的方法是把所有的 d-c 和 a+b 的 value 都丟到一個 pool
03/08 16:40, 19F
→
03/08 16:40, , 20F
整個排好序之後, 比較相鄰值相等的區塊
03/08 16:40, 20F
→
03/08 16:41, , 21F
如果值相等的區塊裡同時有從 d-c 和 a+b 來的 value 那就是
03/08 16:41, 21F
→
03/08 16:41, , 22F
一個 hit, 把這個 hit 的 d 值存進 FR, 最後找出 max FR
03/08 16:41, 22F
推
03/08 16:44, , 23F
唔.. 我弄錯 long 的範圍了, 第一句當我沒說 XD
03/08 16:44, 23F
→
03/08 16:46, , 24F
可是我蠻好奇為什麼超出範圍，規定是MAX的1/4，
03/08 16:46, 24F
→
03/08 16:47, , 25F
可是我改了long long後這個code就AC了。
03/08 16:47, 25F
→
03/08 16:55, , 26F
所以我加了四行code
03/08 16:55, 26F
→
03/08 16:55, , 27F
我的電腦上用long long也能正常work...只是上傳還是WA= =
03/08 16:55, 27F
→
03/08 16:55, , 28F
if (S[i] > 536870911)
03/08 16:55, 28F
→
03/08 16:56, , 29F
return(-1);
03/08 16:56, 29F
→
03/08 16:57, , 30F
if (S[i] < -536870912)
03/08 16:57, 30F
→
03/08 16:57, , 31F
return(-1);
03/08 16:57, 31F
→
03/08 16:57, , 32F
一樣是AC。不曉得為什麼超出範圍。
03/08 16:57, 32F
推
03/08 16:58, , 33F
用巨集會比較好:INT_MAX、LONG_MAX, 不然他們會哭哭
03/08 16:58, 33F
→
03/08 16:59, , 34F
http://codepad.org/BWTF52CP 這是只改long long的code
03/08 16:59, 34F
→
03/08 16:59, , 35F
可以AC。
03/08 16:59, 35F
→
03/08 17:07, , 36F
看來我找到問題所在了，scanf("%ld", S[i]); 原code改ld
03/08 17:07, 36F
→
03/08 17:07, , 37F
就可以AC了，不需要用long long
03/08 17:07, 37F
→
03/08 17:19, , 38F
感謝樓上幾位大大...我犯傻了 竟然忘記打l...
03/08 17:19, 38F
推
03/08 21:37, , 39F
囧 我也沒看到
03/08 21:37, 39F
‣ 更多 ccs5271 的文章
文章代碼(AID): #1BayqQyU (C_and_CPP)