頹coding

題目連結： http://codeforces.com/contest/821 #A 照著敘述做就好。 # include < iostream > using namespace std; int a[ 60 ][ 60 ]; int main (){ int n;cin >> n; for(int i = 0 ; i < n ; i++) for(int j = 0; j < n ; j++) cin >> a[i][j]; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ if(a[i][j] != 1){ bool flag = 0; for(int s = 0 ; s < n ; s++) for(int p = 0 ; p < n ; p++) if(a[i][s] + a[p][j] == a[i][j]) flag = 1; if(!flag){ puts("No"); return 0; } } } } puts("Yes"); return 0; } #B 枚舉所有Y點，然後O(1)判斷那個點可以拿幾根香蕉。 # include < iostream > # include < cmath > using namespace std; long long m,b; long long a (long long y){return (y-b)*-m;} long long check (

題目連結： http://codeforces.com/contest/816 #A 就勇敢的給他暴力做下去～ '9' + 1 會變成 ':'。 # include < iostream > # include < string > using namespace std; int main (){ string s;cin >> s; int ans = 0; while(1){ if(s[0] == s[4] && s[1] == s[3])break; s[4]++; if(s[4] == ':')s[4] = '0',s[3]++; if(s[3] == '6')s[3] = '0',s[1]++; if(s[1] == '4' && s[0] == '2')s[1] = s[0] = '0'; if(s[1] == ':')s[1] = '0',s[0]++; ans++; } cout << ans << endl; return 0; } #B 感覺就有很多人會寫線段樹區間加值ＸＤ 但只要記每個區間的左界、右界，然後掃過去每個點被覆蓋的次數就是在這之前出現的左界數 - 右界數。詢問就用前綴和即可。 # include < iostream > # define N 200005 # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; int l[N],r[N],tmp,c[N],a,b; int main (){jizz int n,k,q;cin >> n >> k >> q; for(int i = 0 ; i &l

. . . . . . . . . . 就裸裸地做（？ # include < iostream > using namespace std; int gcd (int a,int b){return a == 0 ? 0 : b/a + gcd(b%a,a);} int main (){ int x,y; while(cin >> x >> y)cout << gcd(x,y) << endl; }

題目連結： http://tioj.infor.org/problems/1617 大家如果想一下肯定發現一個性質，Med3() 對於三個數字，會回傳中間值，而掃過整個序列，必能找出最大值與最小值的位置， 當然就可以透過這個方法，找n/2次，最後剩下的那個數字就是中位數，但這樣顯然會用太多次Med3()。 因為你已經找出這個序列的極值，那隨便找另外兩個數字和其中一個極值作Med3()會等同於比較那兩個數字的大小（因為極值不可能是中位數），因此可以用sort函式來排序，中間值就是中位數。 # include " lib1617.h " # include < algorithm > int a,b,n,k,v[ 1505 ]; int main (){ n = Get_Box(); if(n == 1) Report (1); a = 1;b = 2; for(int i = 3; i <= n ; i++){ int k = Med3(a,b,i); if(a == k)a = i; if(b == k)b = i; } for(int i = 1 ; i <= n ; i++)if(i != a and i != b)v[k++] = i; std::sort(v,v+n-2,[](int x,int y){ int tmp = Med3(a,x,y); return tmp == x ? 1 : 0; }); Report(v[(n-2)/2]); return 0; } 這樣只能拿40分。 不保證AC解法： 比中位數小的數字個數會等於比中位數大的數字個數，因此我們先找出這個序列的極值，然後隨機找一個數 t 並算出比 v[t] 小和大的個數，而整個序列的中位數在目前序列中會有 k 個數字比v[t]小，如果比v[t]小的數字個數剛好等於 k ，那就找到整個序列的中位數，如果> k 那就改成在比v[t]小的那個陣列內找答案，如果< k那就必須在比v[t]大的那個陣列找答案，且k要減l.size()+1。 顯然如果隨機數選的不

題目連結： https://oj.icpc.tw/contest/9/problem/E 我們可以先想一下，對於某個區間L,R，你要怎麼Ｏ(1)判斷他能不能利用Ｋ分來使這個區間變成最長連續同值區間。 既然要變成最長連續同值區間，一定是使所有值變成該區間內的最大值，而需要多少分才能辦到就等同於將區間最大值乘以區間長度減掉區間和。可利用sparse table以及前綴和來實作。 我們便可以窮舉所有區間，但顯然會TLE。 但在當我們窮舉右界時，其左界具有單調性，因此只要滑過去，一邊取區間長度的max就好。 # include < iostream > # include < vector > # define N 1000005 # define PB push_back using namespace std; int n,k; int a[N]; int logg (int l,int r){return 31 - __builtin_clz(r-l+1);} vector < int > s[ 20 ]; bool check (int aa,int bb){ int tt = logg(aa,bb); int mm = max(s[tt][aa-1],s[tt][bb-(1 << tt)]); int tmp = mm * (bb-aa+1) - a[bb] + a[aa-1]; if(tmp <= k)return 1; return 0; } int main (){ int T;cin >> T; while(T--){ for(int i = 0; i < 20 ; i++)s[i]. clear (); cin >> n >> k; for(int i = 1 ; i <= n ; i++){ cin >> a[i]; s[0]. PB (a[i]); a[i] += a[i-1]; }

題目連結： http://codeforces.com/contest/814 #A k >= 2時一定是輸出Yes，至於k = 1時就只要比第 i 項有沒有小於 i-1 項。 # include < iostream > # include < algorithm > # define endl '\n' # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; int a[ 7122 ],b[ 7122 ]; int main (){ int n,k;cin >> n >> k; for(int i = 0 ; i < n ; i++)cin >> a[i]; for(int j = 0 ; j < k ; j++)cin >> b[j]; if(k >= 2){cout << "Yes" << endl;return 0;} for(int i = 0 ; i < n ; i++){ if(!a[i])a[i] = b[0]; if(a[i] < a[i-1] && i){ cout << "Yes" << endl; return 0; } } cout << "No" << endl; return 0; } #B 有些人會用很多條件去判斷哪一格該放哪一個數字，但其實因為 a 序列和 b 序列皆和 p 序列差一個數字，而a != b，因此可以直接嘗試看看把a序列數字重複的那兩格擇一替換成缺少的那個數字，並檢查是否與 b 序列差一，差一的即為p序列。 # include < iostream > # include < bitset > # define endl

題目連結： http://codeforces.com/contest/812 #A 一開始我題目有點看不太懂，就隨便寫一寫pretest過了，沒想到之後被hackＸＤ。 就是一題暴力題，code有點醜。 # include < iostream > # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; bool ok[ 5 ][ 5 ]; int main (){jizz for(int i = 1 ;i <= 4; i++ ) for(int j = 1; j <= 4 ; j++) cin >> ok[i][j]; bool flag = 0; for(int i = 1; i <= 4; i++){ if(ok[i][4]){ if(i == 1 && (ok[2][1] || ok[4][3] || ok[i][1] || ok[i][2] || ok[i][3] || ok[3][2])) flag = 1; else if(i == 2 && (ok[1][3] || ok[3][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[4][2])) flag = 1; else if(i == 3 && (ok[2][3] || ok[4][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[1][2])) flag = 1; else if(i == 4 && (ok[3][3] || ok[1][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[2][2]))