• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            算法學社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0
            吐槽:
                1. 居然還漲分了,我了個槽。。。
                2. 現在在實驗室只能睡到凳子了,以后要回家睡了?
            300pt
                有一個w*h的矩陣,w,h未知。一開始你以某處為起點(未知)。你一開始向右移動,遇到邊界或者已經走過的位置就左轉,不能左轉就停止(ms我這個地方最后理解錯了,cha錯了一個)。
                給一個移動長度的序列A,(長50,每個數不超過50)。問w*h的可能的最小值,不可能就輸出-1。
            算法分析:
                如果可能的話,w等于偶數位置A[i]的最大值,h等于奇數位置A[i]的最大值。然后判斷w*h是否可行,判斷的方法就是枚舉起點,然后模擬一次。復雜度O(N^3)
                寫起來比較猥瑣。。。
            #include<vector>
            #include<iostream>
            using namespace std;
            int num[55][55];
            void chkmax(int &a,int b){if(a<b)a=b;}
            bool chk(int x,int y,int n,int m){
                return x >=0 && y>=0 && x<n && y<m && !num[x][y];
            }
            bool judge(int x,int y,int n,int m,vector<int> mv){
            //    cout<<"pos: "<<x<<" "<<y<<endl;
                memset(num,0,sizeof(num));
                num[x][y] = 1;
                for(int i = 0,dir = 0; i< mv.size(); i++, dir = (dir+1) % 4){
                    for(int j = 0; j <= mv[i]; j++){
                        int nx = x + (dir == 1) - (dir==3);
                        int ny = y + (dir == 0) - (dir==2);
                        if(j < mv[i]) {
                        //    cout<<nx<<" "<<ny<<endl;
                            if(!chk(nx,ny,n,m)) return 0;
                            x = nx; y = ny;
                            num[x][y] = 1;
                        }
                        else {
                            //cout<<x<<" "<<y<<endl;
                            if(i < mv.size() - 1 && chk(nx,ny,n,m)) return 0;
                        }
                //        cout<<x<<" "<<y<<endl;
                    }
                }
                return 1;
            }
            int chk(vector<int> moves, int n, int m){
                cout<<n<<" "<<m<<endl;
                for(int i=0;i<n;i++)
                    for(int j=0;j<m;j++)
                        if(judge(i,j,n,m,moves)) return n*m;
                return -1;
            }
            class RotatingBot{
                public : int minArea(vector <int> moves){
                    int len = moves.size();
                    int n = 0, m  =0;
                    for(int i=0;i<len;i++)
                        if(i & 1) chkmax(n,moves[i]);
                        else chkmax(m,moves[i]);
                    int ans = chk(moves, n+1,m+1);
                    return ans;
                }
            };
            500pt
                兩個人在無限大棋盤上玩游戲。甲執A子,乙執B子。一開始甲在(0,0)處放棋子A,甲和乙輪流放棋子。每次可以放的位置如下,如果x,y有棋子:
                    1. 如果x-1,y+1空,x+1,y-1可以放。
                    2. 如果x+1,y-1空,x+2,y可以放。
                每次甲/乙必須在所有可能放子的地方放子。問放子t次(t<=1,000,000,000,000)后,(x0,y0)到(x0+h,y0+w)的局面(x0,y0<1,000,000,000,000,w,h<50)。
            算法分析:
                畫一畫發現非常有規律,斜對角線是gray碼。相當于求第i個gray碼的第j個位置的值。可以找到兩個規律:
                    1. 第2^n個gray碼是 1....1
                    2. 第2^i + j個gray碼是兩個j拼接而成的
                然后遞歸求解就好了,復雜度log(t)。
            #include<string>
            #include<vector>
            #include<iostream>
            #include<cassert>
            using namespace std;
            typedef long long ll;
            int dfs(ll l, ll c){
            //    cout<<l<<" "<<c<<endl;
                if(l<c) return 0;
                if(l==1) return 1;
                if((l&1) && c == l/2+1) return 0;
                ll m;
                for(int i=0; (1LL<<i)<= l; m = (1LL<<i),i++) ;
                if(c>l/2) c = l-c+1;
                l -=m;
                if(l==0) return 1;
                return dfs(l,c);
            }
            class CheckerExpansion{
                public : vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h){
                    vector<string> ans;
                    for(int i=0;i<h;i++){
                        ans.push_back("");
                        for(int j=0;j<w;j++){
                            ll x = x0 + j, y = y0+h-i-1, l,c=-1;
                            int p = 0;
                            if((x+y)%2 == 0){
                                l = (x+y)/2+1;
                                if(y < l ){
                                    c = y+1;
                                }
                            }
                            if(c != -1 && l<=t) p = dfs(l,c);
                            char X = p == 0 ? '.' : (l&1 ? 'A': 'B');
                            ans[i].push_back(X);
                        }
                    }
                    return ans;
                }
            };
            posted on 2012-07-22 08:31 西月弦 閱讀(455) 評論(0)  編輯 收藏 引用 所屬分類: 比賽感言
            久久久久一本毛久久久| 理论片午午伦夜理片久久| 性高湖久久久久久久久| 亚洲精品国产字幕久久不卡 | 香蕉久久夜色精品升级完成| 国产亚洲综合久久系列| 久久国产成人| 久久99国产亚洲高清观看首页| 久久国产成人| 久久精品国产69国产精品亚洲| 亚洲乱码日产精品a级毛片久久| 乱亲女H秽乱长久久久| 四虎影视久久久免费观看| 国产精品久久久久…| 国内精品伊人久久久久妇| 久久香蕉国产线看观看99| 亚洲精品乱码久久久久久蜜桃不卡| 91精品日韩人妻无码久久不卡| 日韩精品久久无码中文字幕| 欧美日韩精品久久久免费观看| …久久精品99久久香蕉国产 | 精品久久久久久无码人妻蜜桃| 久久精品无码专区免费青青| 欧美日韩成人精品久久久免费看| 94久久国产乱子伦精品免费| 国内精品久久国产大陆| 浪潮AV色综合久久天堂| 久久精品免费一区二区| 久久99热这里只频精品6| 久久久久久久国产免费看| 国产精品久久久99| 亚洲精品高清国产一久久| 亚洲国产精品久久久久久| 国产成人久久精品一区二区三区| 伊人久久大香线焦AV综合影院| 国产香蕉久久精品综合网| 亚洲国产精品狼友中文久久久| 午夜精品久久久久久久无码| 久久精品国产精品亚洲| 香蕉aa三级久久毛片| 久久久久久久97|