TC SRM 400 DIV2

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

没事做场TC，结果跪了。。。。

250PT:从(0,0)出发，出租车的速度是一定的，步行的速度也是固定的，所以最快的肯定是全部步行，或者步行至一个出租车处，然后坐车。

不会坐两辆出租车的。枚举所有出租车即可。

class GrabbingTaxi{
public:
	int minTime(vector <int> tXs, vector <int> tYs, int gX, int gY, int walkTime, int taxiTime){
		int ans=(abs(gX)+abs(gY))*walkTime;
		for(int i=0;i<tXs.size();i++)
			ans=min(ans,(abs(tXs[i])+abs(tYs[i]))*walkTime+(abs(gX-tXs[i])+abs(gY-tYs[i]))*taxiTime);
		return ans;
	}
};

500Pt：形如p^q的如果p为素数，q大于1，称为XX数。问n是否为XX数，找出p,q。

由于 n有一定的范围，最多不超过2^60,也就是q是肯定小于60的，便可以枚举q判断是否满足条件

class StrongPrimePower{
public:
	bool isprime(LL num){
		if(num==2)
			return true;
		if(!(num&1))
			return false;
		for(int i=3;i<=(int)sqrt(num*1.0)+1;i++)
			if(num%i==0)
				return false;
		return true;
	}
	LL Pow(LL  a,int b){
		return b==0?1:a*Pow(a,b-1);
	}
	vector <int> baseAndExponent(string n){
		LL num;
		sscanf(n.c_str(),"%lld",&num);
		vector<int>ans;
		for(int i=2;i<=60;i++){
			LL p=(int)(eps+pow(num,1.0/i));
			if(Pow(p,i)==num&&isprime(p)){
				ans.push_back((int)p);
				ans.push_back(i);
				return ans;
			}
		}
		return ans;
	}
};

1000pt：跪烂的题，开关问题，最多是8*8，其实可以枚举第一行(2^8)，然后再判断是否满足即可。我偏来个高斯消元，结果发现有多解，然后就枚举自由变元，结果第一组数据就越界，猜测是栈溢出？？？？以下的代码是只能判断无解和唯一解的。

int way[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,-1},{-1,1}};
class LightedPanels{
public:
	int a[70][70],n,row,col;
	void debug(){
		for(int i=0;i<n;i++){
			for(int j=0;j<=n;j++)
				printf("%d ",a[i][j]);
			printf("\n");
		}
	}
	int gauss(){
		int i,j;
		for(i=0,j=0;i<n&&j<n;j++){
			int k=i;
			for(;k<n;k++)
				if(a[k][j])
					break;
			if(a[k][j]){
				for(int r=0;r<=n;r++)
					swap(a[i][r],a[k][r]);
				for(int r=0;r<n;r++)
					if(r!=i&&a[r][j])
						for(k=0;k<=n;k++)
							a[r][k]^=a[i][k];
				i++;
			}
			debug();
			cout<<endl;
		}
		for(j=i;j<n;j++)
			if(a[j][n])
				return -1;
		int ans=0;
		for(int i=0;i<n;i++)
			if(a[i][n])
				ans++;
		return ans;
	}
	int minTouch(vector <string> board){
		row=board.size();col=board[0].size();
		n=row*col;
		memset(a,0,sizeof(a));
		for(int i=0;i<row;i++)
			for(int j=0;j<col;j++){
				a[i*col+j][i*col+j]=1;
				if(board[i][j]=='.')
					a[i*col+j][n]=1;
				for(int k=0;k<8;k++){
					int x=i+way[k][0],y=j+way[k][1];
					if(x>=0&&y>=0&&x<row&&y<col)
						a[i*col+j][x*col+y]=1;
				}
			}
		return gauss();
	}
};