The 18th Zhejiang Provincial Collegiate Programming Contest

D. Shortest Path Query(最短路)

类似二叉树的一个结构，考虑对每个点暴力其子树内的点跑最短路，

则每个点只会被祖先的logn个点遍历一遍，总点数是O(n(logn)^2)的

对于u、v来说，答案类似询问u、v的lca，枚举lca检查到u、v的最小值和即可

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
#define pb push_back
#define fi first
#define se second
const int N=1e5+10;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int s,t,n,m,Q,u,v,w,bit[N];
ll dis[N][18];
vector<P>e[N];
bool vis[N][18];
int main(){
    memset(dis,INF,sizeof dis);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        bit[i]=bit[i>>1]+1;
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        e[u].pb(P(v,w));
        e[v].pb(P(u,w));
    }
    for(int i=1;i<=n;++i){
        priority_queue<P>q;
        dis[i][0]=0;
        q.push(P(0,i));
        while(!q.empty()){
            int x=q.top().first,u=q.top().second;q.pop();
            int dep=0;
            for(int y=u;y!=i;y/=2)dep++;
            if(vis[u][dep])continue;
            vis[u][dep]=1;
            for(int j=0;j<e[u].size();++j){
                int v=e[u][j].first,w=e[u][j].second,nex=0;
                if(v>=i){
                    for(int y=v;y!=i;y/=2)nex++;
                    if(dis[v][nex]>dis[u][dep]+w){
                        dis[v][nex]=dis[u][dep]+w;
                        q.push(P(-dis[v][nex],v));
                    }
                }
            }
        }
    }
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&s,&t);
        ll now=2*INF;
        int ts=s,tt=t,nt=0,ns=0;
        if(bit[ts]>bit[tt])swap(ts,tt),swap(s,t);
        while(bit[tt]>bit[ts])tt/=2,nt++;
        while(tt!=ts){
            tt/=2,ts/=2;
            nt++,ns++;
        }
        while(1){
            now=min(now,dis[s][ns]+dis[t][nt]);
            if(ts==1)break;
            tt/=2,ts/=2;
            nt++,ns++;
        }
        printf("%lld\n",now>=INF?-1:now);
    }
    return 0;
}

I. Grammy and Ropes（思维题）

给你三个绳结，告诉六个蓝色的点处，是否编号大的圆在上(输入为6个true、false)

回答存在多少种不同的方案，使得3个环不存在两个绳结套在一起的情况

如果A在B上，B在C上，C在A上，三个圆会卡在一起，这个时候必须拆开至少一个绳结，7种方案

否则三者如果没出现两两套在一起的情况，说明8种方案都可；再否则，建图暴力删点来判断

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
#define pb push_back
char s[6][15];
bool ok[6],del[3];
int a[3][3],on[3][3],res,cnt;
vector<int>e[3];
void add(int u,int v){
    a[u][v]=a[v][u]=1;
    cnt++;
}
int main(){
    for(int i=0;i<6;++i){
        scanf("%s",s[i]);
        ok[i]=(strcmp(s[i],"true")==0);
    }
    if(ok[0]^ok[3])add(0,1);
    if(ok[1]^ok[4])add(0,2);
    if(ok[2]^ok[5])add(1,2);
    if(!cnt){
        int c=0;
        for(int i=0;i<3;++i){
            for(int j=i+1;j<3;++j){
                if(!ok[c])on[j][i]=1;
                else on[i][j]=1;
                c++;
            }
        }
        bool cyc=0;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                for(int k=0;k<3;++k){
                    if(i!=j && i!=k && j!=k && on[i][j] && on[j][k] && on[k][i]){
                        cyc=1;
                    }
                }
            }
        }
        printf("%d\n",cyc?7:8);
        return 0;
    }
    for(int i=1;i<8;++i){
        for(int j=0;j<3;++j){
            del[j]=i>>j&1;
        }
        bool ans=1;
        for(int j=0;j<3;++j){
            for(int k=j+1;k<3;++k){
                if(!del[j] && !del[k] && a[j][k])ans=0;
            }
        }
        res+=ans;
    }
    printf("%d\n",res);
    return 0;
}