SubaRyaのcode and 廢日常

題目來源:  https://codeforces.com/problemset/problem/1100/A 這題單純地將間格以依序取出("+1總數"-間隔+1數量)-("-1總數"-間隔-1數量)的最大值 #pragma gcc optimize("o2") #include<bits/stdc++.h> #define IO ios_base::sync_with_stio(false) #define CI cin.tie(NULL) #define int long long int using namespace std; signed main() { int n,k,po = 0 ,ne = 0 , str [ 1005 ]; cin >> n >> k; int times = k; for ( int i = 1 ;i <= n;i ++ ) { cin >> str [i]; if ( str [i] == 1 ) po ++ ; else ne ++ ; } // cout << po << " " << ne << endl; int flag = 0 ,totalne[ 1005 ] = { 0 },totalpo[ 1005 ] = { 0 }; while (times -- ) { flag ++ ; for ( int i = flag;i <= n;i += k) { // cout << "i=" << i << endl; if ( str [i] ==- 1 ) total...

題目URL:  http://codeforces.com/contest/999/problem/A 這題主要是判斷ai小就break，兩頭掃過去判斷一下順便記數，但記得特判全部都可以的時候 #include<bits/stdc++.h> using namespace std; int str[ 1005 ]; signed main() { int a,num,total = 0 ,key = 0 ; cin >> num >> a; for ( int i = 1 ;i <= num;i ++ ) { cin >> str[i]; if (str[i] <= a && key == 0 ) { total ++ ; } if (str[i] > a) key = 1 ; } if (total == num) return cout << num , 0 ; total = 0 ; for ( int i = 1 ;i <= num;i ++ ) { if (str[i] <= a) total ++ ; else break ; } for ( int i = num;i >= 1 ;i -- ) { if (str[i] <= a) total ++ ; else break ; } cout << total << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1017/problem/C 稍微想了一下，原來不是要我們去算真正的LIS&LDS(鬆了一口氣)，其實這題有一個小技巧，就是自己sqrt(n)為一組為遞減順序，依此類推，至於如果sqrt後有小數，那就是剩下的自己一組，每一組的頭即是最小遞增數量(LIS)，每一組的數量(剩下的除外)即是最小遞減的數量(LDS) #include<bits/stdc++.h> using namespace std; main() { priority_queue < int ,vector < int >> pq; int num,isq,flag = 1 ; double sq; cin >> num; isq = sqrt(num); sq = sqrt(num); if (sq == ( double )isq) { for ( int i = 1 ;i <= num;i ++ ) { pq.push(i); if (i % isq == 0 ) { while ( ! pq.empty()) { cout << pq.top() << " " ; pq.pop(); } } } } if (sq > ( double )isq) { isq ++ ; for ( int i = 1 ;i <= num;i ++ ) { pq.push(i); if (i % isq == 0 ) ...

題目URL: http://codeforces.com/contest/1017/problem/B 如果稍為的想一下，是否有想出只有判斷到同一個index的情況下只有ai=0 bi=0 或ai=1 bi=0 才會有需要採取交換的動作呢?(可以停下來想一下) 接下來只要判斷到以上條件，就需要"分別"跟在a裡有1 、0的數字交換，因此在輸入時就可以先把a裡面有1、0的數字分開加總，最後在下面判斷時即可加總需要換的數量。 但是記得每判到了一個就得把自己數的總和減1，否則會在後面時重複記數。 #include<bits/stdc++.h> using namespace std; string a,b; signed main() { long long int len,totala = 0 ,totalb = 0 ,total = 0 ; cin >> len; cin >> a; cin >> b; for ( int i = 0 ;i < len;i ++ ) { if (a[i] == '0' ) totala ++ ; else totalb ++ ; } for ( int i = 0 ;i < len;i ++ ) { if (a[i] == b[i] && a[i] == '0' ) { total += totalb; totala -- ; } else if (a[i] != b[i] && a[i] == '1' ) { total += totala; totalb -- ; } } cout << total << endl; ...

題目URL:  http://codeforces.com/contest/1017/problem/A 由於第一個就是要比較的人，因此輸入時就將四個數相加，其餘的輸入相加與之比較，即可排名次 #include<bits/stdc++.h> using namespace std; int total[ 1005 ]; main() { int num,a,b,c,d,ans = 1 ; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> a >> b >> c >> d; total[i] = a + b + c + d; if (total[ 0 ] < total[i] && i >= 1 ) ans ++ ; } cout << ans << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1016/problem/A 這題主要是分堆的技巧，嘛......每一筆的"和"跟每一筆的"除"去做然後記得將商數乘以原來的除數就可以維護這題的小性質。 #include<bits/stdc++.h> using namespace std; map < int , int > str; main() { ios_base :: sync_with_stdio( false ); cin.tie( NULL ); long long int a,b,total = 0 ,num; cin >> a >> b; for ( int i = 0 ;i < a;i ++ ) { cin >> num; total += num; str[i] = total / b; total -= (str[i] * b); } for ( int i = 0 ;i < a;i ++ ) cout << str[i] << " " ; cout << endl; return 0 ; }

題目URL:  http://codeforces.com/contest/1003/problem/A 水題~記數後挑最大的即可 #include<bits/stdc++.h> using namespace std; int str[ 1005 ]; main() { int a,num,maxu = 0 ; cin >> num; while (num -- ) { cin >> a; str[a] ++ ; } for ( int i = 0 ;i < 1005 ;i ++ ) maxu = max(maxu,str[i]); cout << maxu << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1008/problem/B 第一組取最大，後面判斷是否有遞減，可以組成任一組遞減即為YES。 #include<bits/stdc++.h> using namespace std; map < int , int > a,b; int num,maxa,maxb,minu; main() { int deter = 0 ; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> a[i] >> b[i]; } maxa = max(a[ 0 ],b[ 0 ]); for ( int i = 1 ;i < num;i ++ ) { //cout << maxa << endl; maxb = max(a[i],b[i]); minu = min(a[i],b[i]); if (maxa < maxb) { if (maxa < minu) { deter = 1 ; break ; } else { maxa = minu; } } else if (maxa >= maxb) maxa = maxb; } if (deter) return cout << "NO" , 0 ; cout << "YES" << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1004/problem/A 可以擴張就擴張，要判斷的是數若兩數之間一減一加(分別是右、左)加的那個數後比減的大，就不得擴張 #include<bits/stdc++.h> using namespace std; int str[ 1005 ],ans[ 1005 ]; main() { int a,b,flag = 0 ,total = 1 ; cin >> a >> b; for ( int i = 0 ;i < a;i ++ ) { cin >> str[i]; if (i >= 1 ) { if (str[i - 1 ] + b < str[i] - b) total += 2 ; else if (str[i - 1 ] + b == str[i] - b) total ++ ; } } cout << total + 1 << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1006/problem/A 嘛......判斷偶數就減1，奇數不變，就可以輸出啦~ #include<bits/stdc++.h> using namespace std; int str[ 1005 ]; main() { int num; cin >> num; for ( int i = 0 ;i < num;i ++ ) cin >> str[i]; for ( int i = 0 ;i < num;i ++ ) { if (str[i] % 2 == 0 ) cout << str[i] - 1 << " " ; else cout << str[i] << " " ; } cout << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1015/problem/E1 淹水淹水淹水法啦~~~~ 其實可以建四個方向前綴，取size的min，再O(n^2)比較，但O(n^3)可以過的話有何不可呢??(只可惜E2的hard edition就QQ了~) #include<bits/stdc++.h> using namespace std; char m[ 1005 ][ 1005 ]; int sor[ 4 ],a,b,total = 0 ,tot = 0 ,cou = 0 ,flag = 0 ,f = 0 ; int ans[ 10005 ],ansi[ 10005 ],ansj[ 10005 ],stri[ 10005 ],strj[ 10005 ]; signed main() { cin >> a >> b; for ( int i = 1 ;i <= a;i ++ ) for ( int j = 1 ;j <= b;j ++ ) { cin >> m[i][j]; if (m[i][j] == '*' ) { stri[flag] = i; strj[flag] = j; flag ++ ; } } int aa = 0 ,bb = 0 ,cc = 0 ,dd = 0 ; for ( int i = 0 ;i < flag;i ++ ) { aa = 0 ; tot = 1 ; while ((m[stri[i]][strj[i] - tot] == '*' || m[stri[i]][strj[i] - tot] == '#' ) && \ (m[stri[i]][strj[i] + tot] == '*' || m[...

題目URL: http://codeforces.com/contest/6/problem/C 這題很單純的是用deque去頭尾比總和拔值，並且分別記數 #include<bits/stdc++.h> using namespace std; signed main() { deque < int > de; int num,a = 0 ,b = 0 ,t,totala = 0 ,totalb = 0 ; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> t; de.push_back(t); } a += de.front(); de.pop_front(); totala ++ ; while ( ! de.empty()) { //cout << a << " " << b << endl;; if (b >= a) { a += de.front(); de.pop_front(); totala ++ ; } else { b += de.back(); de.pop_back(); totalb ++ ; } } cout << totala << " " << totalb << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1015/problem/D 這題有個小技巧，就是將總數均分k份，不足的一些各加1。 記得特判(n-1)*k是否小於s #include<bits/stdc++.h> using namespace std; #define int long long signed main() { int a,b,c,num,mo,tot = 1 ; cin >> a >> b >> c; if ((a - 1 ) * b < c || b > c) return cout << "NO" , 0 ; else { cout << "YES" << endl; num = c / b; mo = c % b; for ( int i = 0 ;i < b;i ++ ) { if (mo == 0 ) { if (tot + num > a) { tot -= num; cout << tot << " " ; } else { tot += num; cout << tot << " " ; } ...

題目URL:  http://codeforces.com/contest/1015/problem/C 相減sort後，aa總和從小減到大一邊記數，比b小就輸出 #include<bits/stdc++.h> using namespace std; #define int long long int aa,bb,str[ 100005 ]; signed main() { int a,b,total = 0 ,totala = 0 ,tot = 0 ; cin >> a >> b; for ( int i = 0 ;i < a;i ++ ) { cin >> aa >> bb; str[i] = aa - bb; total += bb; totala += aa; } sort(str,str + a); if (total > b) cout << - 1 << endl; else { for ( int i = a - 1 ;i >= 0 ;i -- ) { //cout << str[i] << endl; if (totala <= b) break ; totala -= str[i]; tot ++ ; } cout << tot << endl; } return 0 ; }

題目URL:  http://codeforces.com/contest/1015/problem/B 另類的bubble sort(? #include<bits/stdc++.h> using namespace std; int str[ 10005 ],num,flag = 0 ; string a,b,c,d; main() { cin >> num; cin >> a >> b; c = a; d = b; sort(c.begin(),c.end()); sort(d.begin(),d.end()); if (c != d) cout << - 1 << endl; else { for ( int i = 0 ;i < num;i ++ ) if (a[i] != b[i]) for ( int j = i;j < num;j ++ ) if (a[j] == b[i]) { for ( int k = j;k > i;k -- ) { swap(a[k],a[k - 1 ]); str[flag ++ ] = k; } break ; } cout << flag << endl; for ( int i = 0 ;i < flag;i ++ ) cout << str[...