把假日沒寫出來的34寫一寫 ：（ 3 dp這列過去的那列的dp 又是輪轉位移 不相鄰有點像搶房子 這種資料結構比較複雜的 我都寫到頭腦燒壞：（ 原本用vector+hashmap 1560ms 後來用offset改array有快一點 924ms using ll = long long; class Solution { public: int countWinningSequences(string s) { // F > E > W > F vector<vector<int>> dir = { {1, 2}, {0, 2}, {0, 1} }; vector<vector<int>> add = { {0, -1, 1}, {1, 0, -1}, {-1, 1, 0} }; // for bob int m = 1e9 + 7; int len = s.length(); //cnt range: -1000 to 1000 int offset = 1000; int dp[1000][3][2002] = {{{-1}}}; //vector<vector<unordered_map<int, int>>> dp(len, vector<unordered_map<int, int>>(3)); //dp for Bob's sequence, bob's point //dp[i][0] = F, dp[i][1] = E, dp[i][2] = W //map< key = point , cnt > vector<int> mod; if(s[0] == 'F'){ mod = add[0]; } else if(s[0] == 'E'){ mod = add[1]; } else{//'W mod = add[2]; } dp[0][0][mod[0] + offset]++; dp[0][1][mod[1] + offset]++; dp[0][2][mod[2] + offset]++; for(int i = 1; i < len; i++){ char c = s[i]; if(c == 'F'){ mod = add[0]; } else if(c == 'E'){ mod = add[1]; } else{ // c == 'W' mod = add[2]; } //to dp[i-1] for(int last = 0; last < 3; last++){ for(int point = offset - (len - 1 - i); point <= i + offset ; point++){ if(dp[i-1][last][point] == -1) continue; for(int next: dir[last]){ if(dp[i][next][(point + mod[next])] == -1) dp[i][next][(point + mod[next])] = dp[i-1][last][point]; else{ ll cnt = dp[i][next][(point + mod[next])] + dp[i-1][last][point]; cnt %= m; dp[i][next][(point+ mod[next])] = cnt; } } } } } ll res = 0; for(int few = 0; few < 3; few++){ for(int point = offset + 1; point <= 2000 ; point++){ if(dp[len-1][few][point] > 0) res += dp[len-1][few][point]; res %= m; } } return res; } }; 4. 想要他照cnt, num排序 但又要用num find 再 modify 一開始用pq兜不出來 想一想發現 我想要二分搜又maxheap 那不就是treap嗎 雖然感覺有夠不平衡 但我試著建樹發現 我不知道怎麼維護前x個== 每次都找一遍也太白癡了 最後情不得已改成map排序 對每個num記他的position (iterator) 然後發現沃草multimap只會排key 不會排後面的value 再改成set== 是要多忙 然後還卡long long 沒必要吧這個 944ms using ll = long long; class Solution { public: //multimap<int, int> outX; //multimap<int, int> Xsum; set<pair<int, int>> outX; // <cnt, num> nums not in Xsum unordered_map<int, std::set<pair<int, int>>::iterator> idout; // <num, it of out> set<pair<int, int>> Xsum; // <cnt, num> unordered_map<int, std::set<pair<int, int>>::iterator> idx; // <num, it of Xsum> ll sum ; int coda; vector<long long> findXSum(vector<int>& nums, int k, int x) { int n = nums.size(); sum = 0; coda = x; for(int i = 0; i < k; i++){ int num = nums[i]; if(idx.count(num)){ to_X(num); } // num not in Xsum else if(coda > 0){ if(outX.size() == 0){ to_X(num); } else { to_out(num); out_to_X(); } } else{ // x = 0, Xsum full // insert outX to_out(num); // put outX.rbegin() into Xsum, idx out_to_X(); // put Xsum.begin() into outX, idout X_to_out(); } } vector<ll> res; res.push_back(sum); for(int i = k; i < n; i++){ //print_X(); int last = nums[i-k]; int num = nums[i]; if(last == num){ res.push_back(sum); continue; } // add num if(idx.count(num)){ to_X(num); } else if(coda > 0){ if(outX.size() == 0){ to_X(num); } else { to_out(num); } } else{ to_out(num); } //sub last if(idx.count(last)){ sub_X(last); } else{ sub_out(last); } while(coda >= 0 and outX.size() > 0){ out_to_X(); } while(coda < 0){ X_to_out(); } res.push_back(sum); } return res; } void print_X(){ for(auto [cnt, num]: Xsum){ cout << cnt << ", " << num << "; "; } cout << '\n'; } void sub_X(int num){ auto it = idx[num]; int cnt = it->first - 1; Xsum.erase(it); idx.erase(num); if(cnt > 0) idx[num] = Xsum.insert(make_pair(cnt, num)).first; else coda++; sum -= num; } void sub_out(int num){ auto it = idout[num]; int cnt = it->first - 1; outX.erase(it); idout.erase(num); if(cnt > 0) idout[num] = outX.insert(make_pair(cnt, num)).first; } void to_X(int num){ if(idx.count(num)){ auto it = idx[num]; int cnt = it->first + 1; Xsum.erase(it); idx[num] = Xsum.insert(make_pair(cnt, num)).first; } else{ idx[num] = Xsum.insert(make_pair(1, num)).first; coda--; } sum += num; } void to_out(int num){ if(idout.count(num)){ auto it = idout[num]; int cnt = it->first + 1; outX.erase(it); idout[num] = outX.insert(make_pair(cnt, num)).first; } else{ idout[num] = outX.insert(make_pair(1, num)).first; } } void out_to_X(){ auto [add_cnt, add_num] = *outX.rbegin(); idx[add_num] = Xsum.insert(make_pair(add_cnt, add_num)).first; auto it = outX.end(); it--; outX.erase(it); idout.erase(add_num); coda--; sum += (ll)add_cnt * (ll)add_num; } void X_to_out(){ auto [del_cnt, del_num] = *Xsum.begin(); idout[del_num] = outX.insert(make_pair(del_cnt, del_num)).first; Xsum.erase(Xsum.begin()); idx.erase(del_num); coda++; sum -= (ll)del_cnt * (ll)del_num; } }; -- 好希望我能跟oin一樣厲害 不知道我什麼時候才能有knight badge 太牛了 我以後要叫他牛奶貝 ----- Sent from JPTT on my iPad -- 很姆的咪 姆之咪 http://i.imgur.com/5sw7QOj.jpg -- ※ 發信站: 批踢踢實業坊(pttsite.org.tw), 來自: 123.205.121.194 (臺灣) ※ 文章網址: https://pttsite.org.tw/Marginalman/M.1729096117.A.A33

推 sustainer123: 大師 10/17 00:29

推 Sougou: 什麼時候要去比ACM 10/17 00:29

→ sixB: 昨天看我同學履歷有不知道什麼線上賽的銀牌 好羨慕== 10/17 00:31

→ sixB: 我想很慢 打比賽應該時間內什麼都寫不出來 10/17 00:31

→ Sougou: 現在叫做ICPC了，不知道他是不是比這個 10/17 00:32

推 sowrey: 有人被洋鬼子包養過嗎 10/17 00:32

→ Sougou: 有拿牌的話身價嘎嘎漲 10/17 00:32

→ sixB: icpc好像什麼honor的 我覺得有的放都好羨慕 我履歷好空：（ 10/17 00:42

推 Sougou: 去比一下啊，競程很有趣的啊 10/17 00:43

→ Sougou: honor沒拿牌吧 10/17 00:43

推 oin1104: 大師 10/17 00:46

推 cw758: 到底要多有錢才會想包養 10/17 00:46