牛客网------------------疏密度解题报告
本题有创意,很好的题目!
先把问题分解一下:
如果没有绝对值?
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)
说得够详细了吧
本题卡cin和cout ,必须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) 回帖