2022/7/23

1263D - Secret Passwords

If the string is not marked, go through every letter of it , Use this letter to infect other strings , Of course, letters in other strings will also be infected by this letter , Finally, take a look at cnt As much as it is

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=10007;
ll n,vis[30],vv[200005];
string s[200005];
vector<ll>v[30];
ll cnt;
void dfs(ll u,ll ind){
    //cout<<u<<" "<<vis[u];
    for(int i=0;i<v[u].size();i++){
        ll x=v[u][i];
        if(vv[x]) continue;
        vv[x]=vv[ind];
        //cout<<x<<" "<<u<<" "<<vv[x]<<" "<<vv[u]<<endl;
        for(int j=0;j<s[x].size();j++){
            if(vis[s[x][j]-'a']) continue;
            vis[s[x][j]-'a']=vis[u];
            //cout<<u<<" "<<s[x][j]<<" "<<vis[u]<<endl;
            dfs(s[x][j]-'a',x);
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i].size();j++)
        v[s[i][j]-'a'].push_back(i);
    }
    cnt=0;
    for(int i=1;i<=n;i++){
        if(vv[i]) continue;
        cnt++;
        vv[i]=cnt;
        for(int j=0;j<s[i].size();j++){
            if(vis[s[i][j]-'a']) continue;
            vis[s[i][j]-'a']=cnt;
            dfs(s[i][j]-'a',i);
        }
    }
    printf("%lld\n",cnt);
    system("pause");
    return 0;
} 

G-Link with Monotonic Subsequence_" Weilai cup " structure

My code is so ugly , The implementation method is not very right , The key is to divide each group into sqrt(n) Take the whole thing up , Then reverse the output , Got stuck in the check-in , I am worthy of it

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=10007;
ll t,n;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        ll m=ceil(sqrt(n));
        ll k=n%m;
        for(int i=k;i>=1;i--) printf("%d ",i);
        for(int i=k;i<n;i+=m)
        for(int j=i+m;j>i;j--) printf("%d ",j);
        printf("\n");
    }
    system("pause");
    return 0;
} 

P1967 [NOIP2013 Improvement group ] Truck transportation - Luogu Refactoring tree

Refactoring tree templates , Can handle from point x point-to-point y The minimum value of the maximum edge weight or the maximum value of the minimum edge weight on all paths ; Ah, I use the forward star MLE, use vector No MLE, Is dubious

 Kruskal Refactoring tree —— Learning notes _linbinwu123 The blog of -CSDN Blog _kruskal Refactoring tree

#include <bits/stdc++.h>
#define ll int
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=10007;
ll n,m,s[20005],val[20005];
ll siz[20005],d[20005],f[20005],top[20005],son[20005];
vector<int> g[20005];

void dfs1(ll u,ll fa){
    siz[u] =1;f[u]=fa;d[u]=d[fa]+1;son[u]=0;
    for(int i=0;i<g[u].size();i++){
        ll j=g[u][i];
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j]) son[u]=j;
    }
}

void dfs2(ll u,ll topx){
    top[u]=topx;
    if(son[u]) dfs2(son[u],topx);
    for(int i=0;i<g[u].size();i++){
        if(g[u][i]!=f[u]&&g[u][i]!=son[u])
        dfs2(g[u][i],g[u][i]);
    }
}
ll lca(ll x,ll y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return d[x]<d[y] ? x : y;
}
struct node{
    ll u,v,w;
    bool operator<(const node& a)const { return w>a.w; }
    // The ascending order is (u, v) The minimum value of the maximum edge weight in multiple paths 
    // In descending order (u, v) The maximum value of the minimum edge weight in multiple paths 
}ed[50005];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
void exkruscal(){
    ll ct=n;
    for(int i=1;i<=(n<<1);i++) s[i]=i,val[i]=-1;
    sort(ed+1,ed+m+1);
    for(int i=1;i<=m;i++){
        ll xx=findd(ed[i].u),yy=findd(ed[i].v);
        if(xx==yy) continue;
        val[++ct]=ed[i].w;
        s[xx]=s[yy]=ct;
        g[xx].push_back(ct), g[ct].push_back(xx);
        g[yy].push_back(ct), g[ct].push_back(yy);
        if(ct>=(n<<1)-1) break;
    }
    for(int i=1;i<=ct;i++){
        if(!siz[i]){
            ll xx=findd(i);
            dfs1(xx,0);dfs2(xx,xx);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
    }
    exkruscal();
    ll q; scanf("%d",&q);
    while(q--){
        ll u,v;
        scanf("%d%d",&u,&v);
        if(findd(u)!=findd(v)) printf("-1\n");
        else printf("%d\n",val[lca(u,v)]);
    }
    system("pause");
    return 0;
} 

P2245 Interstellar navigation - Luogu | Refactoring tree

This problem is double experience , The last question is the minimum value of the maximum edge weight , This problem is the maximum value of the minimum edge weight  

#include <bits/stdc++.h>
#define ll int
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=10007;
ll n,m,s[200005],val[200005];
ll siz[200005],d[200005],f[200005],top[200005],son[200005];
vector<int> g[200005];
ll head[50005],cnt;
struct Edge{
    ll from,to,next,w;
}edge[50005];
void addedge(ll from, ll to){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt;
}

void dfs1(ll u,ll fa){
    siz[u] =1;f[u]=fa;d[u]=d[fa]+1;son[u]=0;
    for(int i=0;i<g[u].size();i++){
        ll j=g[u][i];
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j]) son[u]=j;
    }
}

void dfs2(ll u,ll topx){
    top[u]=topx;
    if(son[u]) dfs2(son[u],topx);
    for(int i=0;i<g[u].size();i++){
        if(g[u][i]!=f[u]&&g[u][i]!=son[u])
        dfs2(g[u][i],g[u][i]);
    }
}
ll lca(ll x,ll y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return d[x]<d[y] ? x : y;
}
struct node{
    ll u,v,w;
    bool operator<(const node& a)const { return w<a.w; }
    // The ascending order is (u, v) The minimum value of the maximum edge weight in multiple paths 
    // In descending order (u, v) The maximum value of the minimum edge weight in multiple paths 
}ed[300005];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
void exkruscal(){
    ll ct=n;
    for(int i=1;i<=(n<<1);i++) s[i]=i,val[i]=-1;
    sort(ed+1,ed+m+1);
    for(int i=1;i<=m;i++){
        ll xx=findd(ed[i].u),yy=findd(ed[i].v);
        if(xx==yy) continue;
        val[++ct]=ed[i].w;
        s[xx]=s[yy]=ct;
        g[xx].push_back(ct), g[ct].push_back(xx);
        g[yy].push_back(ct), g[ct].push_back(yy);
        if(ct>=(n<<1)-1) break;
    }
    for(int i=1;i<=ct;i++){
        if(!siz[i]){
            ll xx=findd(i);
            dfs1(xx,0);dfs2(xx,xx);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
    }
    exkruscal();
    ll q; scanf("%d",&q);
    while(q--){
        ll u,v;
        scanf("%d%d",&u,&v);
        if(findd(u)!=findd(v)) printf("impossible\n");
        else printf("%d\n",val[lca(u,v)]);
    }
    system("pause");
    return 0;
} 

E- flood _ The bullock practice match 62 Refactoring tree

It's inexplicable again MLE, This time I used the forward facing star ,,, It seems that changing the size of the array is too ,,,

Of the selected points , The minimum path of any two points should be greater than x Will not disconnect , Therefore, the maximum value of the minimum weight in any two-point path should be less than or equal to x, This also shows that the refactoring tree is a small root heap , The farther away the small root piles are val The smaller the value , So don't ask for two lca Will timeout , Just count the adjacent ones directly , use dfn Array records dfs order , Be careful d Arrays cannot be used to sort , Because it is also included in the point transformed by the edge weight , Although I don't quite understand why dfs order , But after pushing, I found dfs The order is right , It should be related to the order of sorting and tree building , But I didn't figure out what the principle is , Maybe the brain has stopped turning ,,,

Now it is 2022/7/25, Let's take a look at , Pictured

Use it to build a reconstruction tree with small root heap , According to this input order

You will get the reconstruction tree as shown in the figure below

 

 dfs Order is 9,5,8,7,6,4,2,3,1, Find out besides 5,4 The outside is adjacent , and 5,4 It can also be regarded as adjacency in a sense , therefore dfs It's right to order adjacency

Kruskal Refactoring tree —— Learning notes _linbinwu123 The blog of -CSDN Blog _kruskal Refactoring tree

#include <bits/stdc++.h>
#define ll int
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll n,m,q,s[MAX],val[MAX];
ll siz[MAX],d[MAX],dfnt,dfn[MAX],f[MAX],top[MAX],son[MAX];
ll head[MAX],cnt;
struct Edge{
    ll from,to,next,w;
}edge[MAX<<1];
void addedge(ll from, ll to){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt;
}
void dfs1(ll u,ll fa){
    dfn[u]=++dfnt;
    siz[u] =1;f[u]=fa;d[u]=d[fa]+1;son[u]=0;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j]) son[u]=j;
    }
}
void dfs2(ll u,ll topx){
    top[u]=topx;
    if(son[u]) dfs2(son[u],topx);
    for(int i=head[u];i;i=edge[i].next){
        if(edge[i].to!=f[u]&&edge[i].to!=son[u])
        dfs2(edge[i].to,edge[i].to);
    }
}
ll lca(ll x,ll y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return d[x]<d[y] ? x : y;
}
struct node{
    ll u,v,w;
    bool operator<(const node& a)const { return w>a.w; }
    // The ascending order is (u, v) The minimum value of the maximum edge weight in multiple paths 
    // In descending order (u, v) The maximum value of the minimum edge weight in multiple paths 
}ed[MAX];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
void exkruscal(){
    ll ct=n;
    for(int i=1;i<=(n<<1);i++) s[i]=i,val[i]=-1;
    sort(ed+1,ed+m+1);
    for(int i=1;i<=m;i++){
        ll xx=findd(ed[i].u),yy=findd(ed[i].v);
        if(xx==yy) continue;
        val[++ct]=ed[i].w;
        s[xx]=s[yy]=ct;
        addedge(ct,xx);addedge(xx,ct);
        addedge(ct,yy);addedge(yy,ct);
        if(ct>=(n<<1)-1) break;
    }
    for(int i=1;i<=ct;i++){
        if(!siz[i]){
            ll xx=findd(i);
            dfs1(xx,0);dfs2(xx,xx);
        }
    }
}
bool cmp(ll a,ll b){
    return dfn[a]<dfn[b];
    //return d[a]<d[b];
}
ll a[MAX];
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
    }
    exkruscal();
    ll last=0,k;
    //for(int i=1;i<=2*n;i++) cout<<d[i]<<" "<<dfn[i]<<" "<<findd(i)<<endl;;cout<<endl;
    while(q--){
        scanf("%d",&k);
        for(int i=1;i<=k;i++) scanf("%d",&a[i]),a[i]^=last;
        sort(a+1,a+k+1,cmp);
        for(int i=1;i<=k;i++) cout<<i<<" "<<a[i]<<" "<<dfn[a[i]]<<" "<<d[a[i]]<<" cao"<<endl;
        ll ans=0;
        for(int i=2;i<=k;i++){
            ans=max(ans,val[lca(a[i],a[i-1])]);
            cout<<val[lca(a[i],a[i-1])]<<" cc "<<a[i]<<" "<<a[i-1]<<endl;
        }
        printf("%d\n",ans);last=ans;
    }
    system("pause");
    return 0;
}