luogu1955 [NOI2015] 程序自动分析

题目大意

　　假设x1,x2,x3...代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。i,j<=1000000000, n<=1000000

思路

　　如果把所有相等的变量纳为一个或几个集合，那么输出yes当且仅当同一个相等集合中不存在一对xi,xj被要求不相等。集合→并查集。i,j,n的范围→离散化。

离散化的标准做法

功能

　　将离散的数据压缩到一个有限的区间处理。具体可以为输入一个数的下标，输出该下标的排名。

实现

　　将原始下标排序，得到一个下标为原始下标排名顺序、值为原始下标的数组。然后我们就可以运用LowerBound二分由原始下标找到其在原数组中的位置了。

注意事项

并查集

一开始所有节点的Father都是自己。
Join两个节点是将一个节点的Root的Father设为另一个节点的Root，而不是将节点的Father设为另一个节点。

整体

如果只想得到70分的话，注意下标范围是多于N的，所以并查集中的N都应当设为1000000。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <cstdlib>

using namespace std;

const int MAX_N = 200010;

struct Discret

{

private:

    int SortedA[MAX_N];

    int Rank[MAX_N];

    int N;

    int LowerBound(int *a, int l, int r, int k)

    {

        while (l < r)

        {

            int mid = (l + r) / 2;

            if (k <= SortedA[mid])

                r = mid;

            else

                l = mid + 1;

        }

        return l;

    }

public:

    void Init(int n, int *a)

    {

        N = n;

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

            SortedA[i] = a[i];

        sort(SortedA + 1, SortedA + n + 1);

        int prevVal = 0, rankCnt = 0;

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

        {

            if (SortedA[i] != prevVal)

            {

                Rank[i] = ++rankCnt;

                prevVal = SortedA[i];

            }

            else

                Rank[i] = rankCnt;

        }

    }

    int GetRank(int val)

    {

        return Rank[LowerBound(SortedA, 1, N, val)];

    }

}List;

struct UnionFind

{

private:

    struct Node

    {

        Node *Father;

    }_nodes[MAX_N];

    Node *GetRoot(Node *cur)

    {

        return cur->Father == cur ? cur : cur->Father = GetRoot(cur->Father);

    }

public:

    void Init(int n)

    {

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

            _nodes[i].Father = _nodes + i;

    }

    bool SameRoot(int a, int b)

    {

        Node *root1 = GetRoot(_nodes + a);

        Node *root2 = GetRoot(_nodes + b);

        return root1 == root2;

    }

    void Join(int a, int b)

    {

        GetRoot(_nodes + a)->Father = GetRoot(_nodes + b);

    }

}G;

int main()

{

#ifdef _DEBUG

    freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

    static vector< pair<int, int> > equal, nequal;

    static int OrgVal[MAX_N];

    int caseCnt;

    scanf("%d", &caseCnt);

    while (caseCnt--)

    {

        equal.clear();

        nequal.clear();

        int n;

        scanf("%d", &n);

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

        {

            int x1, x2, isEqual;

            scanf("%d%d%d", &x1, &x2, &isEqual);

            if (isEqual)

                equal.push_back(pair<int, int>(x1, x2));

            else

                nequal.push_back(pair<int, int>(x1, x2));

            OrgVal[i * 2 - 1] = x1;

            OrgVal[i * 2] = x2;

        }

        List.Init(n * 2, OrgVal);

        G.Init(n * 2);

        for (int i = 0; i < equal.size(); i++)

        {

            int rank1 = List.GetRank(equal[i].first), rank2 = List.GetRank(equal[i].second);

            if (!G.SameRoot(rank1, rank2))

                G.Join(rank1, rank2);

        }

        bool Ok = true;

        for (int i = 0; i<nequal.size(); i++)

        {

            int rank1 = List.GetRank(nequal[i].first), rank2 = List.GetRank(nequal[i].second);

            if (G.SameRoot(rank1, rank2))

            {

                Ok = false;

                break;

            }

        }

        if (Ok)

            printf("YES\n");

        else

            printf("NO\n");

    }

    return 0;

}

巴特西

luogu1955 [NOI2015] 程序自动分析

题目大意

思路

离散化的标准做法

功能

实现

注意事项

并查集

整体

最新文章

热门文章