#26830: ［Python］可以使用itertools.product建表。附加：通用2^q取餘數加速的想法(使用 & 跟 <<)
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
一、建表做法
這題可以建表，product()有兩個參數，第一個是你要重複產生的東西，第二個是repeat，看你要每個位子重複幾次，product可以類比雙重迴圈，詳細可以參考官方文件，解釋得很清楚
https://docs.python.org/3/library/itertools.html#itertools.product
而這題用到的技巧與官方範例非常類似，寫起來大概可以長這樣
p_table = [
[int(''.join(x)) for x in product('12', repeat=k)]
for k in range(1, 18)
]
__________
二、 2^q次取餘數加速方法
首先，要製作2的q次方，加速的第一步就可以把次方寫成 1<<q，之後再 k % (1<<q)，但這個方法還是要用到 ［%］。
有另外一個作法是使用&，餘數設定為(1<<q) -1， 也就是 k & ((1<<q) -1)
(1<<q) -1 會產生類似 0b 1111...111 的東西，取餘數就是大於 餘數的東西都不見，那就保留 2進位 q個1 就可以了。
類似像1234 %100 就直接寫 34
__________
三、 搜尋的方法
我自己是用線性搜尋，也就是寫個迴圈慢慢搜尋。
比較不同的是，當初在建表的時候是已經排序過的list，因此可以分別從兩端尋找min、max。
我會先找small，如果small沒找到就不用浪費力氣找max，因為已經全部遍歷一遍了，可以直接 impossible。
找到small之後，使用reversed(p_table)可以從右端尋找max
如果min == max只輸出一個即可
__________
如果有其他不同的作法，歡迎大家寫寫解題報告分享呦 :D
#26831: Re:［Python］可以使用itertools.product建表。附加：通用2^q取餘數加速的想法(使用 & 跟 <<)
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
一、建表做法
這題可以建表，product()有兩個參數，第一個是你要重複產生的東西，第二個是repeat，看你要每個位子重複幾次，product可以類比雙重迴圈，詳細可以參考官方文件，解釋得很清楚
https://docs.python.org/3/library/itertools.html#itertools.product
而這題用到的技巧與官方範例非常類似，寫起來大概可以長這樣
p_table = [
[int(''.join(x)) for x in product('12', repeat=k)]
for k in range(1, 18)
]
__________
二、 2^q次取餘數加速方法
首先，要製作2的q次方，加速的第一步就可以把次方寫成 1<<q，之後再 k % (1<<q)，但這個方法還是要用到 ［%］。
有另外一個作法是使用&，餘數設定為(1<<q) -1， 也就是 k & ((1<<q) -1)
(1<<q) -1 會產生類似 0b 1111...111 的東西，取餘數就是大於 餘數的東西都不見，那就保留 2進位 q個1 就可以了。
類似像1234 %100 就直接寫 34
__________
三、 搜尋的方法
我自己是用線性搜尋，也就是寫個迴圈慢慢搜尋。
比較不同的是，當初在建表的時候是已經排序過的list，因此可以分別從兩端尋找min、max。
我會先找small，如果small沒找到就不用浪費力氣找max，因為已經全部遍歷一遍了，可以直接 impossible。
找到small之後，使用reversed(p_table)可以從右端尋找max
如果min == max只輸出一個即可
__________
如果有其他不同的作法，歡迎大家寫寫解題報告分享呦 :D
#26832: Re:［Python］可以使用itertools.product建表。附加：通用2^q取餘數加速的想法(使用 & 跟 <<)
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
一、建表做法
這題可以建表，product()有兩個參數，第一個是你要重複產生的東西，第二個是repeat，看你要每個位子重複幾次，product可以類比雙重迴圈，詳細可以參考官方文件，解釋得很清楚
https://docs.python.org/3/library/itertools.html#itertools.product
而這題用到的技巧與官方範例非常類似，寫起來大概可以長這樣
p_table = [
[int(''.join(x)) for x in product('12', repeat=k)]
for k in range(1, 18)
]
__________
二、 2^q次取餘數加速方法
首先，要製作2的q次方，加速的第一步就可以把次方寫成 1<<q，之後再 k % (1<<q)，但這個方法還是要用到 ［%］。
有另外一個作法是使用&，餘數設定為(1<<q) -1， 也就是 k & ((1<<q) -1)
(1<<q) -1 會產生類似 0b 1111...111 的東西，取餘數就是大於 餘數的東西都不見，那就保留 2進位 q個1 就可以了。
類似像1234 %100 就直接寫 34
__________
三、 搜尋的方法
我自己是用線性搜尋，也就是寫個迴圈慢慢搜尋。
比較不同的是，當初在建表的時候是已經排序過的list，因此可以分別從兩端尋找min、max。
我會先找small，如果small沒找到就不用浪費力氣找max，因為已經全部遍歷一遍了，可以直接 impossible。
找到small之後，使用reversed(p_table)可以從右端尋找max
如果min == max只輸出一個即可
__________
如果有其他不同的作法，歡迎大家寫寫解題報告分享呦 :D
#26833: Re:［Python］可以使用itertools.product建表。附加：通用2^q取餘數加速的想法(使用 & 跟 <<)
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
一、建表做法
這題可以建表，product()有兩個參數，第一個是你要重複產生的東西，第二個是repeat，看你要每個位子重複幾次，product可以類比雙重迴圈，詳細可以參考官方文件，解釋得很清楚
https://docs.python.org/3/library/itertools.html#itertools.product
而這題用到的技巧與官方範例非常類似，寫起來大概可以長這樣
p_table = [
[int(''.join(x)) for x in product('12', repeat=k)]
for k in range(1, 18)
]
二、 2^q次取餘數加速方法
- 首先，要製作2的q次方，加速的第一步就可以把次方寫成 1<<q，
之後再 k % (1<<q)，但這個方法還是要用到 ［%］。 - 有另外一個作法是使用&，餘數設定為(1<<q) -1， 也就是 k & ((1<<q) -1)
- (1<<q) -1 會產生類似 0b 1111…111 的東西，取餘數就是大於 餘數的東西都不見，
那就保留 2進位 q個1 就可以了。 - 類似像1234 %100 就直接寫 34
三、 搜尋的方法
- 我自己是用線性搜尋，也就是寫個迴圈慢慢搜尋。
- 比較不同的是，當初在建表的時候是已經排序過的list，因此可以分別從兩端尋找min、max。
- 我會先找small，如果small沒找到就不用浪費力氣找max，因為已經全部遍歷一遍了，可以直接 impossible。
- 找到small之後，使用reversed(p_table)可以從右端尋找max
- 如果min == max只輸出一個即可
如果有其他不同的作法，歡迎大家寫寫解題報告分享呦 :D
ZeroJudge Forum