头像

Haze

南京师范大学附属中学




离线:4小时前


活动打卡代码 AcWing 165. 小猫爬山

Haze
5天前
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int n=read(),w=read();
int a[88],used[88];
bool check(int d,int x){
    if(x==n+1)return true;
    for(int i=1;i<=d;++i){
        if(a[x]+used[i]<=w&&used[i-1]!=0){
            used[i]+=a[x];
            if(check(d,x+1))return true;
            used[i]-=a[x];
        }
    }
    return false;
}
int main(){
    used[0]=1;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=18;++i){
        if(check(i,1)){
            printf("%d",i);
            return 0;
        }
    }
}


活动打卡代码 AcWing 164. 可达性统计

Haze
5天前
#include<bits/stdc++.h>
using namespace std;
#define N 30099
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int d[N],tp[N],now,vis[N];
vector<int>g[N],G[N];
queue<int>s;
bitset<N>f[N];
int main(){
    int n=read(),m=read(),i;
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        g[u].push_back(v);
        G[v].push_back(u);
        d[u]++;
    }
    for(int i=1;i<=n;++i){
        if(d[i]==0)s.push(i);
    }
    while(s.size()){
        int u=s.front();
        vis[u]=1;
        s.pop();
        tp[++now]=u;
        for(int i=0;i<G[u].size();++i){
            int v=G[u][i];
    //      if(vis[v])continue;
            d[v]--;
            if(d[v]==0)s.push(v);
        }
    }
//  for(int i=1;i<=n;++i)f[i][i]=1;
    for(int i=1;i<=n;++i){
        int x=tp[i];
        f[x][x]=1;
        for(auto j:G[x]){
            f[j]|=f[x];
        }
    }
    for(int i=1;i<=n;++i){
        printf("%d\n",f[i].count());
    }
    return 0;
} 


活动打卡代码 AcWing 258. 石头剪子布

Haze
6天前
#include<bits/stdc++.h>
using namespace std;
char op;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   op=ch;
   return s*w;
}
int n,m,u[12000],v[12000],wl[12000];
int fa[100099];
int find(int x){
    if(x==fa[x])return fa[x];
    fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int check(int x){
    int ans,rd;
    for(int i=0;i<=n*3;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        if(u[i]==x||v[i]==x)continue;
        if(wl[i]==0){
            merge(u[i],v[i]);
            merge(u[i]+n,n+v[i]);
            merge(u[i]+n+n,n+n+v[i]);
        }
        if(wl[i]==1){
            merge(u[i],n+n+v[i]);
            merge(u[i]+n,v[i]);
            merge(u[i]+n+n,n+v[i]);         
        }
        if(wl[i]==-1){
            merge(u[i],n+v[i]);
            merge(u[i]+n,n+n+v[i]);
            merge(u[i]+n+n,v[i]);           
        }
        if(find(u[i])==find(u[i]+n)||find(u[i])==find(u[i]+n+n)||find(u[i]+n)==find(u[i]+n+n))return i;
        if(find(v[i])==find(v[i]+n)||find(v[i])==find(v[i]+n+n)||find(v[i]+n)==find(v[i]+n+n))return i;
    }
    return -1;
}
int main(){
    while(cin>>n>>m){
        int ans=0,cnt=0,r;
        for(int i=1;i<=m;++i){
            u[i]=read();
            if(op=='=')wl[i]=0;
            if(op=='>')wl[i]=1;
            if(op=='<')wl[i]=-1;
            v[i]=read();
        }
        for(int i=0;i<n;++i){
            int x=check(i);
            if(x==-1)++cnt,r=i;
            else ans=max(ans,x);
        }
        if(cnt==0){
            puts("Impossible");
        }
        if(cnt>1){
            puts("Can not determine");
        }
        if(cnt==1){
            printf("Player %d can be determined to be the judge after %d lines\n",r,ans);
        }
    }
    return 0;
} 


活动打卡代码 AcWing 356. 次小生成树

Haze
8天前

辣鸡写法,过不过得去看脸。

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define N 300099
#define inf 200000000000
#define fs first
#define sc second
using namespace std;
inline long long read(){
    long long s=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){
        s*=10,s+=ch-'0';
        ch=getchar();
    }
    return s;
}
pair<long long,pair<long long,long long> >e[N];
vector<long long>t[N],c[N];
long long n,m,cs[N],sum,ecnt,ans=inf;
long long fa[N][26],f[N][26][2],vis[N],dp[N];//0 max 1 second_max 
long long lca(long long x,long long y){
    if(dp[x]<dp[y])swap(x,y);
    for(long long i=23;i>=0;--i)
        if(dp[fa[x][i]]>=dp[y])
            x=fa[x][i];
    if(x==y)return x;
    if(dp[x]!=dp[y])x=fa[x][0];
    for(long long i=23;i>=0;--i){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i],y=fa[y][i];
        }
    }
    return fa[x][0];
}
long long Mxquery(long long u,long long v){
//  cout<<u<<' '<<v<<endl;
    long long a=0;
    if(dp[u]<dp[v])swap(u,v);
    for(long long i=24;i>=0;--i){
//      cout<<"A"<<' '<<a<<endl;
        if(dp[fa[u][i]]>=dp[v]){
//          cout<<"***ZA***"<<endl;
            a=max(a,f[u][i][0]);
            u=fa[u][i];
        }
    }
    return a;
}
long long mxquery(long long u,long long v){
    long long x=lca(u,v);
//  cout<<"LCA "<<v<<' '<<Mxquery(u,v)<<endl; 
    return max(Mxquery(u,x),Mxquery(v,x));
}
long long second_max(long long a,long long b,long long c,long long d){
    long long x[5]={a,b,c,d};
    sort(x,x+4);
    if(x[3]==x[2]){
        if(x[2]==x[1]){
            if(x[1]!=x[0])return x[0];
            return 0;
        }
        return x[1];
    }
    return x[2];
}
long long Smquery(long long u,long long v){
    if(dp[u]<dp[v])swap(u,v);
    long long maxans=1,secondmaxans=0;
    for(long long i=24;i>=0;--i){
        if(dp[fa[u][i]]>=dp[v]){
            maxans=max(maxans,f[u][i][0]);
            secondmaxans=second_max(maxans,secondmaxans,f[u][i][0],f[u][i][1]);
            u=fa[u][i];
        }
    }   
    return secondmaxans;
}
long long smquery(long long u,long long v){
    long long x=lca(u,v);
    return second_max(Mxquery(u,x),Mxquery(v,x),Smquery(u,x),Smquery(v,x));
}
struct U{
    long long fa[N];
    void reset(){
        for(long long i=1;i<=n;++i)fa[i]=i;
    }
    long long find(long long x){
        if(fa[x]==x)return x;
        fa[x]=find(fa[x]);
        return fa[x];
    }
    void merge(long long x,long long y){
        fa[find(x)]=find(y);
    }
}st;
void dfs(long long x,long long d){
    vis[x]=1;
    dp[x]=d;
    for(long long i=0;i<t[x].size();++i){
        long long u=t[x][i];
        if(vis[u])continue;
        fa[u][0]=x;
        f[u][0][0]=c[x][i];
    //  printf("f[%d][][]=%d\n",u,f[u][0][0]);
        dfs(u,d+1);
    }
}
int main(){
//  freopen("testdata.txt","r",stdin);
    n=read(),m=read();
    st.reset();
    for(long long i=1;i<=m;++i){
        long long u=read(),v=read(),z=read();
        if(u==v){
            --m;
            continue;
        }
        e[i]=make_pair(z,make_pair(u,v));
    }
    sort(e+1,e+m+1);
    for(long long i=1;i<=m&&ecnt<=n-1;++i){
        long long u=e[i].sc.fs,v=e[i].sc.sc,cost=e[i].fs;
        if(st.find(u)==st.find(v))continue;
        st.merge(u,v);
        ecnt++,sum+=cost,cs[i]=1;
        t[u].push_back(v);
        t[v].push_back(u);
        c[u].push_back(cost);
        c[v].push_back(cost);
    }
    dfs(1,0);
    fa[1][0]=1;
    for(long long i=1;i<=24;++i){
        for(long long j=1;j<=n;++j){
            fa[j][i]=fa[fa[j][i-1]][i-1];
        }
    }
    for(long long i=1;i<=24;++i){
        for(long long j=1;j<=n;++j){
            f[j][i][0]=max(f[j][i-1][0],f[fa[j][i-1]][i-1][0]);
        //  cout<<"FJI0"<<f[j][i][0]<<endl;
            f[j][i][1]=second_max(f[j][i-1][0],f[fa[j][i-1]][i-1][0],f[j][i-1][1],f[fa[j][i-1]][i-1][1]);
        }
    }
    for(long long i=1;i<=m;++i){
        if(cs[i]==0){
            long long w=e[i].fs;
            long long mx=mxquery(e[i].sc.fs,e[i].sc.sc),sm=smquery(e[i].sc.fs,e[i].sc.sc);
            if(w>mx)ans=min(ans,sum-mx+w);
            if(w==mx)ans=min(ans,sum-sm+w);
//          cout<<i<<' '<<mx<<' '<<sm<<endl;
        }
    }
//  for(long long i=1;i<=m;++i)cout<<e[i].fs<<' '<<e[i].sc.fs<<' '<<e[i].sc.sc<<' '<<cs[i]<<endl;
//  puts("");
    printf("%lld",ans);
    return 0;
}


活动打卡代码 AcWing 178. 第K短路

Haze
8天前
#include<bits/stdc++.h>
#define N 1009
#define M 100099
using namespace std;
int n,m,k,s,t;
vector<int>g[N],c[N];
int x[M],y[M],z[M];
int dis[N],f[N],vis[N],cnt[N];
priority_queue<pair<int,int> >q;
void dijkstra(int R){
    memset(dis,0x3f,sizeof(dis));
    dis[R]=0;
    q.push(make_pair(0,R));
    while(q.size()){
        int x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x]=true;
        for(int i=0;i<g[x].size();++i){
            dis[g[x][i]]=min(dis[g[x][i]],dis[x] + c[x][i]);
            q.push(make_pair(-dis[g[x][i]],g[x][i]));
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    if(m==0){
        puts("-1");
        return 0;
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
        g[y[i]].push_back(x[i]);
        c[y[i]].push_back(z[i]);
    }
    scanf("%d%d%d",&s,&t,&k);
    if(s==t)++k;
    dijkstra(t);
    swap(f,dis);
    for(int i=1;i<=n;++i)g[i].clear();
    for(int i=1;i<=n;++i)c[i].clear();
    for(int i=1;i<=m;++i){
        g[x[i]].push_back(y[i]);
        c[x[i]].push_back(z[i]);
    }
    q.push(make_pair(-f[s],s));
    while(cnt[t]<=k&&q.size()){
        int w=-q.top().first,u=q.top().second;
        q.pop();
        cnt[u]++;
        if(cnt[t]==k){
            printf("%d",w);
            return 0;
        }
        if(cnt[u]<=k){
            for(int i=0;i<g[u].size();++i){
                int v=g[u][i];
                q.push(make_pair(-(w-f[u]+f[v]+c[u][i]),v));
            }
        }
    }
    puts("-1");
    return 0;
}


活动打卡代码 AcWing 506. 货车运输

Haze
29天前

结论

感觉答案是最大生成树上路径 $u\to v$ 的最小的那条边 $(a,b)$ 的权。简要说明一下:

考虑 kruskal 算法建出的生成树。

假设存在一条比生成树上更优的路径 A,不妨假设这条路径上瓶颈边为 (a',b')。

我们会发现,在建树过程中 (a,b) 考虑的时间是在 A 上所有边之后的。

此时 u,v 早已联通,该边是不可能在生成树上的。与假设矛盾。

怎样算答案?

如果把边权最小值换为两点距离你肯定会做: LCA。

如果把树换成序列你肯定更会做: 倍增 (ST表)

那不就可以考虑倍增维护最小值吗?设 $f(u,i)$ 为 $u$ 向上跳 $2^i$ 次边权最小值,一边求 LCA 一边算最小值。

原图不是不联通吗,我们在连边的时候用并查集维护一下连通性。

加边,将不同连通块都连在一起。这些边的边权直接设为 -1。这样就规避了上篇题解的问题。

时间复杂度 $O((n+m)\log(n+m)+q\log n)$

这题要是放到今天,差不多是 D2T1,当年可是 D1T3(假设还是考两天)。

听懂了就点个赞呗 ^v^

代码

我没乱写,大家伙可以看看。

#include<bits/stdc++.h>
#define inf 1000000007
using namespace std;
inline int read(){
    int s=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){
        s*=10,s+=ch-'0';
        ch=getchar();
    }
    return s;
}
int n,m,vis[10099],dp[10099],f[10099][28],mi[10099][28];
pair<int,pair<int,int> >e[222222];
//不想写结构体和 cmp 可以用 pair,排序中 first 比 second 优先。
vector<int>t[10099],w[10099];
int fa[10099],now;
int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void reset(){
    for(int i=1;i<=n;++i)fa[i]=i;
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
void dfs(int x,int d){
    if(vis[x])return;
    vis[x]=1;
    dp[x]=d;
    for(int i=0;i<t[x].size();++i){
        if(vis[t[x][i]]==0){
            dfs(t[x][i],d+1);
            f[t[x][i]][0]=x;
        }
    }
}
int lca(int x,int y){
    int ans=inf;
    if(dp[x]<dp[y])swap(x,y);
    while(dp[x]>dp[y]){
        ans=min(ans,mi[x][(int)log2(dp[x]-dp[y])]);
        x=f[x][(int)log2(dp[x]-dp[y])];
    }
    if(x==y)return ans;
    for(int i=22;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            ans=min(ans,min(mi[x][i],mi[y][i]));
            x=f[x][i],y=f[y][i];
        }
    }
    return min(ans,min(mi[x][0],mi[y][0]));
}
int main(){
    memset(mi,0x7f,sizeof(mi));
    n=read(),m=read();
    reset();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),c=read();
        e[++now]=make_pair(c,make_pair(u,v));
        merge(u,v);
    }
    //加边
    for(int i=1;i<=n;++i){
        if(find(1)!=find(i)){
            merge(1,i);
            e[++now]=make_pair(-1,make_pair(1,i));      
        }
    }
    sort(e+1,e+now+1);
    reset();
    for(int cnt=1,p=now;cnt<n;++cnt){
        int u=e[p].second.first;
        int v=e[p].second.second;
        while(find(u)==find(v)){
            --p;
            u=e[p].second.first;
            v=e[p].second.second;
        }
        merge(u,v);
        t[u].push_back(v);
        t[v].push_back(u);
        w[u].push_back(e[p].first);
        w[v].push_back(e[p].first);
        --p;
    }
    dfs(1,0);
    f[1][0]=1;
    for(int i=1;i<=26;++i){
        for(int u=1;u<=n;++u){
            f[u][i]=f[f[u][i-1]][i-1];
        }
    }
    for(int x=1;x<=n;++x){
        for(int i=0;i<t[x].size();++i){
            int u=t[x][i],v=x;
            if(u>v)continue;
            if(f[u][0]==v)mi[u][0]=w[x][i];
            else mi[x][0]=w[x][i];
        }
    }
    for(int i=1;i<=26;++i){
        for(int u=1;u<=n;++u){
            mi[u][i]=min(mi[f[u][i-1]][i-1],mi[u][i-1]);
        }
    }
    int q=read();
    for(int i=1;i<=q;++i)
        printf("%d\n",lca(read(),read()));
    return 0;
}



Haze
30天前

结论

感觉答案是最大生成树上路径 $u\to v$ 的最小的那条边 $(a,b)$ 的权。简要说明一下:

考虑 kruskal 算法建出的生成树。

假设存在一条比生成树上更优的路径 A,不妨假设这条路径上瓶颈边为 (a',b')。

我们会发现,在建树过程中 (a,b) 考虑的时间是在 A 上所有边之后的。

此时 u,v 早已联通,该边是不可能在生成树上的。与假设矛盾。

怎样算答案?

如果把边权最小值换为两点距离你肯定会做: LCA。

如果把树换成序列你肯定更会做: 倍增 (ST表)

那不就可以考虑倍增维护最小值吗?设 $f(u,i)$ 为 $u$ 向上跳 $2^i$ 次边权最小值,一边求 LCA 一边算最小值。

原图不是不联通吗,我们在连边的时候用并查集维护一下连通性。

加边,将不同连通块都连在一起。这些边的边权直接设为 -1。这样就规避了上篇题解的问题。

时间复杂度 $O((n+m)\log(n+m)+q\log n)$

这题要是放到今天,差不多是 D2T1,当年可是 D1T3(假设还是考两天)。

听懂了就点个赞呗 ^v^

代码

我没乱写,大家伙可以看看。

#include<bits/stdc++.h>
#define inf 1000000007
using namespace std;
inline int read(){
    int s=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){
        s*=10,s+=ch-'0';
        ch=getchar();
    }
    return s;
}
int n,m,vis[10099],dp[10099],f[10099][28],mi[10099][28];
pair<int,pair<int,int> >e[222222];
//不想写结构体和 cmp 可以用 pair,排序中 first 比 second 优先。
vector<int>t[10099],w[10099];
int fa[10099],now;
int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void reset(){
    for(int i=1;i<=n;++i)fa[i]=i;
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
void dfs(int x,int d){
    if(vis[x])return;
    vis[x]=1;
    dp[x]=d;
    for(int i=0;i<t[x].size();++i){
        if(vis[t[x][i]]==0){
            dfs(t[x][i],d+1);
            f[t[x][i]][0]=x;
        }
    }
}
int lca(int x,int y){
    int ans=inf;
    if(dp[x]<dp[y])swap(x,y);
    while(dp[x]>dp[y]){
        ans=min(ans,mi[x][(int)log2(dp[x]-dp[y])]);
        x=f[x][(int)log2(dp[x]-dp[y])];
    }
    if(x==y)return ans;
    for(int i=22;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            ans=min(ans,min(mi[x][i],mi[y][i]));
            x=f[x][i],y=f[y][i];
        }
    }
    return min(ans,min(mi[x][0],mi[y][0]));
}
int main(){
    memset(mi,0x7f,sizeof(mi));
    n=read(),m=read();
    reset();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),c=read();
        e[++now]=make_pair(c,make_pair(u,v));
        merge(u,v);
    }
    //加边
    for(int i=1;i<=n;++i){
        if(find(1)!=find(i)){
            merge(1,i);
            e[++now]=make_pair(-1,make_pair(1,i));      
        }
    }
    sort(e+1,e+now+1);
    reset();
    for(int cnt=1,p=now;cnt<n;++cnt){
        int u=e[p].second.first;
        int v=e[p].second.second;
        while(find(u)==find(v)){
            --p;
            u=e[p].second.first;
            v=e[p].second.second;
        }
        merge(u,v);
        t[u].push_back(v);
        t[v].push_back(u);
        w[u].push_back(e[p].first);
        w[v].push_back(e[p].first);
        --p;
    }
    dfs(1,0);
    f[1][0]=1;
    for(int i=1;i<=26;++i){
        for(int u=1;u<=n;++u){
            f[u][i]=f[f[u][i-1]][i-1];
        }
    }
    for(int x=1;x<=n;++x){
        for(int i=0;i<t[x].size();++i){
            int u=t[x][i],v=x;
            if(u>v)continue;
            if(f[u][0]==v)mi[u][0]=w[x][i];
            else mi[x][0]=w[x][i];
        }
    }
    for(int i=1;i<=26;++i){
        for(int u=1;u<=n;++u){
            mi[u][i]=min(mi[f[u][i-1]][i-1],mi[u][i-1]);
        }
    }
    int q=read();
    for(int i=1;i<=q;++i)
        printf("%d\n",lca(read(),read()));
    return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

Haze
1个月前
#include<bits/stdc++.h>
#define M 1999999
#define S second
#define F first
using namespace std;
int n,m,s[M],f[M];
pair<int,pair<int,int> >c[M];
int find(int x){
    if(f[x]==x)return x;
    f[x]=find(f[x]);
    return f[x];
}
void merge(int x,int y){
    f[find(x)]=find(y);
}
bool check(int x){
    for(int i=1;i<=n;++i)f[i]=i,f[i+n]=i+n;
    for(int i=x;i<=m;++i){
        merge(c[i].S.F,c[i].S.S+n);
        merge(c[i].S.F+n,c[i].S.S);
    }
    for(int i=1;i<=n;++i){
        if(find(i)==find(i+n))return true;
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&c[i].S.F,&c[i].S.S,&c[i].F);
    sort(c+1,c+m+1);
    int l=0,r=m,mid;
    while(l<r){
        mid=1+(l+r)>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    printf("%d",c[l].F);
    return 0;
}


活动打卡代码 AcWing 251. 小Z的袜子

Haze
1个月前
#include<bits/stdc++.h>
using namespace std;
inline long long read(){
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
long long sum=0,sum2=0,n=read(),m=read(),len=sqrt(n),id[54321],arr[54321],ans[54321],cnt[54321],ql[54321];
struct q{
    long long l,r,id;
}ask[54321];
long long cmp(q a,q b){
    if(id[a.l]!=id[b.l])return id[a.l]>id[b.l];
    return a.r>b.r;
}
long long gcd(long long x,long long y){
    return x?gcd(y%x,x):y;
}
void sub(long long x){
    sum2-=cnt[arr[x]]*cnt[arr[x]];
    cnt[arr[x]]--;
    sum--;
    sum2+=cnt[arr[x]]*cnt[arr[x]];
}
void add(long long x){
    sum2-=cnt[arr[x]]*cnt[arr[x]];
    cnt[arr[x]]++;
    sum++;
    sum2+=cnt[arr[x]]*cnt[arr[x]];
}
int main(){
    long long i,l=1,r=0;
    for(i=1;i<=n;++i)arr[i]=read();
    for(i=1;i<=n;++i)id[i]=i/len;
    for(i=1;i<=m;++i){
        ask[i].l=read();
        ask[i].r=read();
        ask[i].id=i;
    }
    sort(ask+1,ask+m+1,cmp); 
    for(i=1;i<=m;++i){
        while(l<ask[i].l)sub(l++);
        while(l>ask[i].l)add(--l);
        while(r>ask[i].r)sub(r--);
        while(r<ask[i].r)add(++r);
        ans[ask[i].id]=sum2-sum;
        ql[ask[i].id]=(ask[i].r-ask[i].l)*(ask[i].r-ask[i].l+1);
    }
    for(i=1;i<=m;++i){
        if(ans[i]==0)printf("0/1\n");
        else printf("%lld/%lld\n",ans[i]/gcd(ans[i],ql[i]),ql[i]/gcd(ans[i],ql[i]));
    }
    return 0;
}

莫队




Haze
1个月前

$10^5$ 的数据写 $\log$ 的数据结构不是浪费吗?

分块那么可爱。

#include<bits/stdc++.h>
#define len 320
using namespace std;
long long arr[150000],id[150000],pre[150000],sum[150000];
int main(){
    long long n,m,l,r,k;
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;++i){
        scanf("%lld",&arr[i]);
        id[i]=(i-1)/len;
        sum[id[i]]+=arr[i];
//      cout<<id[i]<<' ';
    }
//  for(int i=0;i<=n;++i){
//      cout<<sum[i]<<endl;
//  }
    for(long long i=1;i<=m;++i){
        char ch=getchar();
        while(ch!='Q'&&ch!='C')ch=getchar();
        if(ch=='C'){
            scanf("%lld%lld%lld",&l,&r,&k);
            long long now=l;
            for(now=l;id[now]==id[l]&&now<=r;++now){
        //      cout<<now<<' ';
                arr[now]+=k;
                sum[now]+=k;
            }
            for(;now+len<=r;now+=len){
        //      cout<<now<<' ';
                pre[id[now]]+=k;
            }
            for(;now<=r;++now){
        //      cout<<now<<' ';
                arr[now]+=k;
                sum[now]+=k;
            }       
        }
        else{
            scanf("%lld%lld",&l,&r);
            long long now=l,ans=0;
            for(;id[now]==id[l]&&now<=r;++now){
        //      cout<<now<<' ';
                ans+=arr[now]+pre[now];
            }
            for(;now+len<=r;now+=len){
        //      cout<<now<<'R';
                ans+=sum[id[now]]+pre[id[now]]*len;
            }           
            for(;now<=r;++now){
        //      cout<<now<<' ';
                ans+=arr[now]+pre[now];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}