×
解除綁定,重新設定系統帳號的密碼
您的系統帳號 ID:
您的系統帳號:
您的帳號暱稱:
設定新密碼:
設定新密碼:
×
請輸入要加入的「課程代碼」
請向開設課程的使用者索取「課程代碼」
分類題庫
解題動態
排行榜
討論區
競賽區
登入
註冊
發表新討論
解題報告
#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