zhaozeyang 10 發表於 May 5, 2011 檢舉 Share 發表於 May 5, 2011 (已編輯) Time Limit: 1000/2000 MS (Java/Others) Memory Limit: 32768/1024 K (Java/Others) Problem DescriptionIn the new year party, everybody will get a "special present".Now it's your turn to get your special present, a lot of presents now putting on the desk, and only one of them will be yours.Each present has a card number on it, and your present's card number will be the one that different from all the others, and you can assume that only one number appear odd times.For example, there are 5 present, and their card numbers are 1, 2, 3, 2, 1.so your present will be the one with the card number of 3, because 3 is the number that different from all the others.InputThe input file will consist of several cases. Each case will be presented by an integer n (1<=n<1000000, and n is odd) at first. Following that, n positive integers will be given in a line, all integers will smaller than 2^31. These numbers indicate the card numbers of the presents.n = 0 ends the input.OutputFor each case, output an integer in a line, which is the card number of your present.Sample Input51 1 3 2 231 2 10 Sample Output32Hint input huge,use scanf to avoid Time Limit Exceeded 題目的意思就大致就是找出出現奇數個的數字,數據很多，普通暴力的那種肯定會超時的。cin不能用，cin比scanf慢很多這個該這麼寫，完全沒頭緒啊 此內容已被編輯, May 5, 2011 ,由 zhaozeyang 鏈接文章 分享到其他網站
j100002ben 10 發表於 May 5, 2011 檢舉 Share 發表於 May 5, 2011 (已編輯) 如果是Java，因為記憶體夠多(題目給的）直接開一個有2^31個元素的small int或是char陣列（假設是s）當flag原本是0，每輸入一個數字（假設是t）就把對應的的元素值反向（就是s[t] = !s[t] ）之後一個for找出是1的就是答案不要去作取餘數，很浪費時間如果是其他程式語言，因為只有1024K可以用，所以上面的方法不能用所以要建立Binary Search Tree，參考：http://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9每讀一個數字進來就先找看看是否存在，如果存在就把他刪掉，如果不存在就把他加進去，最後剩下來的Root就會是答案程式維基百科裡面有，直接用吧XDD如果還有其他更快的方法，我還挺想要知道的說~~ 此內容已被編輯, May 5, 2011 ,由 j100002ben 鏈接文章 分享到其他網站
su_horng 10 發表於 May 7, 2011 檢舉 Share 發表於 May 7, 2011 你漏看了一句最重要的話喔 : "you can assume that only one number appear odd times."這題記憶體限制緊, 比較可能的做法大概是利用xor運算子xor算子有幾個特性: 任何數字只要自己xor偶數次就會變0, 而且做xor運算的先後順序不影響答案所以把題目給的所有數字xor起來就是答案 <- 防捏以這題的限制來說, 可能其他方法都無法通過測試 鏈接文章 分享到其他網站
j100002ben 10 發表於 May 8, 2011 檢舉 Share 發表於 May 8, 2011 你漏看了一句最重要的話喔 : "you can assume that only one number appear odd times."這題記憶體限制緊, 比較可能的做法大概是利用xor運算子xor算子有幾個特性: 任何數字只要自己xor偶數次就會變0, 而且做xor運算的先後順序不影響答案所以把題目給的所有數字xor起來就是答案 <- 防捏以這題的限制來說, 可能其他方法都無法通過測試對吼.....寫普通程式寫久了都忘記XOR了XDDD:P的確，這題用XOR應該是最佳解吧...:p 鏈接文章 分享到其他網站
aalexx 10 發表於 May 25, 2011 檢舉 Share 發表於 May 25, 2011 不懂不懂我知道xor自己會變成零但是那麼多筆資料要如何xor到自己用陣列嗎好像太慢呀 鏈接文章 分享到其他網站
j100002ben 10 發表於 May 25, 2011 檢舉 Share 發表於 May 25, 2011 不懂不懂我知道xor自己會變成零但是那麼多筆資料要如何xor到自己用陣列嗎好像太慢呀不是那個意思啦～～使只要同樣的資料被XOR偶數次就會變成0和什麼時候XOR是沒有關係的換句話說～假設浸來的資料是： a c d e b d a c da XOR c XOR d XOR e XOR b XOR d XOR a XOR c XOR d和 0 XOR b 是一樣的東西所以只要剩下來的資料再 XOR 一次 0 就會是要的數字了 鏈接文章 分享到其他網站
aalexx 10 發表於 June 7, 2011 檢舉 Share 發表於 June 7, 2011 例如說001001011010001011作以下運算001^001=000000^011=011011^010=001001^001=000000^011=011這樣的話最後的結果不是011嗎可是應該是要輸出010吧 鏈接文章 分享到其他網站
j100002ben 10 發表於 June 7, 2011 檢舉 Share 發表於 June 7, 2011 例如說001001011010001011作以下運算001^001=000000^011=011011^010=001001^001=000000^011=011這樣的話最後的結果不是011嗎可是應該是要輸出010吧你的測試資料是錯的啊...只會有「一組奇數個數字」，其他的都會是偶數個你的測試資料010和001各有1個和3個所以結果的011是010 XOR 001的結果:p 鏈接文章 分享到其他網站
Recommended Posts
請登入後來留意見
在登入之後,您才能留意見
立即登入