ck1090148@gl.ck.tp.edu.tw
(北逆)
學校
:
臺北市立建國高級中學
編號 : 162695
來源 : [123.193.62.108]
最後登入時間 ：
2023-02-12 22:38:34
這題很多眉眉角角，有夠靠北，有想法了也未必過。
先講解題想法：
1.區分字串只看「裡面有誰」而不論有幾個同樣的字母，因此可以透過位元運算把字串變成整數。
2.確定兩組轉換過的數字是否互補，請用XOR運算，值得注意的是，若A^B = C，A^C也等於B。
3.同一組CP可能出現很多次，可以使用map，以(1.)轉換過的數字為key, value則是出現次數。
4.承2, 因此找尋互補的方式：以(key^2n-1)為新的key，丟進map就可以知道原本的key的互補cp有幾個。
5.一邊輸入一邊運算，大幅加快執行速度。
然後是我一路上遇到的各種妖魔鬼怪：
1.注意總共有38人，想法(1.)存成整數型態時的大小(238-1)會超過int(231-1), 看到int統統給我換long long。
2.假設討論n個人，兩組互補XOR的結果就會是2n-1(就是1111.......1)，這個數字不要用math裡面的pow(2, n)算，
位元運算是你的好朋友：(1LL << n)-1。
3.注意前一行的1LL，long long後綴，避免溢值，不然明明跑出來了卻是很奇怪的答案。
4.不要用map，map性能比較差啊，我用map最後25%一直跳這個：
系統呼叫了 abort 函式！
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)
改成用unordered_map就AC了。
以上，希望可以幫到跟我一樣快撞牆的人!
題外話，搞那麼久最後寫完只有30行好空虛喔QAQ
這題很多眉眉角角，有夠靠北，有想法了也未必過。
先講解題想法：
1.區分字串只看「裡面有誰」而不論有幾個同樣的字母，因此可以透過位元運算把字串變成整數。
2.確定兩組轉換過的數字是否互補，請用XOR運算，值得注意的是，若A^B = C，A^C也等於B。
3.同一組CP可能出現很多次，可以使用map，以(1.)轉換過的數字為key, value則是出現次數。
4.承2, 因此找尋互補的方式：以(key^2n-1)為新的key，丟進map就可以知道原本的key的互補cp有幾個。
5.一邊輸入一邊運算，大幅加快執行速度。
然後是我一路上遇到的各種妖魔鬼怪：
1.注意總共有38人，想法(1.)存成整數型態時的大小(238-1)會超過int(231-1), 看到int統統給我換long long。
2.假設討論n個人，兩組互補XOR的結果就會是2n-1(就是1111.......1)，這個數字不要用math裡面的pow(2, n)算，
位元運算是你的好朋友：(1LL << n)-1。
3.注意前一行的1LL，long long後綴，避免溢值，不然明明跑出來了卻是很奇怪的答案。
4.不要用map，map性能比較差啊，我用map最後25%一直跳這個：
系統呼叫了 abort 函式！ terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc Aborted (core dumped)
改成用unordered_map就AC了。
以上，希望可以幫到跟我一樣快撞牆的人!
題外話，搞那麼久最後寫完只有30行好空虛喔QAQ
orz