竞赛讨论区 > 牛客网-----------疏密度解题报告
头像
兴安真人
编辑于 2018-10-24 08:59
+ 关注

牛客网-----------疏密度解题报告

牛客网------------------疏密度解题报告

本题有创意,很好的题目!


先把问题分解一下:

如果没有绝对值?

5     2     和=7

3     7     和=10

1     9     和=10

计算任何2行的差,然后求和的最大值? 这问题简单吧?

就变成了每行求和,然后找出最大值和最小值,计算差就行了O(n)复杂度!

上面的行中 最大10,最小7,所以10-7=3就是答案。

-------------------以上是C 语言的题----------------------------

这题变成各项相减后,取绝对值,再相加!

5      2

3      7

就说这2行,请大家耐心看完!

5      2

3      7  第1行减去第2行后:

变成:

2       |-5|    和=7

就是 2 5

对于第2列: 如果是-2  +7 就对了

这就产生大小的对比关系:

1    0

0     1       1表示每两行大小关系,大的为1

对于1的值就是+号,0的值就是-号,

所以上面的2行变成:

5 -2

-3 7

这里就没有减法了,计算2行的和!

5+-2+-3+7=7(和)

变成了计算任意2行和的最大值

1  0

0 1 只是其中一种变化!

----------------------------------接上一页---------------------------------

1  0    0

0  1     1 也是

0      1

1      0 也是

也就是2个取反的2进制所对应的元素和就是最大值

对于每一行来说:如果有2列的话, 有00    01   10     11 (对应0,1,2,3);

计算a[i][0]    a[i][1]       a[i][2]      a[i][3] 的值(就是和,1就加,0就减)

I代表行号

计算完这些行后,要找出 a[i][0]最大值,a[i][1]的最大值,a[i][2]的最大值和a[i][3]的最大值;

也就是a[i][00]   a[i][01]  a[i][10]  a[i][11] 最大值;

[00]的最大值,[01]的最大值,[10]的最大值,[11]的最大值都存到a[1][0],a[1][1],a[1][2]a[1][3]里;

然后a[1][0]a[1][3]是一对, 0  0 的补是1   1;

然后a[1][1]a[1][2]是一对, 0  1 的补是 1    0;

计算max(a[1][0]+a[1][3],a[1][1]+a[1][2])

如何计算二进制补: ~j是不对的!

01 的补是 10  ,但前提是k=2,2

k=3 3列时,01的补其实对应001的补=110,所以 j^111才是正确的(k=3

j^11111(k=5)

说得够详细了吧

本题卡cincout ,必须scanf 才能过!

这题并查集没啥大关系

#include <iostream>

#include <stdio.h>

using namespace std;

const int N=1e5+5;

typedef long long LL;

LL a[N][10],b[N][1<<5],ans=-9999999;

int c[N];

int kk;

int n,k,m;

LL max1(LL x,LL y)

{

if (x<y) return y;

else

return x;

}

int find(int x)

{

if (x==c[x]) return x;

c[x]=find(c[x]);

return c[x];

}

int join(int x,int y)

{

int x1=find(x);

int y1=find(y);

if (x1==y1) return 0;

c[y1]=x1;

for(int i=0;i<=kk;i++)

{

b[x1][i]=max1(b[x1][i],b[y1][i]);

}

return 0;

}

int main()

{

int p1,p2,p3;

scanf("%d%d%d",&n,&k,&m);

kk=(1<<k)-1;

for(int i=1;i<=n;i++)

for(int j=1;j<=k;j++)

scanf("%lld",&a[i][j]);

for(int i=1;i<=n;i++)

for(int j=0;j<=kk;j++)

for(int p=0;p<k;p++)

{

if (j&(1<<p))

b[i][j]+=a[i][p+1];

else

b[i][j]-=a[i][p+1];

}

for(int i=1;i<=n;i++) c[i]=i;

for(int i=1;i<=m;i++)

{

scanf("%d",&p1);

if (p1==1)

{

scanf("%d%d",&p2,&p3);

join(p2,p3);

}

if (p1==2)

{  ans=-999999999;

scanf("%d",&p2);

int tp=find(p2);

for(int j=0;j<=kk;j++)

ans=max1(ans,b[tp][j]+b[tp][j^kk]);

printf("%lld\n",ans);

}

}

return 0;

}




全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐