Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

32ms,比较弱的代妈,用了STL的

Posted by KatrineYang at 2016-08-21 00:27:20 on Problem 2411
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

vector<int> trans[12][2048];
bool jsed[12] = {0};

bool has(int n, int b){
	return (n & (1<<b)) > 0;
}

int J[13] = {0};

int getJ(int ip){
	if(J[ip] > 0) return J[ip];
	int ans = (1<<ip) + (1<<(ip+1));
	J[ip] = ans;
	return ans;
}

void js(int h){
	jsed[h] = 1;
	int p2 = (1 << h);
	for(int i = 0; i < p2; i++){
		vector<int> pos;
		for(int j = 0; j < h-1; j++){
			if(!has(i, j) && !has(i, j+1)) pos.push_back(j);
		}
		int sz = pos.size();
		trans[h][i].push_back(p2-1-i);
		for(int i1 = 0; i1 < sz; i1++){
			trans[h][i].push_back(p2-1-i-getJ(pos[i1]));
		}
		for(int i1 = 0; i1 < sz-1; i1++){
			for(int i2 = i1+1; i2 < sz; i2++){
				if(pos[i2]-pos[i1]<=1) continue;
				trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2]));
			}
		}
		for(int i1 = 0; i1 < sz-2; i1++){
			for(int i2 = i1+1; i2 < sz-1; i2++){
				if(pos[i2]-pos[i1]<=1) continue;
				for(int i3 = i2+1; i3 < sz; i3++){
					if(pos[i3]-pos[i2]<=1) continue;
					trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2])-getJ(pos[i3]));
				}
			}
		}
		for(int i1 = 0; i1 < sz-3; i1++){
			for(int i2 = i1+1; i2 < sz-2; i2++){
				if(pos[i2]-pos[i1]<=1) continue;
				for(int i3 = i2+1; i3 < sz-1; i3++){
					if(pos[i3]-pos[i2]<=1) continue;
					for(int i4 = i3+1; i4 < sz; i4++){
						if(pos[i4]-pos[i3]<=1) continue;
						trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2])-getJ(pos[i3])-getJ(pos[i4]));
					}
				}
			}
		}
		for(int i1 = 0; i1 < sz-4; i1++){
			for(int i2 = i1+1; i2 < sz-3; i2++){
				if(pos[i2]-pos[i1]<=1) continue;
				for(int i3 = i2+1; i3 < sz-2; i3++){
					if(pos[i3]-pos[i2]<=1) continue;
					for(int i4 = i3+1; i4 < sz-1; i4++){
						if(pos[i4]-pos[i3]<=1) continue;
						for(int i5 = i4+1; i5 < sz; i5++){
							if(pos[i5]-pos[i4]<=1) continue;
							trans[h][i].push_back(p2-1-i-getJ(pos[i1])-getJ(pos[i2])-getJ(pos[i3])-getJ(pos[i4])-getJ(pos[i5]));
						}
					}
				}
			}
		}
	}

}

int main() {
	while(1){
		int w, h;
		scanf("%d%d", &w, &h);
		if(w == 0 && h == 0) break;
		if((w*h)%2 == 1){
			printf("0\n");
			continue;
		}
		if((!(jsed[w] ^ jsed[h]) && w < h) || (jsed[w] && (!jsed[h]))){
			int temp = h;
			h = w;
			w = temp;
		}
		if(h == 1){
			printf("1\n");
			continue;
		}
		if(!jsed[h]){
			js(h);
		}
		long long int dp[12][2048] = {0};
		int p2 = (1<<h);
		//初始值:要么洞要么棍
		for(int i = 0; i < p2; i++){
			bool ok = 1;
			bool st[12];
			for(int j = 0; j < h; j++){
				if((i & (1<<j)) > 0) st[j] = 1;
				else st[j] = 0;
			}
			int cnt = 0;
			for(int j = 0; j < h; j++){
				if(st[j]){
					if(cnt%2 != 0){
						ok = 0;
						break;
					}
					cnt = 0;
				}
				else{
					cnt++;
				}
			}
			if(cnt%2 != 0) ok = 0;
			if(ok) dp[1][i] = 1;
			else dp[1][i] = 0;
		}
		//for(int i = 0; i < p2; i++) cout << dp[1][i] << " "; cout << endl;
		for(int i = 2; i <= w; i++){
			if(i == w){
				int sz = trans[h][0].size();
				long long int temp = 0;
				for(int j = 0; j < sz; j++){
					temp += dp[i-1][trans[h][0][j]];
				}
				//cout << temp;
				printf("%I64d\n", temp);
				break;
			}
			for(int j = 0; j < p2; j++){
				long long int temp = 0;
				int sz = trans[h][j].size();
				for(int k = 0; k < sz; k++){
					temp += dp[i-1][trans[h][j][k]];
				}
				dp[i][j] = temp;
			}
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator