警示后人 WA on #7
查看原帖
警示后人 WA on #7
316358
不知名用户楼主2024/3/18 20:55

wrong answer 5162nd numbers differ - expected: '18', found: '10'。应该这种错误没有别的错法吧,如果有不同的错法欢迎评论。

原因:合并两个区间时,第一个区间最后的 or 值变化处后面可能还有一些数,但是你把它们忽略了,所以维护一段区间还要维护最大值。

核心部分:

AC:

struct arr
{
	int x[32], mx[32], len, m;
};
int a[N], b[N];
arr itoa(int x, int y){arr a;a.len = 1, a.mx[1] = a.m = x, a.x[1] = y;return a;}
arr operator + (arr a, const arr &b)
{
	int i, m = a.m;
	a.m = max(a.m,b.m);
	for(i=1;i<=b.len;i++) if((a.x[a.len]|b.x[i])!=a.x[a.len])
	{
		a.len++;
		a.x[a.len] = a.x[a.len-1] | b.x[i];
		m = a.mx[a.len] = max(m,b.mx[i]);
	}
	return a;
}

WA:

struct arr
{
	int x[32], mx[32], len;
};
int a[N], b[N];
arr itoa(int x, int y){arr a;a.len = 1, a.mx[1] = x, a.x[1] = y;return a;}
arr operator + (arr a, const arr &b)
{
	int i;
	for(i=1;i<=b.len;i++) if((a.x[a.len]|b.x[i])!=a.x[a.len])
	{
		a.len++;
		a.x[a.len] = a.x[a.len-1] | b.x[i];
		a.mx[a.len] = max(a.mx[a.len-1],b.mx[i]);
	}
	return a;
}
2024/3/18 20:55
加载中...