#17730: 解法思路


p3a_owhj (阿普二信)

學校 : 不指定學校
編號 : 39897
來源 : [36.227.79.178]
最後登入時間 :
2024-06-04 22:09:36
c658. 小新的提款卡密碼 -- it's david | From: [218.161.13.235] | 發表日期 : 2019-05-11 23:54

以下是我的解法思路, 用map, set , vector , 沒做 hash_table

 

for q=34~99999 :
    n = q*q
找出 n 各位數的 set< pair<int,int> > sii;

例如 q=5678:n=32239684 則 sii={<2,2>,<3,2>,<4,1>,<6,1>,<8,1>,<9,1>};
                                             即 2個2,2個3,1個4,1個6,1個8,1個9
又 q=5768:n=33269824 及 q=6544:n=42823936 也皆有相同的 位數set

我用 typedef set< pair<int,int> > stype

我的解法是用 map< stype , int > 記錄不同 sii 的出現序
若出現相同的 sii 則另以 vector< vector<int> > ans 串接其 q值
例如:若 5678的出現序為 sn 則 ans[sn].push_back(5678)
而 5768 , 6544 也是同一個 sn 所以三個為同一 ans


先跑完 q=34~99999 扣掉平方有0的 n 建map的 size()共 15255種 不同的 sii值

效率雖不是很好,但少了處理 hash ,仍勉強 AC

 

 
ZeroJudge Forum