hdu 5637 BestCoder Round #74 (div.2)

时间：2023-03-09 14:38:47
hdu 5637 BestCoder Round #74 (div.2)

Transform

 Accepts: 7
 Submissions: 49
 Time Limit: 4000/2000 MS (Java/Others)
 Memory Limit: 131072/131072 K (Java/Others)
问题描述
给出nn个整数, 对于一个整数xx, 你可以做如下的操作若干次:

  + 令xx的二进制表示为\overline{b_{31}b_{30}...b_0}​b​31​​b​30​​...b​0​​​​​, 你可以翻转其中一个位.

  + 令yy是给出的其中一个整数, 你可以把xx变为x \oplus yx⊕y, 其中\oplus⊕表示位运算里面的异或操作.

现在有若干整数对(S, T)(S,T), 对于每对整数你需要找出从SS变成TT的最小操作次数.
输入描述
输入包含多组数据. 第一行有一个整数TT (T \le 20)(T≤20), 表示测试数据组数. 对于每组数据:

第一行包含两个整数nn和mm (1 \le n \le 15, 1 \le m \le 10^5)(1≤n≤15,1≤m≤10​5​​), 表示给出整数的数目和询问的数目. 接下来一行包含nn个用空格分隔的整数a_1, a_2, ..., a_na​1​​,a​2​​,...,a​n​​ (1 \le a_i \le 10^5)(1≤a​i​​≤10​5​​).

接下来mm行, 每行包含两个整数s_is​i​​和t_it​i​​ (1 \le s_i, t_i \le 10^5)(1≤s​i​​,t​i​​≤10​5​​), 代表一组询问.
输出描述
对于每组数据, 输出一个整数S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)S=(​i=1​∑​m​​i⋅z​i​​) mod (10​9​​+7), 其中z_iz​i​​是第ii次询问的答案.
输入样例
1

3 3

1 2 3

3 4

1 2

3 9
输出样例
10
Hint
3 \to 43→4 (2次操作): 3 \to 7 \to 43→7→4

1 \to 21→2 (1次操作): 1 \oplus 3 = 21⊕3=2

3 \to 93→9 (2次操作): 3 \to 1 \to 93→1→9
/*

hdu 5637	

给你n个数，然后对于x有两种操作：

1.改变x二进制中的一位，即1->0 or 0->1

2.将x与n个数中的t异或得到 x^t

求最后得到y的最小操作数

最开始想到求出x^y，但是不知道怎么处理。如果每个询问都进行一次搜索的话感觉

会TLE,为什么就没想到预处理出来- -！

正解：

先把上面两种操作得到所有情况求出来，然后从x->y也就是异或上(x^y)，而这个值

的最小步数已经处理出来，直接进行O(1)的查询即可

hhh-2016-03-06 12:12:08

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <map>

#include <queue>

#include <algorithm>

using namespace std;

typedef long long ll;

#define LL(x) (x<<1)

#define RR(x) (x<<1|1)

#define MID(a,b) (a+((b-a)>>1))

const int maxn=100500;

const int MOD = 1e9+7;

int a[maxn];

int step[maxn<<2];

int tp[maxn<<2];

int y,n;

int ans ;

void bfs()

{

    memset(step,-1,sizeof(step));

    int star = 0,tail = 0;

    tp[0] = 0,step[0] = 0;

    while(star <= tail)

    {

        int cur = tp[star];

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

        {

            int t = cur^a[i];

            if(step[t] != -1)

                continue;

            tp[++tail] = t;

            step[t] = step[cur]+1;

        }

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

        {

            int t = cur^(1<<i);

            if(step[t] != -1)

                continue;

            tp[++tail] = t;

            step[t] = step[cur]+1;

        }

        star++;

    }

    return ;

}

int main()

{

    int t,q;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&q);

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

        {

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

        }

        bfs();

        int x,y;

        ll sum = 0;

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

        {

            scanf("%d%d",&x,&y);

            int ans = step[x^y];

            sum = (sum+(ll)(i*ans)%MOD)%MOD;

        }

        printf("%I64d\n",sum%MOD);

    }

    return 0;

}

　　

相关文章