2022 / 7 / 20 training record

Algorithm training

Kruskal Algorithm

P2323 [HNOI2006] The problem of highway construction

Ideas ： Reviewed it once kruskal Algorithm . This question is more complicated , But the disassembled algorithms are all routine operations .
1. Sort the first-class highways , Run it over kurskal Algorithm , When the number of first-class highways reaches k when , Then return to exit , Record the maximum road value ;
2. Again , Sort the secondary roads , Write another one kruskal Algorithm , When the number reaches n-1-k Then exit the loop , Record the maximum value of class II Highway ;
3. This approach is seriously problematic , If k The selected value of the first-class highway is less than the maximum value of the second-class highway , Then you can continue to choose 1 First class highway , For class II Highway, the value of the previous highway is selected , Compare , Determine the minimum ;

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int N=1e5+100;
int n,k,m,f[N],g,minn;
bool vis[N];
struct node
{
    
    int a,b,c1,c2,id;
}e[N];
struct Ans
{
    
    int p,q;
}ans[N];
bool cmp1(node n1,node n2)
{
    
    return n1.c1<n2.c1;
}
bool cmp2(node n1,node n2)
{
    
    return n1.c2<n2.c2;
}
bool cmp3(Ans a1,Ans a2)
{
    
    return a1.p<a2.p;
}
int r_find(int r)
{
    
    if(r==f[r])    return f[r];
    f[r]=r_find(f[r]);
    return f[r];
}
void kruskal1()
{
    
    int tmp=0;
    for(int i=1;i<=m;i++)
    {
    
        if(!vis[e[i].id])
        {
    
            int fx=r_find(e[i].a),fy=r_find(e[i].b);
            if(fx==fy)
                continue;
            f[fx]=fy;
            tmp++,g++;
            minn=max(minn,e[i].c1);
            ans[g].p=e[i].id;
            ans[g].q=1;
        }
        if(tmp==k)
            return;
    }
}
void kruskal2()
{
    
    int tmp=0;
    for(int i=1;i<=m;i++)
    {
    
        if(!vis[e[i].id])
        {
    
            int fx=r_find(e[i].a),fy=r_find(e[i].b);
            if(fx==fy)
                continue;
            f[fx]=fy;
            tmp++,g++;
            minn=max(minn,e[i].c2);
            ans[g].p=e[i].id;
            ans[g].q=2;
        }
        if(tmp==n-1-k)
            return;
    }
}
signed main()
{
    
    cin>>n>>k>>m;
    m-=1;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
    {
    
        cin>>e[i].a>>e[i].b>>e[i].c1>>e[i].c2;
        e[i].id=i;
    }
    sort(e+1,e+m+1,cmp1);
    kruskal1();
    sort(e+1,e+m+1,cmp2);
    kruskal2();
    cout<<minn<<endl;
    sort(ans+1,ans+g+1,cmp3);
    for(int i=1;i<=g;i++)
    {
    
        cout<<ans[i].p<<" "<<ans[i].q<<endl;
    }
    return 0;
}

Kruskal Refactoring tree

Code ： In two parts ,kruskal Templates +lca Templates

nature ： Explain the article

1. In the original figure n Nodes , Are leaf nodes on the tree ;

2. The refactoring tree is a large root heap ( Reconstruct according to the minimum spanning tree );

3. Refactoring tree ( Reconstruct according to the minimum spanning tree ) in , Any two nodes a,b Of , The minimum value of the maximum edge weight in the path on the original graph is LCA(a,b) Right to the point of ;

4. If the original graph is not connected , Will get reconstruction tree forest ;

5. The total number of nodes in the reconstructed tree is 2n−1, It's a binary tree .

Use scenarios ： It can be used to solve a kind of problems such as “ The query starts from a certain point and passes by an edge weight of no more than val The node that can be reached by the edge of ” The problem of .

P1967 [NOIP2013 Improvement group ] Truck transportation

problem ： Each road has weight restrictions on vehicles , Without exceeding the weight limit , It can carry a variety of goods at most ？
1. This problem is based on the maximum spanning tree , That is, the sorting rule of road weight limit is descending ;
2. Recent public ancestor Lca The template of , two dfs.
3.dfs1 Find out size（ The size of the subtree ）,dep（ Node depth ）,fa（ Parent node ）,son（x My middle-aged son ）;dfs2 Find out top（x At the top of the heavy chain )
4. Then reconstruct the spanning tree . common 2n-1 A little bit ,n-1 A dot is an imaginary dot ,n A point is a real point .

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int N=1e5+100;
int n,m,f[N],tol,val[N];
vector<int>g[N];
bool vis[N];
struct node
{
    
    int x,y,z;
}e[N];
bool cmp(node e1,node e2)
{
    
    return e1.z>e2.z;
}
int r_find(int r)
{
    
    if(r==f[r])    return f[r];
    f[r]=r_find(f[r]);
    return f[r];
}
int son[N],siz[N],top[N],fa[N],dep[N];
void dfs1(int u,int pare)   // Refactoring tree lca initialization 
{
    
    siz[u]=1;dep[u]=dep[pare]+1;
    son[u]=0;fa[u]=pare;
    for(auto &v:g[u])
    {
    
        if(v!=pare)
        {
    
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[son[u]]<siz[v])
                son[u]=v;
        }
    }
}
void dfs2(int u,int topf)
{
    
    top[u]=topf;
    if(son[u])
        dfs2(son[u],topf);
    for(auto &v:g[u])
    {
    
        if(v!=fa[u]&&v!=son[u])
            dfs2(v,v);
    }
}
int lca(int x,int y)
{
    
    while(top[x]!=top[y])
    {
    
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
void kruskal()
{
    
    for(int i=1;i<n*2;i++)
        f[i]=i;
    sort(e+1,e+m+1,cmp);
    tol=n;
    for(int i=1;i<=m;i++)
    {
    
        int fx=r_find(e[i].x),fy=r_find(e[i].y);
        if(fx!=fy)
        {
    
            val[++tol]=e[i].z;
            f[fx]=f[fy]=tol;
            g[fx].push_back(tol),g[tol].push_back(fx);
            g[fy].push_back(tol),g[tol].push_back(fy);
            if(tol ==n*2-1) break;
        }
    }
    for(int i=1;i<=tol;i++)
    {
    
        if(!siz[i])
        {
    
            int rt=r_find(i);
            dfs1(rt,0);
            dfs2(rt,rt);
        }
    }
}

signed main()
{
    
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>e[i].x>>e[i].y>>e[i].z;
    kruskal();
    int q;cin>>q;
    while(q--)
    {
    
        int u,v;cin>>u>>v;
        if(r_find(u)!=r_find(v))
            cout<<-1<<endl;
        else
            cout<<val[lca(u,v)]<<endl;
    }
    return 0;
}

P2245 Interstellar navigation

problem ： Edge right is the dangerous degree of navigation , spot A Sail to the top B What is the minimum possible danger level value of the most dangerous side you pass ?
Ideas ： This problem is based on the minimum spanning tree , That is, the ranking rule of risk coefficient is birth order ;

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int N=5e5+100;
int n,m,q,f[N],tol,val[N];
vector<int>g[N];
struct node
{
    
    int a,b,c;
}e[N];
bool cmp(node e1,node e2)
{
    
    return e1.c<e2.c;
}
int r_find(int r)
{
    
    if(r==f[r])    return f[r];
    f[r]=r_find(f[r]);
    return f[r];
}
int son[N],siz[N],top[N],fa[N],dep[N];
void dfs1(int u,int pare)   // Refactoring tree lca initialization 
{
    
    siz[u]=1;dep[u]=dep[pare]+1;
    son[u]=0;fa[u]=pare;
    for(auto &v:g[u])
    {
    
        if(v!=pare)
        {
    
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[son[u]]<siz[v])
                son[u]=v;
        }
    }
}
void dfs2(int u,int topf)
{
    
    top[u]=topf;
    if(son[u])
        dfs2(son[u],topf);
    for(auto &v:g[u])
    {
    
        if(v!=fa[u]&&v!=son[u])
            dfs2(v,v);
    }
}
int lca(int x,int y)
{
    
    while(top[x]!=top[y])
    {
    
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
void kruskal()
{
    
    for(int i=1;i<n*2;i++)
        f[i]=i;
    sort(e+1,e+m+1,cmp);
    tol=n;
    for(int i=1;i<=m;i++)
    {
    
        int fx=r_find(e[i].a),fy=r_find(e[i].b);
        if(fx!=fy)
        {
    
            val[++tol]=e[i].c;
            f[fx]=f[fy]=tol;
            g[fx].push_back(tol),g[tol].push_back(fx);
            g[fy].push_back(tol),g[tol].push_back(fy);
            if(tol ==n*2-1) break;
        }
    }
    for(int i=1;i<=tol;i++)
    {
    
        if(!siz[i])
        {
    
            int rt=r_find(i);
            dfs1(rt,0);
            dfs2(rt,rt);
        }
    }
}

signed main()
{
    
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>e[i].a>>e[i].b>>e[i].c;
    kruskal();
    cin>>q;
    while(q--)
    {
    
        int u,v;cin>>u>>v;
        if(r_find(u)!=r_find(v))
            cout<<"impossible"<<endl;
        else
            cout<<val[lca(u,v)]<<endl;
    }
    return 0;
}

Thinking training

A. Doremy’s IQ（div1）

Ideas ：
1. It's easy to think , The choice of participating in the competition in the front will affect the number of participating in the competition in the back , That will produce the aftereffect . Therefore, you should choose from the back to the front .
2. If IQ is 2, When looking forward from behind ： If there is a competition value greater than 2, If you participate, then 2 Reduced to 1, But it will not affect the previous competition .
3. From the back forward , Yes q The second choice has nothing to do with the value required by the competition , When q When consumed , If there is less than or equal to q The competition of , Participate unconditionally .

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int N=1e6+100;
int n,q,a[N];
char c[N];
signed main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n>>q;
        for(int i=1;i<=n;i++)
            cin>>a[i],c[i]='0';
        int g=0;
        for(int i=n;i>=1;i--)
        {
    
            if(a[i]<=g) c[i]='1';
            else if(g<q)
                c[i]='1',g++;
        }
        for(int i=1;i<=n;i++)
            cout<<c[i];
        cout<<endl;
    }
    return 0;
}

D. Difference Array

Ideas ： I didn't have any ideas when I started this problem ,n Number difference , Conduct n-1 Secondary reduction , The final output a[n] Value , It feels like violence .
1.n-1 The second reduction is fixed , Each round will a[i] Updated to 0, Not involved in sorting .
2. If the number is subtracted, the result is 0, Then the number should not participate in the sorting . because a[i] and 0 The result of subtraction is still a[i], It will increase the complexity of sorting , It's an optimization of violent practices .

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int N=1e6+100;
int n,a[N];

signed main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int l=1;
        for(int i=1;i<=n-1;i++)
        {
    
            for(int j=n;j>=l;j--)
                a[j]-=a[j-1];
            a[i]=0;
            sort(a+l,a+n+1);
            while(a[l]==0&&l<=n)
                l++;
        }
        cout<<a[n]<<endl;
    }
    return 0;
}