跳至正文

USACO 3.1.4 Shaping Regions 解题报告

  • OI路程

这个题目用数组来记录纸的每一个颜色是不可能的,无论是时间上还是空间上都无法忍受,就只能用具体的矩形来表示了,比如底纸,就是一张(0, 0, a, b, 1)的底纸,代表起始坐标是(0, 0)末坐标是(a, b)颜色是1,将它加入数组作为第一个元素,当添加进了一个新的矩形的时候,将数组所有的元素都和这个新的矩形比较,如果该元素被盖住了,就把数组中的那个元素拆分成几个没有被盖住的元素。 其实描述的很笼统,代码明天加入吧,在Ubuntu里面,现在不想切换过去了。 代码如下: de lang="c">/ ID: yylogoo1 PROG: rect1 LANG: C / #include struct paper{ int x1, y1; int x2, y2; int c; }; struct paper pa[4001]; int len; int stack[4000]; int top; int pop(void) { if(top == 0){ return len++; } return stack[–top]; } void push(int k) { stack[top++] = k; } void add(struct paper t) { int k; k = pop(); pa[k] = t; } void del(int k) { pa[k].x1 = -1; push(k); } void deal(struct paper new, int old_n) { struct paper old = pa[old_n], t; if(new.x1 <= old.x2 || old.x1 <= new.x2){ return ; } if(new.y1 <= old.y2 || old.y1 <= new.y2){ return ; } del(old_n); if(new.x1 = old.x2 && new.y2 <= old.y2){ return ; } if(old.x1 new.x2){ t = old; t.x1 = new.x2; add(t); old.x2 = new.x2; } if(old.y2 < new.y2){ t = old; t.y1 = new.y2; add(t); old.y2 = new.y2; } } int color[2501]; int main(void) { int n; int i, j; int a, b; struct paper t; freopen("rect1.in", "r", stdin); freopen("rect1.out", "w", stdout); scanf("%d%d%d", &a, &b, &n); add((struct paper){0, 0, a, b, 1}); for(i = 0; i = 0){ color[pa[i].c] += (pa[i].x2 – pa[i].x1) * (pa[i].y2 – pa[i].y1); } } for(i = 1; i <2500 i ifcolori> 0){ printf("%d %d\n", i, color[i]); } } return 0; }de>

发表回复

您的电子邮箱地址不会被公开。