吐槽：
1. 居然還漲分了，我了個(gè)槽。。。
2. 現(xiàn)在在實(shí)驗(yàn)室只能睡到凳子了，以后要回家睡了？
300pt
有一個(gè)w*h的矩陣，w，h未知。一開始你以某處為起點(diǎn)(未知)。你一開始向右移動(dòng)，遇到邊界或者已經(jīng)走過的位置就左轉(zhuǎn)，不能左轉(zhuǎn)就停止(ms我這個(gè)地方最后理解錯(cuò)了，cha錯(cuò)了一個(gè))。
給一個(gè)移動(dòng)長(zhǎng)度的序列A，(長(zhǎng)50，每個(gè)數(shù)不超過50)。問w*h的可能的最小值，不可能就輸出-1。
算法分析：
如果可能的話，w等于偶數(shù)位置A[i]的最大值，h等于奇數(shù)位置A[i]的最大值。然后判斷w*h是否可行，判斷的方法就是枚舉起點(diǎn)，然后模擬一次。復(fù)雜度O(N^3)
寫起來(lái)比較猥瑣。。。
#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
兩個(gè)人在無(wú)限大棋盤上玩游戲。甲執(zhí)A子，乙執(zhí)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)。
算法分析：
畫一畫發(fā)現(xiàn)非常有規(guī)律，斜對(duì)角線是gray碼。相當(dāng)于求第i個(gè)gray碼的第j個(gè)位置的值。可以找到兩個(gè)規(guī)律：
1. 第2^n個(gè)gray碼是 1....1
2. 第2^i + j個(gè)gray碼是兩個(gè)j拼接而成的
然后遞歸求解就好了，復(fù)雜度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
西月弦 閱讀(447)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
比賽感言