SubaRyaのcode and 廢日常

．題目URL:  http://codeforces.com/problemset/problem/1012/A ．有些的小技巧要注意，可先畫個座標去發現構成最小面積矩形的approach，即是左右與上下之距離最小、其他點包含在矩形內、最外圍的兩端點為邊界的最大與最小。當然，最initial的想法一定是對半剖分、其一reverse後的首與尾差積括號絕對值(25~27行 ans = xx * yy; ) ．(這題我看其他電神用sort就可以過，但我還用priority_queue，取兩端) 因為我最一開始以為可能性O(n^2)的內建sort會吃TLE，可能此題可以壓線過，相對性的，我怕這件事發生(因為是比賽)所以我用空間換取時間 。 ．但是，直到目前的說法依舊是有缺陷的，如果一個特測是: 1 1 2 3 3 3 4 11 那麼我的答案是16，可是答案是10。 ．接著停下來想一想，如果我將x軸以最小與最大的典固定，此時，我無論y軸的兩個數字為何，兩陣列各取一數字所組成的一個點「 必定 」至少一種方式使每一點坐落於矩形內(?)，此時全部暴搜一遍即可(O(n^2))，結果會吃TLE~~QQ(而且很不幸的有些會WA) ．再停下來想一下，固定的部分以直覺上與經驗上的method貌似沒錯，但：     ．(a)如何優化那看似擾人的暴搜？     ．(b)如何判斷真的是「至少一個必定」且最小? ．以特測 1 1 2 3 3 3 4 11 判斷，如果以暴搜會得到(1,3) (11,3)，答案是0，但有一個地方出錯了，會有一點(1,4)會超過原定矩形範圍     ．如何結合(a)與(b)? ． 先解決最小的問題，就用min去跑兩陣列除了首點之點兩個相減最小。然後兩陣列的兩數由小跑到大，就能維持上下的範圍且當狀態的最小。 #include<bits/stdc++.h> using namespace std; map < long long int , long long int > str1,str2,str; main() { long long int ans; priority_queue < long long int ,vector < long long i

題目URL:  http://codeforces.com/contest/1013/problem/B 我在練習賽時，這題爛在把 '&' 寫成 '&&' 浪費了30分鐘......恨啊~~ 我的寫法很耗空間，先用兩個陣列記數，其一去掃過判斷，只要等於2就break***，pretest AC，但最後在main test時又爛掉一次，因為要注意的地方是掃過判斷時，先別急著break(依我的寫法而論)。 (更改敘述接在***後面)把break打掉，改成全部取min，因為特測就是前面有兩個重複，其實後面只要換一個即可，這樣就main test AC了。 #include<bits/stdc++.h> using namespace std; map < int , int > str,boo,coo; main() { int a,b,len = 0 ,ans = 2 ,deter = 0 ,nans; cin >> a >> b; for ( int i = 0 ;i < a;i ++ ) { cin >> str[i]; len = max(len,str[i]); boo[str[i]] ++ ; coo[str[i]] ++ ; if (boo[str[i]] >= 2 ) { deter = 1 ; } } int de; if (deter == 1 ) cout << 0 << endl; else { for ( int i = 0 ;i <= len;i ++ ) { de = str[i] & b; if (de != str[i]) {

題目URL:  http://codeforces.com/contest/1013/problem/A 這題......我只恨題目囉嗦......嘛......訓練讀英題，好啦，總之把這一歸納一下，即可得知只是把兩陣列的總和拿去做比較。 #include<bits/stdc++.h> using namespace std; int stra,strb; main() { int num,totala = 0 ,totalb = 0 ; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> stra; totala += stra; } for ( int i = 0 ;i < num;i ++ ) { cin >> strb; totalb += strb; } if (totala >= totalb) cout << "Yes" << endl; else cout << "No" << endl; return 0 ; }

題目URL : http://codeforces.com/problemset/problem/1011/B 其實稍微想一下這題，二分搜......嗎......不 ! 看了看範圍即可想到一個很邪惡的作法------對 ! brute force ! 掃過去邊 input 邊標記一下，j 為天數，用 i 掃過去除，再用人數 tot 去減，tot < = 0就輸出囉~至於我的 j 為何由大到小去掃，讀者們不妨思考一下~~ =w= #include<bits/stdc++.h> using namespace std; int str[ 1005 ]; main() { int a,b,x,ans = 0 ; cin >> a >> b; for ( int i = 0 ;i < b;i ++ ) { cin >> x; str[x] ++ ; } int tot; for ( int j = 100 ;j >= 1 ;j -- ) { tot = a; for ( int i = 1 ;i <= 100 ;i ++ ) tot -= str[i] / j; if (tot <= 0 ) { ans = j; break ; } } cout << ans << endl; return 0 ; } (其實由小到大依我所知要判到 tot > 0 後 ans 要減 1 之類的我覺得好煩 XD 深怕特判例外隱藏其中所以走簡單且保險的路線)

題目URL :  http://codeforces.com/contest/1011/problem/A 啊啊啊啊啊~~來刷水題囉~~(練練手速&提升自信的好管道) 單純標記+由小掃到大取不可相臨的字母。 #include<bits/stdc++.h> using namespace std; int cho[ 30 ]; char str[ 1005 ]; main() { int a,b,ans = 0 ; cin >> a >> b; for ( int i = 0 ;i < a;i ++ ) { cin >> str[i]; cho[str[i] - 96 ] ++ ; } int tot = b; for ( int i = 1 ;i <= 26 ;i ++ ) { if (tot == 0 ) break ; else if(tot != 0 && cho[i] >= 1 ) { if (cho[i - 1 ] !=- 1 ) { ans += i; tot -- ; cho[i] =- 1 ; } } } if (tot == 0 ) cout << ans << endl; else if (tot > 0 ) cout << - 1 << endl; return 0 ; }

我叫蘇子權，準高二16歲，平時愛耍廢(也就是看動漫、爬爬文、刻刻code、刷新TLE次數......之類的)，現就學於時雨私立高級監獄(中學 (? )擔任第一屆最雷資訊社社長，一年過去了一張比賽獎狀皆無......然後進修廢到二階沒過(持續自己進修資芽algo_18b中)，偶爾陪電神polarischiba打CF，然後又被電。 進修方式： ·  去CF&AC看人家的code，遇到模板大神就跪；遇到簡潔到看不懂我就debug · 看看資芽講義，不會的就去google其他大神的解析 · 寫寫賽後心得，去看看polarischiba&他們同學的賽後心得，在心理建設方面有很大的幫助 · 追新番&補舊番，看起來很耍廢，但......真的很廢(我 (? ) 目標&夢想： · 想進TOI卻要等明年的可悲人 · 把日文學好然後去日本 · 做出NERvGear Conclusion ·  私心推薦「polarischiba的code收藏區」 URL: https://polarischiba.blogspot.com/ · 我的blog懶得複雜設計(其實是我不會 (? )，所以我的版面跟他十分相像，而且我覺得這個版面還不錯?  (此為建網日期，因為可能會補過去日期的心得&code) 備註：CF(codeforces)             AC(AtCoder)

題目URL: http://codeforces.com/contest/1005/problem/B 簡單的從後往前掃，注意不一樣就break，重點是我看了其他人都用reverse的函式再從頭開始掃(我又學到一招了)，反正我是用手刻，至於快或慢......影響不大，看個人習慣~細節注意就行 自我補充reverse: string a; reverse( a.begin() , a.end() ); #include<bits/stdc++.h> using namespace std; char str1[ 200005 ],str2[ 200005 ]; int main() { cin >> str1; cin >> str2; int len1 = strlen(str1) , len2 = strlen(str2); int tot = len1 + len2,total = 0 ,deter = 0 ; for ( int i = len1 - 1 ,j = len2 - 1 ;i >= 0 ,j >= 0 ;i -- ,j -- ) { if (str1[i] != str2[j]) { total = len1 - 1 - i + len2 - 1 - j; deter = 1 ; } break ; } if (deter == 1 ) cout << tot - total << endl; else if (total == 0 ) cout << abs(len1 - len2) << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1005/problem/C   嘛......這題原本最initial的想法是兩兩去湊，但看了看範圍......絕對吃TLE，所以換個思路，反正他只是想找不為2的次方的兩兩和之一數，所以以防CE，我習慣陣列使用map ，好習慣(? 然後出現過的數字標一標，掃過去再用*2的迴圈去找2的次方......等小細節判斷，就亮綠燈啦~! #include<bits/stdc++.h> using namespace std; int str[ 200005 ]; map < long long , long long > pt; main() { int num; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> str[i]; pt[str[i]] ++ ; } int com,tot = 0 ; for ( int i = 0 ;i < num;i ++ ) { int deter = 0 ; com = str[i]; pt[str[i]] -- ; for ( long long j = 1 ;j < 2000000000 ;j *= 2 ) { if (j <= com) continue ; if (pt[j - com] > 0 ) deter = 1 ; } pt[com] ++ ; if (deter == 0 ) tot ++ ; } cout << tot << endl; return