其他.md

hash

迷一样的hash．．．．．

题目链接

2016　JAG E Similarity of Subtrees

分析

啊这位大佬的图非常到位

hash函数的定义方式是将深度为 $d$ 的顶点给一个权重$p^d$, 取　$p$ 为素数就好

AC code

const int  MOD = 1e9+7;
const int p = 19;
std::map<LL, int> ma;
LL hash_val[maxn];
std::vector<int> G[maxn];
void dfs(int u,int fa) {
    hash_val[u] =1;
    for(auto v: G[u]){
        if(v == fa)continue;
        dfs(v,u);
        hash_val[u] = (hash_val[u]+hash_val[v]*p) % MOD;
    }
    ma[hash_val[u]]++;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    for(int i=0 ; i<n-1 ; ++i){
        int u,v;
        cin>>u>>v;
        G[u].pb(v);G[v].pb(u);
    }
    dfs(1,-1);
    LL ans =0;
    for(auto e : ma){
        ans += (LL)e.se*(e.se -1)/2;
    }
    std::cout << ans << '\n';
    return 0;
}

二维离散化

分析

直接二维离散化,然后记录下各压缩了多少行和列，将其权值相乘便是离散化的图里的权重. dfs or bfs 统计一下就行了.

std::map<int, int> idx_x,idx_y;

LL vx[maxn],vy[maxn];
int a[maxn][maxn];
std::vector<LL> ans;
int x[maxn],y[maxn];

Pair bad[maxn];

int lishan(int * arr,int len, LL *val,std::map<int, int>& m ){
    m.clear();
    sort(arr,arr+len);
    len = unique(arr,arr+len)-arr;
    int t =1;
    val[t] = 1;
    m[arr[0]] = t++;
    for(int i=1 ; i<len ; ++i){
        if(arr[i]!=arr[i-1]+1)val[t++] = arr[i] - arr[i-1]-1;//补空白
        val[t] =1;m[arr[i]] = t++;
    }
    return t;
}
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};
int vis[maxn][maxn];
LL bfs(int i,int j) {
    queue<Pair> Q;
    Q.push(mp(i,j));
    vis[i][j] =1;
    LL cnt =0;
    while (!Q.empty()) {
        Pair p = Q.front();Q.pop();
        cnt += vx[p.fi] * vy[p.se];
        for(int i=0 ; i<4 ; ++i){
            int ni = p.fi + dx[i];
            int nj = p.se+dy[i];
            if(!a[ni][nj] && !vis[ni][nj]){
                vis[ni][nj] =1;
                Q.push(mp(ni,nj));
            }
        }
    }
    return cnt;
}


int main()
{
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    int T;
    cin>>T;

    for(int kase =1 ; kase <=T ; ++kase){
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=1 ; i<=k ; ++i){
            scanf("%d%d",&bad[i].fi, &bad[i].se );
            x[i] = bad[i].fi;y[i] = bad[i].se;
        }
        x[0] = 1;x[k+1] = n;
        y[0] = 1;y[k+1] = m;
        n = lishan(x,k+2,vx,idx_x);
        m = lishan(y,k+2,vy,idx_y);
        ms(a,0);
        for(int i=1;  i<=k ; ++i)a[idx_x[bad[i].fi]][idx_y[bad[i].se]] = 1;
        for(int i=0 ; i<=m ; ++i)a[0][i] = a[n][i] =1;
        for(int i=0 ; i<=n ; ++i)a[i][0] = a[i][m] =1;
        ms(vis,0);
        ans.clear();
        for(int i=1 ; i<n ; ++i){
            for(int j=1 ; j<m ; ++j){
                if(!a[i][j] && !vis[i][j])ans.pb(bfs(i,j));
            }
        }
        printf("Case #%d:\n",kase );
        sort(ans.begin(),ans.end());
        printf("%d\n",ans.size() );
        for(unsigned int i=0 ; i<ans.size() ; ++i){
            printf("%lld%c",ans[i],i==ans.size()-1?'\n':' ' );
        }
    }

    return 0;
}