UOJ#127. 【NOI2015】程序自动分析

100 阅读 0 评论 66 点赞

我是靠谱客的博主典雅饼干，最近开发中收集的这篇文章主要介绍UOJ#127. 【NOI2015】程序自动分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem : 程序自动分析
Description :

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 x1,x2,x3,…x1,x2,x3,… 代表程序中出现的变量，给定 nn 个形如 xi=xjxi=xj 或 xi≠xjxi≠xj 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2x1=x2，x2=x3x2=x3，x3=x4x3=x4，x1≠x4x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

Solution :

并查集+字典树HASH。这题一看就是要把相等的那些变量连接在一起，然后去查不相等的变量是否连接。并查集可以解决，但是这个题有 $n(n<100000)$ 个等式，却有 $m(m<1000000000)$ 个变量，那么这是一定要离散化的，离散化后最多 $2*n$ 个点。学习我上篇博客POJ2513 -Colored Sticks(The UofA Local 2000.10.14)字典树HASH的离散化方法，把输入的变量下表当成字符串处理，但是字典树用的动态的，没过，于是改成静态的，过了。后来我用map< int,int>离散化也过了，不过慢了一倍，于是我又用map< string,int>,这次超时了！看图：

分析用动态字典数不过的原因应该是字典树创建结点，而后有没有删除导致读取了脏数据。

因此得出结论
1. 不要用指针，能用静态用静态。
2. map处理string到int很慢，因此数据大的时候用字典树代替map。

Code(C++) :

#include <stdio.h>
#include <string.h>

#include <iostream>
#include <vector>

using namespace std;

const int MAXN=100000*2+50;

struct Node{
    int id;
    int next[10];
    Node(){
        id=-1;
        for(int i=0;i<10;i++)
            next[i]=-1;
    }
}points[MAXN*4];

int ID=0,Root,E;

int p[MAXN];
vector<pair<int,int> > lines;

int make(char str[])
{
    int p=Root;
    for(int i=0;str[i];i++){
        int pos=str[i]-'0';
        if(points[p].next[pos]==-1){
            points[p].next[pos]=E++;
        }
        p=points[p].next[pos];
    }
    if(points[p].id==-1)
        points[p].id=++ID;
    return points[p].id;
}

int find(int x)
{
    return x==p[x]? x:p[x]=find(p[x]);
}

int main()
{
    //freopen("in","r",stdin);
    int T;
    for(scanf("%d",&T);T--;){
        ID=0,Root=0,E=1;
        memset(points,-1,sizeof(points));
        for(int i=0;i<MAXN;i++)
            p[i]=i;
        lines.clear();
        char num1[15],num2[15];
        int e;
        int n;
        scanf("%d",&n);
        for(int L=0;L<n;L++){
            scanf("%s%s%d",num1,num2,&e);
            int id1=make(num1);
            int id2=make(num2);
            //printf("id1:%d id2:%dn",id1,id2);
            if(e==1){
                int tx=find(id1);
                int ty=find(id2);
                if(tx!=ty)
                    p[tx]=ty;
            }else{
                lines.push_back(make_pair(id1,id2));
            }
        }
        bool f=true;
        for(unsigned int i=0;i<lines.size();i++){
            int tx=lines.at(i).first;
            int ty=lines.at(i).second;
            if(find(tx)==find(ty)){
                f=false;
                break;
            }
        }
        puts(f? "YES":"NO");
    }
    return 0;
}