codeforces.com/contest/432/problem/E

10
14
2014

You have an n × m rectangle table, its cells are not initially painted. Your task is to paint all cells of the table. The resulting picture should be a tiling of the table with squares. More formally:

each cell must be painted some color (the colors are marked by uppercase Latin letters);
we will assume that two cells of the table are connected if they are of the same color and share a side; each connected region of the table must form a square.

Given n and m, find lexicographically minimum coloring of the table that meets the described properties.

Input

The first line contains two integers, n and m (1 ≤ n, m ≤ 100).

Output

Print lexicographically minimum coloring of the table that meets the described conditions.

One coloring (let's call it X) is considered lexicographically less than the other one (let's call it Y), if:

consider all the table cells from left to right and from top to bottom (first, the first cell in the first row, then the second cell in the first row and so on);
let's find in this order the first cell that has distinct colors in two colorings;
the letter that marks the color of the cell in X, goes alphabetically before the letter that marks the color of the cell in Y.

							Sample test(s)

									input
1 3

									output
ABA

									input
2 2

									output
AA
AA

									input
3 4

									output
AAAB
AAAC
AAAB

									 

说起来好久没写题解了= =

上高中了码代码的时间都少了很多。。

链接http://codeforces.com/contest/432/problem/E

题目大意：

给你一个N*M的矩阵，要你用不同颜色正方形去覆盖，相邻的正方形颜色不能相同

颜色从A~Z，求字典序最小

具体的看样例应该能明白

只是来找题意的看到这就好了。。。

题解（我的做法）：贪心

n*m枚举，找到空着的点开始放

判断下这个点最小能放什么

枚举下边界

貌似效率有点萎= =（我不会算。。）

重点在于枚举边界的时候

首先判断边上相邻的有没有相同颜色的

开始我只想到这个，认为找到能放的颜色，尽量放面积大的正方形一定优

然后wa6。。。

后来想到。。

假设当前这个能放的是C

横着过去的某一格能放A了

那么显然放A会更优

而不是把C的面积一直扩大

AAAA

BBBB

AACC

在倒数第二行的第4位

这个地方能放A

所以放A……

最后2行改成

AACA

AABC

这样就对了。。

简单说判断的时候

和当前点同一行的某个点

能放比当前点字典序小的字母

那么当前的正方形就不能覆盖到它

否则尽量扩大

好了帖代码。。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[105][105],b,c,d,e,f,g,h,i,j,k,l,m,n;
inline bool pd(int x,int y,int s)
{return a[x-1][y]==s||a[x+1][y]==s||a[x][y-1]==s||a[x][y+1]==s;}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)if(!a[i][j]){
		if(i==3&&j==21){
			k=1;
		}
		for(k=1;k<=26;k++)if(!pd(i,j,k)){
			for(l=1;l<=n;l++){
				if(i+l>n||j+l>m)break;
				d=0;
				for(g=j;g<=j+l;g++)
				if(a[i+l][g]||pd(i+l,g,k)){d=1;break;}
				if(d)break;
				for(g=i;g<=i+l;g++)
				if(a[g][j+l]||pd(g,j+l,k)){d=1;break;}
				if(d)break;
				for(g=1;g<k;g++)if(!pd(i,j+l,g))d=1;
				if(d)break;
			}
			l--;
			for(d=i;d<=i+l;d++)
			for(e=j;e<=j+l;e++)a[d][e]=k;
			break;
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)putchar(a[i][j]+'A'-1);
		printf("\n");
	}
	return 0;
}

现在喜欢Tab键开8格= =格式萎的话可以复制到别的地方看。。

Category: BZOJ | Tags: | Read Count: 827

[回复]

Dylan Alder 说:
2019年4月02日 15:00

Table about the new code for the context upon the all figure have to out now from the resulting time along with this. Must be have to describe the properties from the best assignment writing service uk with the few of the days while be catching to have formally standard.

sxczf's Blog

AFO

codeforces.com/contest/432/problem/E

分类

最新评论

最新留言

链接

功能