Transform

传送门:Transform

题意:

题意:t 组数据,每组给出 n 个数与 m 组询问,每组询问有 s、t 两个数,对于数 s 现给出两种变换,一种是改变 s 二进制位的某一位,即 0 变 1 或 1 变 0,另一种是让 s 从给出 n 个数当中的任意一个做异或运算,问从 s 到 t 最少要经过几步变换,最后输出每组的组号 i 与该组答案 zi 的和(模 1E9+7)

思路:假设 s^x^y^z^w^...^q=t 是最小操作次数,由于其等价于 0^x^y^z^w^...^q=s^t,因此只需要根据所给的 n 个数将 1E5 范围内的所有步数求出来存到 res[] 数组中,最后根据 s、t 的值直接可以得到 res[s^t] 然后进行计算即可。

 

#include<iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 4e4;
const int mod = 1e9 + 7;
int step[maxn];
int arr[20];
int n, m;
void bfs() {
  memset(step, 1, sizeof(step));
  priority_queue <int> que;
  que.push(step[0] = 0);
  while (!que.empty()) {
    int now = que.top();
    que.pop();
    for (int i = 0; i < n; i++) {
      if (step[now^arr[i]] > step[now] + 1) {
        step[now^arr[i]] = step[now] + 1;
        que.push(now^arr[i]);
      }
    }
    for (int i = 0; i < 17; i++) {
      if (step[now ^ (1 << i)] > step[now] + 1) {
        step[now ^ (1 << i)] = step[now] + 1;
        que.push(now ^ (1 << i));
      }
    }
  }
}
int main() {
  int T; 
  cin >> T;
  while (T--) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
      cin >> arr[i];
    }
    bfs();
    int ans = 0;
    int x, y;
    for (int i = 1; i <= m; i++) {
      cin >> x >> y;
      ans = (ans + (step[x^y] * i) % mod) % mod;
    }
    cout << ans % mod << endl;
  }
  return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

14 − 6 =