ACM学习历程—HDU5637 Transform（数论 && 最短路）

题目链接：http://codeforces.com/problemset/problem/590/A

题目大意是给两种操作，然后给你一个s，一个t，求s至少需要多少次操作到t。

考虑到第一种操作是将某一位取反，而第二种操作是抑或一个数。

显然第一种操作也是可以通过抑或一个数得到的。比如：第i位取反，相当于抑或(1<<i)这个数。于是就将n个数扩大到n+17就可以了，因为100000最多17位。

此外如果p^a^b^c...=q的话，那么a^b^c...=p^q。于是，只需要求出p^q至少需要几个数抑或而成就可以了。

然后跑一个类似于最短路就可以了，此处采用spfa。

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <vector>

#include <string>

#define LL long long

#define MOD 1000000007

using namespace std;

int n, m, a[];

int dis[];

bool vis[];

void input()

{

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

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

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

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

        a[i+n] = <<i;

    n += ;

    //spfa

    memset(dis, -, sizeof(dis));

    dis[] = ;

    memset(vis, false, sizeof(vis));

    vis[] = true;

    queue<int> q;

    q.push();

    int k, v, t;

    while (!q.empty())

    {

        k = q.front();

        q.pop();

        vis[k] = false;

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

        {

            v = k^a[i];

            if (dis[v] != - && dis[v] <= dis[k]+)

                continue;

            dis[v] = dis[k]+;

            if (!vis[v])

            {

                q.push(v);

                vis[v] = true;

            }

        }

    }

}

int main()

{

    //freopen("test.in", "r", stdin);

    int T;

    scanf("%d", &T);

    for (int times = ; times <= T; ++times)

    {

        input();

        int s, t;

        LL ans = ;

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

        {

            scanf("%d%d", &s, &t);

            ans += (LL)i*dis[s^t];

            ans %= MOD;

        }

        cout << ans << endl;

    }

    return ;

}

巴特西

ACM学习历程—HDU5637 Transform（数论 && 最短路）

最新文章

热门文章