[TIOJ]1285. A.分割矩形

.
. .
. . .
. . . .
就裸裸地做（？ 


#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;
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ]1994. 冰塊線

題目連結： http://tioj.infor.org/problems/1994 裸裸的遞迴下去，判斷朝向哪一邊即可～ 我的code挺暴力的>< # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int a[ 2050 ][ 2050 ]; void make (int x,int y,int l,int r,int sta){ if(r - l == 3){ if(sta == 1)a[x][y] = l,a[x+1][y] = l+1,a[x+1][y+1] = r-1,a[x][y+1] = r; if(sta == 2)a[x][y] = l,a[x+1][y] = r,a[x+1][y+1] = r-1,a[x][y+1] = l+1; if(sta == 3)a[x][y] = r-1,a[x+1][y] = r,a[x+1][y+1] = l,a[x][y+1] = l+1; if(sta == 4)a[x][y] = r-1,a[x+1][y] = l+1,a[x+1][y+1] = l,a[x][y+1] = r; return; } int t = (r-l+1)/4; int p = sqrt(r-l+1)/2; if(sta ...
繼續閱讀

[TIOJ]1617. [Interactive] 中位數

題目連結： 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。 顯然如果隨機數選的不...
繼續閱讀

[TIOJ]1420. 地雷區 (Mine)

題目連結： http://tioj.ck.tp.edu.tw/problems/1420 要看這個地雷有沒有和別的地雷有重疊到的地方，其實就是看這個地雷的周圍24塊，並用disjoint set維護。 # include < bits/stdc++.h > # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; typedef pair< int , int > Pair; bitset< 50004 > is; int n,m,c; int gx[ 24 ] = {0,0,1,-1,1,1,-1,-1,2,2,2,2,2,-2,-2,-2,-2,-2,1,0,-1,1,0,-1}, gy[ 24 ] = {1,-1,0,0,-1,1,-1,1,0,1,2,-1,-2,0,1,2,-1,-2,2,2,2,-2,-2,-2}; struct DJS{ int p[50004]; void init(){for(int i = 0 ; i < 50004 ; i++)p[i] = i;} int query (int x){return p[x] == x ? x : p[x] = query(p[x]);} void unite (int x,int y){x = query(x);y = query(y);p[x] = y;} int count (){ int ans = 0; for(int i = 1 ; i <= c; i++ ){ int tmp = query(i); if(!is[tmp])ans++; is[tmp] = 1; } return ans; } }djs; map<Pair, int > mp; int X[ 50004 ],Y...
繼續閱讀