台湾菜

HDOJ 1199 Color the Ball

twcai • acm/icpc

HDOJ 1199
  这题既可以用线段树解,也可以使用离散化。
  我决定使用离散化先做一遍,做题的过程中发现这题的细节还是蛮多的,需要仔细考虑。
  一开始我是把所有出现过的坐标都经过排序后离散化,然后再开数组模拟涂色过程,很快就发现这样不行。因为这样离散化后的两个连续点之间不一定实际连续,这样没没办法判断线段是否相连了。在借鉴了别人的做法后,我改写了程序,把黑色的涂色过程对它前面操作产生的影响先处理掉,然后再对白色进行合并。这里重点就是判断两条线段的相对关系,需要注意的是两条线段不重合但相邻的情况,我发现了这个问题,才在ZOJ上AC,但是HDOJ上还是继续WA。
  最后我在涂白的线段合并的二重循环由原来的

for(i = 0; i < m; i++){
if(op[i].l == -1)
continue;
for(j = i + 1; j < m; j++)
{
.
}
}

改成了

for(i = 0; i < m; i++){
if(op[i].l == -1)
continue;
for(j = 0; j < i; j++)
{
.
}
}

以后终于AC。但是原因我还是不明白……我个人感觉没什么影响……晚上继续想吧。
贴下代码:
#include
#include
using namespace std;

struct operation
{
int l, r, c;
};

operation op[10010], od[2010];

int main()
{
int n, m;
int i, j;
char c[10];

while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i++)
{
scanf("%d %d %s", &od[i].l, &od[i].r, c);
od[i].c = c[0] == 'b' ? 0 : 1;
}
m = 0;
for(i = 0; i < n; i++)
{
if(od[i].c == 1){
op[m++] = od[i];
}
else{
for(j = 0; j < m; j++)
{
if(op[j].l < 0)
continue;
if(od[i].l <= op[j].l && od[i].r >= op[j].r)
op[j].l = -1;
else if(od[i].r >= op[j].l
&& od[i].r < op[j].r && od[i].l <= op[j].l)
op[j].l = od[i].r + 1;
else if(od[i].l > op[j].l
&& od[i].r >= op[j].r && od[i].l <= op[j].r)
op[j].r = od[i].l - 1;
else if(od[i].l > op[j].l && od[i].r < op[j].r)
{
op[m].r = op[j].r, op[m++].l = od[i].r + 1;
op[j].r = od[i].l -1;
}
}
}
}//处理至只剩下白色

if(m > 5000)
while(1);

bool fg = 1;
while(fg)
{
fg = 0;
for(i = 0; i < m; i++){
if(op[i].l == -1)
continue;
for(j = 0; j < i; j++)
{
if(i == j)
continue;
if(op[j].l == -1)
continue;
if(op[i].l <= op[j].l && op[i].r >= op[j].r){
op[j].l = -1;
fg = 1;
}
else if(op[i].l > op[j].l && op[i].r < op[j].r){
op[i].l = -1;
fg = 1;
}
else if(op[i].l <= op[j].l
&& op[i].r >= op[j].l -1 && op[i].r < op[j].r){
op[i].r = op[j].r, op[j].l = -1;
fg = 1;
}
else if(op[i].l > op[j].l
&& op[i].l <= op[j].r + 1 && op[i].r >= op[j].r){
op[i].l = op[j].l, op[j].l = -1;
fg = 1;
}
}
}
}

int ret = -1, np;
for(i = 0; i < m; i++)
{
if(op[i].l == -1)
continue;
if(op[i].r - op[i].l > ret){
ret = op[i].r - op[i].l;
np = op[i].l;
}
}
if(ret >= 0)
printf("%d %dn", np, np + ret);
else
printf("Oh, my godn");
}
return 0;
}

comments powered by Disqus