百度之星2018复赛 1003.带劲的and和

Accepts: 791 Submissions: 2435
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

Problem

Description

度度熊专门研究过“动态传递闭包问题”,他有一万种让大家爆蛋的方法;但此刻,他只想出一道简简单单的题——至繁,归于至简。

度度熊有一张n个点m条边的无向图,第$i$个点的点权为$v_i$。

如果图上存在一条路径使得点i可以走到点j,则称i,j是带劲的,记$f(i,j)=1$;否则$f(i,j)=0$。显然有$f(i,j) = f(j,i)$。

度度熊想知道求出:$\sum ^{n-1}{i=1} \sum^{n}{j=i+1} f(i, j) \times \max(v_i, v_j) \times (v_i \& v_j)$

这里是只喵QAQ

其中$\&$是C++中的and位运算符,如$1 \& {3}=1, 2 \& 3=2$。

请将答案对$10^9+7$取模后输出。

Input

第一行一个数,表示数据组数TT。

每组数据第一行两个整数n,m;第二行n个数表示$v_i​$;接下来mm行,每行两个数u,v,表示点u和点v之间有一条无向边。可能有重边或自环。

数据组数T=50,满足:

  • $1 \le n,m \le 100000$
  • $1 \le v_i \le 10^9$

其中90%的数据满足$n,m \le 1000$

Output

每组数据输出一行,每行仅包含一个数,表示带劲的and和。

Sample Input

1
2
3
4
5
6
7
8
1
5 5
3 9 4 8 9
2 1
1 3
2 1
1 2
5 2

Sample Output

1
99

Solution

先放下官方题解吧

比较简单的数据结构题,需要掌握位运算每一位是独立的性质,难度3分。

因为是无向图,所以有f(i,j) = f(j,i)f(i,j)=f(j,i),不妨用并查集得到图上各个连通块,连通块中每对点的ff均为1,而不同连通块的点对互不影响。

求和的式子中有$\max$一项,不妨对于每个联通块中的点,将它们的权值vv从小到大排序,这样枚举到一个点,计算它和前面点之间的贡献时,$\max$就是当前点的权值。

还需要处理\&&运算符,这是一个经典的套路,只需要对于二进制的每一位统计出有多少个点在这一位上是1,对于每一位分开计算贡献即可。举个例子,如果要计算权值11和权值7的贡献,则有

$max(7,11) \times (7 \& 11) = 11 \times ((1 + 2 + 4) \& (1 + 2 + 8)) = 11 \times 1 + 11 \times 2$

复杂度为$O(n \log n + n \times 30)$,因为二进制位有30个。

并查集和排序自己想到了,但按位的操作自己没有见过,这次也算是见识到了。

用一个dp数组记录下比它小的数字该位有多少个1就吼惹。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+7;
#define LL long long int
const LL mod=1e9+7;
vector<int>ufs[MAXN];
int fa[MAXN];
LL w[MAXN];
int n;
int u_find(int p)
{
while(p!=fa[p])
{
fa[p]=fa[fa[p]];
p=fa[p];
}
return p;
}

void ufsunion(int x, int y)
{
x=u_find(x);
y=u_find(y);
if(x==y)
return;
else
{
fa[y]=x; //提交的代码没用ufs路径优化
}
}
int main()
{
int T,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0; i<=n; i++)
ufs[i].clear();
for(int i=0; i<n; i++)
scanf("%I64d",&w[i]);
for(int i=0; i<=n; i++)
fa[i]=i;
int u,v;
for(int i=1; i<=m; i++)
{
scanf("%d%d",&u,&v);
u--,v--;
ufsunion(u,v);
}
LL ans=0;
for(int i=0; i<n; i++)
ufs[u_find(i)].push_back(w[i]);
for(int i=0; i<n; i++)
{
if(ufs[i].empty())
continue;
sort(ufs[i].begin(),ufs[i].end());
}
int dp[32];
for(int i=0; i<n; i++)
{
memset(dp,0,sizeof(dp));
int len=ufs[i].size();
for(int j=0; j<len; j++)
{
LL it=ufs[i][j];
for(int j=0; j<30; j++)
{
if(it&(1<<j))
{
ans=(ans+(1LL*it*dp[j]%mod)*(1<<j))%mod; //计算当前数字每一位的贡献
dp[j]++; //更新该位1的个数
}
}
}
}
printf("%I64d\n",ans);
}
}
❤采之欲遗谁,所思在远道。❤
0%