编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 291ms

├ 测试数据 10：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：616ms

第10个...在tangky的教导下A了...

既然楼下的解题报告都很简略。。。我来写个详细的吧。。。(tangky表BS我)

Orz 教主 非常简略 一针见血

让我们先考虑一维:

一维很简单,只要找最大最小一减即可;

接着来考虑二维:

考虑两个点xi,yi,xj,yj

其曼哈顿距离为|xi-xj|+|yi-yj|

我们把绝对值去掉

得到四个式子

xi-xj+yi-yj

xj-xi+yi-yj

xi-xj+yj-yi

xj-xi+yj-yi

这里面的最大值是否有变化呢？显然没有！

因此,把一个曼哈顿距离公式中的所有绝对值去除,每个点得到2^k个一维坐标,距离最大值是不会变的。

比如说样例:

4 2

2 1

1 4

4 5

5 3

二维有四种情况

-x y

x -y

-x -y

x y

分别变成:

2 1：-1 1 -3 3

1 4：3 -3 -5 5

4 5：1 -1 -9 9

5 3：-2 2 -8 8

也就是说,同一状态的最大-最小得出的4个最大值：

5 5 6 6

其中的最大值为6,即为答案。

由于D

ORZ 玛维-影之歌！
看了他的题解觉得非常的神奇，仔细一推敲发现真的如此！
知道算法后题目就变得很简单了。
由于刚在转C++,写的不够地道，请谅解。

BY JSB 绍兴一中万岁！
#include<stdio.h>
using namespace std;
long a[33][100001];
long p[6];
long i,j,n,d,ans,min,max,now;
void make(long step,long s)
{
if (step-1==d) return;
if (step==d)
{
now++;a[now][i]=s+p[step];
now++;a[now][i]=s-p[step];
}
else
{
make(step+1,s+p[step]);
make(step+1,s-p[step]);
}
}
int main()
{
scanf("%ld %ld",&n,&d);
for (i=1;i<=n;i++)
{
for (j=1;j<d;j++)
scanf("%ld ",&p[j]);
scanf("%ld",&p[j]);
now=0;
make(1,0);
}
ans=0;
for (i=1;i<=now;i++)
{
max=-2000000000;min=-max;
for (j=1;j<=n;j++)
{
if (a[i][j]>max) max=a[i][j];
if (a[i][j]<min) min=a[i][j];
}
if (max-min>ans) ans=max-min;
}
printf("%ld",ans);
//scanf("%ld",&ans);
return 0;

}

貌似浙江省选的时候DHX和XCH都讲了下这题。可惜没听。

Orz 玛维 &TKy 神。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：144ms

我沙茶了。

一个数组应该开0..100001 的我开了0..5.。wa了N次.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

玛维-影之歌 orz!

var x:array[1..5,1..10000] of longint;

x1,y1:longint;

i,j,k,n,m,ans,ans1,ans2,cm:longint;

a:array[0..32,1..100000] of longint; {0:-,1:+}

function suan(x,j:longint):longint;

begin

suan:=(x>>(m-j))and 1;

if suan1 then exit(-1) else exit(1);

end;

begin

readln(n,m);

for i:=1 to n do

for j:=1 to m do

read(x[j,i]);

cm:=1 shl m-1;

for i:=0 to cm do

for j:=1 to n do

for k:=1 to m do

a:=a+suan(i,k)*x[k,j];

for i:=0 to cm do

begin

ans1:=-maxlongint;

ans2:=maxlongint;

for j:=1 to n do

begin

if ans1a then ans2:=a;

end;

if ans

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 134ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 259ms

├ 测试数据 08：答案正确... 291ms

├ 测试数据 09：答案正确... 947ms

├ 测试数据 10：答案正确... 791ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2659ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 41ms

强烈膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜

楼下的大牛。。。。。。

第27个···我最喜欢的数字，，抢到了真好。。

。。。我独立AC啦。。。

我想了半天一开始想仿照欧几里德距离的做法。。但搞不出来。。

然后想到拆绝对值。。于是灵光一闪。。。。

有个细节要注意就是计算每个状态的时候。要把Max设成-inf。。不能设成0.因为可能都是负的。。

很好 第23个AC

不得不说玛维的题解 太强悍了

我想破脑袋还没想出来的方法 一下就说明白了

晕.....................

无限佩服玛维与Tangky中.......

看了玛维的题解，感到很神奇。

为什么呢？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 9ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：128ms

第11个AC,纪念一下。

付神牛一出手,AC直线上升

哇.,...膜拜IOI2009金牌付神牛

膜拜ing

付神牛一次AC~将这道题AC率由50%+提高到了67%

哇.,...膜拜IOI2009金牌付神牛

哇.,...膜拜IOI2009金牌付神牛

这题ac率太猛了

Flag 　　

题号 　　P1453

类型(?) 　　数论 / 数值

通过 　　4人

提交 　　4次

通过率 　　100%

难度 　　3

把绝对值去掉取max

原题Ｎ最大有１００００００，因为ＶＪ承受不了７０ＭＢ＋的数据包

只能改成最大１０００００

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：222ms

过了YEAH

楼下太强了