说起来好久没写题解了= =
上高中了码代码的时间都少了很多。。
链接http://codeforces.com/contest/432/problem/E
题目大意:
给你一个N*M的矩阵,要你用不同颜色正方形去覆盖,相邻的正方形颜色不能相同
颜色从A~Z,求字典序最小
具体的看样例应该能明白
只是来找题意的看到这就好了。。。
题解(我的做法):贪心
n*m枚举,找到空着的点开始放
判断下这个点最小能放什么
枚举下边界
貌似效率有点萎= =(我不会算。。)
重点在于枚举边界的时候
首先判断边上相邻的有没有相同颜色的
开始我只想到这个,认为找到能放的颜色,尽量放面积大的正方形一定优
然后wa6。。。
后来想到。。
假设当前这个能放的是C
横着过去的某一格能放A了
那么显然放A会更优
而不是把C的面积一直扩大
AAAA
AAAA
AAAA
AAAA
BBBB
BBBB
BBBB
BBBB
AACC
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格= =格式萎的话可以复制到别的地方看。。
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.