算法学社
記錄難忘的征途
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 西月弦 阅读(414) 评论(0)  编辑 收藏 引用 所属分类: 比赛感言

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理