【NOI2005】【DLX】智慧珠游戏(code)

Emoi posted @ 2012年9月17日 22:32 in 未分类 , 1333 阅读

 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<cctype>
#include<bitset>
using namespace std;

const int tt[61][6][2] =
{
	{{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 0}, {0, 1}, {1, 0}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 0}, {0, 1}, {1, 1}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 0}, {1, 0}, {1, 1}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 1}, {1, 0}, {1, 1}, {0, 0}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 2}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {1, 1}, {1, 2}, {0, 0}},
	{{4, 0}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {2, 0}, {0, 1}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {1, 1}, {2, 1}, {0, 0}},
	{{4, 0}, {0, 1}, {1, 1}, {2, 1}, {2, 0}, {0, 0}},	
	{{4, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {0, 0}},		
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {2, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}},
	{{5, 0}, {0, 2}, {1, 2}, {2, 0}, {2, 1}, {2, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 2}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 1}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 2}},		 
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {1, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {2, 1}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {1, 0}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {2, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 2}},
	{{5, 0}, {0, 0}, {0, 2}, {1, 0}, {1, 1}, {1, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {0, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {1, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {1, 1}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}},
	{{5, 0}, {1, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}},
	{{5, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 1}, {1, 2}, {1, 3}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {0, 2}, {0, 3}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {2, 0}, {3, 0}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {3, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {1, 1}, {2, 1}, {3, 1}},
	{{5, 0}, {0, 1}, {1, 1}, {1, 0}, {2, 0}, {3, 0}},
	{{5, 0}, {0, 1}, {1, 0}, {1, 1}, {1, 2}, {2, 1}},
	{{5, 0}, {0, 1}, {0, 2}, {1, 0}, {2, 0}, {1, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}},
	{{5, 0}, {0, 0}, {1, 0}, {1, 1}, {2, 1}, {2, 2}},
	{{5, 0}, {0, 2}, {1, 1}, {1, 2}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 3}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 0}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 3}},			 
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {0, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {3, 1}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {0, 0}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {3, 0}}
};

const int t[13][2] = 
{
	{0, 0}, {1, 4}, {5, 6}, {7, 14}, {15, 15}, {16, 19}, {20, 27}, 
	{28, 31}, {32, 39}, {40, 47}, {48, 48}, {49, 52}, {53, 60}
};
			  
const int ft[61] = 
{
	0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 5, 5, 5, 5, 
	6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 
	9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12
};

const int tooo[78] = 
{
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12
};
	
char m1[12][12];

bool use[11][11];
bool choose[3005];

int d[350005], u[350005], r[350005], l[350005], col[350005], row[350005], size[105];
int done[13];
int mtx[3005][70];
int btl[11][11], ltb[60][2], ctl[100], map[11][11];
int h, z, node;
int xx[3005], yy[3005], nn[3005];
int num, que[100];

void init()
{
	memset(done, 0, sizeof(done));
   freopen("zhzyx.in", "r", stdin);
	for (int i = 1; i <= 10; i++) 
	{
		gets(m1[i]);
		for (int j = 1; j <= i; j++)
		{
			map[i][j] = tooo[(int)m1[i][j - 1]];
			if (map[i][j]) use[i][j] = 1, done[map[i][j]] = 1;
		}
	}
}

bool check(int k, int x, int y)
{
	for (int i = 1; i <= tt[k][0][0]; i++)
		if (use[x + tt[k][i][0]][y + tt[k][i][1]] || x + tt[k][i][0] < y + tt[k][i][1] || x + tt[k][i][0] > 10) return 0;
	return 1;
}

void prepare()
{
	h = 0;
	for (int i = 1; i <= 10; i++)
		for (int j = 1; j <= i; j++)
			if (!use[i][j])
				btl[i][j] = ++h;
	for (int i = 1; i <= 12; i++)
		if (!done[i])
			ctl[i] = ++h;
	z = 0;
	memset(mtx, 0, sizeof(mtx));
	for (int i = 1; i <= 12; i++)
		if (!done[i])
			for (int j = t[i][0]; j <= t[i][1]; j++)
				for (int x = 1; x <= 10; x++)
					for (int y = 1; y <= x; y++)
						if (check(j, x, y))
						{
							mtx[++z][ctl[i]] = 1;
							xx[z] = x; yy[z] = y; nn[z] = j;
							for (int k = 1; k <= tt[j][0][0]; k++)
								mtx[z][btl[x + tt[j][k][0]][y + tt[j][k][1]]] = 1;
						}
}


void build(int line)
{
	for (int i = 1; i <= num; ++i, ++node)
	{
		int p = que[i];
		size[p]++;
		row[node] = line;
		col[node] = p;
		d[node] = p;
		u[node] = u[p];
		d[u[node]] = node;
		u[d[node]] = node;
		if (i == 1) r[node] = node, l[node] = node;
		else
		{
			l[node] = node - 1;
			r[node] = node - i + 1;
			l[r[node]] = node;
			r[l[node]] = node;
		}
	}
}

void addp()
{
	node = h + 1;
	memset(r, -1, sizeof(r));
	memset(l, -1, sizeof(r));
	memset(u, -1, sizeof(r));
	memset(d, -1, sizeof(r));
	for (int i = 1; i <= h; i++)
		r[i - 1] = i, l[i] = i - 1, u[i] = i, d[i] = i, row[i] = 0, col[i] = i, size[i] = 1;
	r[h] = 0; l[0] = h; u[0] = 0; d[0] = 0; col[0] = 0; row[0] = 0;

	for (int i = 1; i <= z; ++i)
	{
		num = 0;
		for (int j = 1; j <= h; ++j)
			if (mtx[i][j]) que[++num] = j;
		build(i);
	}
}

void remove(int k)
{
	r[l[k]] = r[k]; l[r[k]] = l[k];
	for (int i = d[k]; i != k; i = d[i])
		for (int j = r[i]; j != i; j = r[j])
		{
			u[d[j]] = u[j];
			d[u[j]] = d[j];
			size[col[j]]--;
		}
}
void resume(int k)
{
	for (int i = u[k]; i != k; i = u[i])
		for (int j = l[i]; j != i; j = l[j])
			size[col[u[d[j]] = d[u[j]] = j]]++;
	l[r[k]] = r[l[k]] = k;
}
bool dfs(int k)
{
	if (r[0] == 0) return 1;
	int mini = INT_MAX, pos = 0;
	for (int i = r[0]; i != 0; i = r[i])
		if (size[i] < mini) mini = size[i], pos = i;
	remove(pos);
	for (int p = d[pos]; p != pos; p = d[p])
	{
		choose[row[p]] = 1;
		for (int q = r[p]; q != p; q = r[q]) remove(col[q]);
		if (dfs(k + 1)) return 1;
		choose[row[p]] = 0;
		for (int q = l[p]; q != p; q = l[q]) resume(col[q]);
	}
	resume(pos);
	return 0;
}
void fill(int k, int x, int y)
{
	for (int i = 1; i <= tt[k][0][0]; i++)
		map[x + tt[k][i][0]][y + tt[k][i][1]] = ft[k];
}

void outit()
{
   freopen("zhzyx.out", "w", stdout);
	if (dfs(1))
	{
		for (int i = 1; i <= 3005; i++) if (choose[i]) fill(nn[i], xx[i], yy[i]);
		for (int i = 1; i <= 10; i++)
		{
			for (int j = 1; j <= i; j++) printf("%c", (char)map[i][j] + 64);
			printf("\n");
		}
	}
	else cout<<"No solution"<<endl;
	exit(0);
}

int main()
{
   init();
	prepare();
	addp();
	outit();
   return 0;
}
Avatar_small
seo service UK 说:
2024年1月16日 16:58

A very excellent blog post. I am thankful for your blog post. I have found a lot of approaches after visiting your post

Avatar_small
먹튀신고 说:
2024年2月18日 13:54

Awesome blog! Do you have any tips and hints for aspiring writers? I’m planning to start my own website soon but I’m a little lost on everything. Would you propose starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m totally overwhelmed .. Any recommendations? Many thanks! 

Avatar_small
먹튀폴리스신고 说:
2024年2月18日 13:54

Definitely believe that which you said. Your favorite justification appeared to be on the net the simplest thing to be aware of. I say to you, I certainly get annoyed while people consider worries that they plainly don’t know about. You managed to hit the nail upon the top and defined out the whole thing without having side-effects , people can take a signal. 

Avatar_small
먹튀사이트조회 说:
2024年2月18日 13:54

Your blog is very helpful for beginners who want to learn Data science. I am also a Data science developer. I had done Data Science course from TGC India. They offer a variety of tutorials covering everything from the processes of Data Science to how to get started with Data Science.

Avatar_small
안전사이트 说:
2024年2月18日 14:23

Thanks for sharing very Nice Information for Us. Otherwise if anyone want to learn Python, Data Sciences and Python Frameworks. Expert Trainers, Project based Training, Placement assistance makes us different from others

Avatar_small
먹튀검증업체 说:
2024年2月18日 14:23

Driving forward Through You In Normal Need To Partake In The Standard Expansions Of Having A Standard Presence Destruction Then You Truly Need Not Go Out Conventionally. .You Can Other Than Help The Relationship Of Our Escorts Who Is Available to Driving Forward And In All Pieces Of The Country.

Avatar_small
먹튀신고 说:
2024年2月18日 14:24

There are certainly a lot of details like that to take into consideration. That is a great point to bring up. I offer the thoughts above as general inspiration but clearly there are questions like the one you bring up where the most important thing will be working in honest good faith. I don?t know if best practices have emerged around things like that, but I am sure that your job is clearly identified as a fair game. Both boys and girls feel the impact of just a moment’s pleasure, for the rest of their lives.

Avatar_small
안전놀이터검증 说:
2024年2月18日 15:23

I spend time people’s writing. It has the excellent to consider you demonstrate around thoughts together with the intellect and also res while doing this very important topic is sometimes successfully deemed.

Avatar_small
카지노탐구생활 说:
2024年2月18日 15:23

I love how your blog delves into diverse topics, providing a well-rounded and enriching reading experience. It’s my go-to source for learning something new every day.

Avatar_small
토크리 说:
2024年2月18日 15:25

It was a decent post to be sure. I completely delighted in understanding it in my lunch time. Will definitely come and visit this blog all the more frequently. Much obliged for sharing.

Avatar_small
토디야 说:
2024年2月18日 15:27

Wow! This could be one particular of the most beneficial blogs We’ve ever arrive across on this subject. Actually Great. I’m also a specialist in this topic therefore I can understand your hard work.

Avatar_small
먹튀검증 说:
2024年2月18日 15:27

The best alternative to Backpage is out there and it is ebackpage.com. It has turned out to be the best Backpage replacement after its seizure. It has amassed the most traffic from the Backpage demise. This has been the best alternative to both the customers and consumers in the market.

Avatar_small
먹튀검증사이트 说:
2024年2月18日 15:28

Your blog is very helpful for beginners who want to learn Data science. I am also a Data science developer. I had done Data Science course from TGC India. They offer a variety of tutorials covering everything from the processes of Data Science to how to get started with Data Science.

Avatar_small
ok토토먹튀검증 说:
2024年2月18日 15:56

his is my first time i visit here. I found so many entertaining stuff in your blog, especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the leisure here! Keep up the good work. I have been meaning to write something like this on my website and you have given me an idea.

Avatar_small
파워볼사이트 说:
2024年2月18日 15:58

Great blog found to be well written about Express computers and it’s utilization in various domains more importantly in name of Data science and Machine learning that everyone will understand and gain the enough knowledge from your blog being more informative is an added advantage for the users who are going through it. Once again nice blog keep it up.

Avatar_small
토토사이트모음 说:
2024年2月18日 15:58

Thanks for writing such a lovely and informative post for us. Now I will keep visiting your blog at regular intervals. And also I want to request you to write more such posts in the future, so that I can refer my more friends to visit on your blog. Keep Blogging!!!

Avatar_small
우리카지노 说:
2024年2月18日 15:58

Controlled works inside theories involving finances along with credit, good specification in the research subject, are characterized to get many-sided along with many-leveled.

Avatar_small
바카라게임 说:
2024年2月18日 16:31

his is my first time i visit here. I found so many entertaining stuff in your blog, especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the leisure here! Keep up the good work. I have been meaning to write something like this on my website and you have given me an idea.

Avatar_small
카지노큐 说:
2024年2月18日 16:32

Wow! This could be one particular of the most beneficial blogs We’ve ever arrive across on this subject. Actually Great. I’m also a specialist in this topic therefore I can understand your hard work.

Avatar_small
카지노 说:
2024年2月18日 16:32

These are all really solid tips. I can’t tell you how often I see a comment on one of the blogs I write for that amounts to “nice post” and nothing more. I’ve even worked at a couple of sites that delete comments that don’t add to the discussion!

Avatar_small
토토시대 说:
2024年2月18日 17:10

Great blog found to be well written about Express computers and it’s utilization in various domains more importantly in name of Data science and Machine learning that everyone will understand and gain the enough knowledge from your blog being more informative is an added advantage for the users who are going through it. Once again nice blog keep it up.

Avatar_small
토토24 说:
2024年2月18日 17:10

Your blog is very helpful for beginners who want to learn Data science. I am also a Data science developer. I had done Data Science course from TGC India. They offer a variety of tutorials covering everything from the processes of Data Science to how to get started with Data Science.

Avatar_small
먹튀사이트 说:
2024年2月18日 17:42

Your blog is very helpful for beginners who want to learn Data science. I am also a Data science developer. I had done Data Science course from TGC India. They offer a variety of tutorials covering everything from the processes of Data Science to how to get started with Data Science.

Avatar_small
메이저놀이터 说:
2024年2月18日 17:43

I’d also like to state that most of those that find themselves without the need of health insurance are normally students, self-employed and those that are jobless. More than half from the uninsured are under the age of Thirty five. They do not sense they are in need of health insurance since they are young along with healthy. Their income is normally spent on real estate, food, and also entertainment. Some people that do represent the working class either whole or not professional are not given insurance by means of their jobs so they go without because of the rising valuation on health insurance in america. Thanks for the tips you discuss through your blog.

Avatar_small
사설토토 说:
2024年2月18日 17:43

It's my first time here. I found this board and found it really helpful and it helped me out a lot. I want to give something back and help others like you helped me.

Avatar_small
토토사이트검증 说:
2024年2月18日 17:45

I thought it was heading to become some dull previous publish, however it truly compensated for my time. I’ll publish a hyperlink to this web page on my blog. I am positive my visitors will uncover that extremely helpful.

Avatar_small
메이저놀이터 说:
2024年2月18日 17:45

There are certainly a lot of details like that to take into consideration. That is a great point to bring up. I offer the thoughts above as general inspiration but clearly there are questions like the one you bring up where the most important thing will be working in honest good faith. I don?t know if best practices have emerged around things like that, but I am sure that your job is clearly identified as a fair game. Both boys and girls feel the impact of just a moment’s pleasure, for the rest of their lives.

Avatar_small
온라인카지노순위 说:
2024年2月18日 18:00

They Have Been In This Requiring Some Undertaking. In this way, They Respect The Attitude And Need Of Their Clients In a Clear Manner. . These Call Young women Respect That Different Clients Are Ensured Going To Have Different Systems.

Avatar_small
스포츠토토 说:
2024年2月18日 18:53

Hi there! Nice material, do keep me posted when you post something like this again! I will visit this blog leaps and bounds for more quality posts like it. Thanks.

Avatar_small
먹튀검증커뮤니티 说:
2024年2月18日 18:54

Definitely believe that which you said. Your favorite justification appeared to be on the net the simplest thing to be aware of. I say to you, I certainly get annoyed while people consider worries that they plainly don’t know about. You managed to hit the nail upon the top and defined out the whole thing without having side-effects , people can take a signal. 

Avatar_small
메이저놀이터 说:
2024年2月18日 18:54

Awesome blog! Do you have any tips and hints for aspiring writers? I’m planning to start my own website soon but I’m a little lost on everything. Would you propose starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m totally overwhelmed .. Any recommendations? Many thanks! 

Avatar_small
카지노사이트목록 说:
2024年2月18日 19:17

Nice to be visiting your blog once more, it has been months for me. Well this article that ive been waited for therefore long. i want this article to finish my assignment within the faculty, and it has same topic together with your article. Thanks, nice share.

Avatar_small
메이저토토사이트 说:
2024年2月18日 19:53

Sir, I've read your article entirely and I greatly admire it. It is one of the most useful blogs I have found. I'm eager to read more of your blog posts. Here is a post that you should read where you can learn about Morse code. The Morse code was developed so that operators could translate the indentations marked on the paper tape into text messages. Please refer to the article to learn more about

Avatar_small
แนะนำ เว็บบาคาร่า 说:
2024年2月18日 19:53

Your posts are neatly organized with the information I want, so there are plenty of resources to reference. I bookmark this site and will find your posts frequently in the future. Thanks again ^^

Avatar_small
먹튀검증사이트 说:
2024年2月18日 19:55

I'm really getting a charge out of exploring your carefully made articles. It seems like you consume a great deal of energy. I'm most certainly burnt out on battling to track down pertinent and astute editorial regarding this matter. I think this is the most reasonable point of view for doing it when in doubt. I think this is the most reasonable viewpoint for doing it, truth be told.

Avatar_small
먹튀사이트 说:
2024年2月18日 21:08

I'm really getting a charge out of exploring your carefully made articles. It seems like you consume a great deal of energy. I'm most certainly burnt out on battling to track down pertinent and astute editorial regarding this matter. I think this is the most reasonable point of view for doing it when in doubt. I think this is the most reasonable viewpoint for doing it, truth be told.

Avatar_small
먹튀사이트 说:
2024年2月18日 21:08

I spend time people’s writing. It has the excellent to consider you demonstrate around thoughts together with the intellect and also res while doing this very important topic is sometimes successfully deemed.

Avatar_small
seo service UK 说:
2024年2月24日 15:36

The writer is enthusiastic about purchasing wooden furniture on the web and his exploration about best wooden furniture has brought about the arrangement of this article


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1