2020牛客暑期多校训练营（第七场）J- Pointer Analysis 暴力

J- Pointer Analysis

题意

给你(26)个全局指针(A,B,C,dots,Z)，(26)个对象(a,b,c,d,dots,z)，每个对象有(26)个成员指针，例如对象(a)有(a.a,a.b,dots.a.z)这(26)个成员指针。

有下面四种赋值语句：

• (A=x)，指针(A)指向对象(x)。
• (A=B)，将指针(B)赋值给指针(A)。
• (A.f=B)，将指针(B)赋值给指针(A)指向的所有对象的成员指针(f)。
• (A=B.f)，将指针(B)指向的所有对象的成员指针(f)赋值给(A)。

分析

根据赋值语句来迭代建图，对于前两个赋值语句我们直接建(A->x,A->B)的边，

对于(A.f=B)，找到(A)指向的所有对象(x)，建(x.f->B)的边，

对于(A=B.f)，找到(B)指向的所有对象(x)，建(A->x.f)的边，

然后(dfs)更新每个全局指针(A,B,dots,Z)可能指向的对象的集合，

只要上述操作能新增至少一条边，就重复上述过程，否则无法再更新答案。

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int n;
set<int>g[N],h[N];
struct ppo
{
    int x,y,z;
};
vector<ppo>a,b;
int vis[1010];
int id[222][222];
int ok;
void dfs(int u,int fa){
    if(vis[u]) return;
    vis[u]=1;
    for(int x:g[u]){
        dfs(x,fa);
        if(x>='a'&&x<='z'){
            auto it=g[fa].find(x);
            if(it==g[fa].end()){
                g[fa].insert(x);
                ok=1;
            }
        }
    }
}
int main(){
    //ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n;
    rep(i,1,n){
        char s[5],t[5];
        scanf("%s = %s",s,t);
        int l1=strlen(s),l2=strlen(t);
        if(l1==l2){
            g[s[0]].insert(t[0]);
        }else{
            if(l1>l2){
                a.pb(ppo{s[0],t[0],s[2]});
            }else{
                b.pb(ppo{s[0],t[0],t[2]});
            }
        }
    }
    int ba=127;
    for(int i='a';i<='z';i++) for(int j='a';j<='z';j++){
        id[i][j]=++ba;
    }
    ok=1;
    while(ok){
        ok=0;
        memset(vis,0,sizeof(vis));
        for(ppo it:a){
            for(int i='a';i<='z';i++) if(g[it.x].find(i)!=g[it.x].end()){
                if(g[id[i][it.z]].find(it.y)==g[id[i][it.z]].end()){
                    g[id[i][it.z]].insert(it.y);
                    ok=1;
                }
            }
        }
        for(ppo it:b){
            for(int i='a';i<='z';i++) if(g[it.y].find(i)!=g[it.y].end()){
                if(g[it.x].find(id[i][it.z])==g[it.x].end()){
                    g[it.x].insert(id[i][it.z]);
                    ok=1;
                }
            }          
        }
        for(int i='A';i<='Z';i++){
            memset(vis,0,sizeof(vis));
            dfs(i,i);
        }
    }
    rep(i,'A','Z'){
        printf("%c: ",i);
        rep(j,'a','z') if(g[i].find(j)!=g[i].end()){
            printf("%c",j);
        }
        puts("");
    }
    return 0;
}