吐槽：
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
西月弦 阅读(438)
评论(0) 编辑 收藏 引用 所属分类:
比赛感言