2022/7/21 training summary

Algorithm training

“ Weilai cup ” J Serval and Essay

I see two solutions to this problem ：
One is to make use of tarjan The method of finding the reverse order topological order
nature ：tarjan Every time push_back(s.top()) Then we can get the reverse topological order without shrinking points ( The idea is to understand , But the code just doesn't understand , I also specially reviewed tarjan Algorithm .....)

The second approach is the idea of joint search , I think it's really clever .
1. Only when the precursor of a point ( That is the preparation condition ) When they are all in a set , Before merging
2. Update the size of the collection when merging . Each set of samples initializes the array .

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

using namespace std;
const int N=1e6+100;
int n,sz[N],f[N];
bool vis[N];
vector<int>g[N];
int r_find(int r)
{
    
    if(r==f[r])
        return f[r];
    f[r]=r_find(f[r]);
    return f[r];
}
void mg(int x,int y)
{
    
    sz[y]+=sz[x],sz[x]=sz[y];
    f[x]=y;
    vis[x]=1;
}
bool check(int x)
{
    
    if(vis[x]||!g[x].size())
        return 0;
    int cur=r_find(g[x][0]);
    for(int i=1;i<g[x].size();i++)  // If other parent nodes are not in the same set 
    {
    
        if(cur!=r_find(g[x][i]))
            return 0;
    }
    if(cur==x)
        return 0;
    return 1;
}
signed main()
{
    
    int t;cin>>t;
    int Ti=0;
    while(t--)
    {
    
        Ti++;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            f[i]=i,g[i].clear(),vis[i]=0,sz[i]=1;
        }
        for(int i=1;i<=n;i++)
        {
    
            int k;cin>>k;
            for(int j=1;j<=k;j++)
            {
    
                int x;cin>>x;
                g[i].push_back(x);  // Record the connected parent node 
            }
        }
        while(1)
        {
    
            int flag=1;
            for(int i=1;i<=n;i++)
            {
    
                if(check(i))
                {
    
                    flag=0;
                    mg(i,r_find(g[i][0]));
                }
            }
            if(flag)    break;
        }
        int res=0;
        for(int i=1;i<=n;i++)
            res=max(res,sz[i]);
        cout<<"Case #"<<Ti<<": "<<res<<endl;
    }
    return 0;
}

H. Life is a Game (The 2021 ICPC Asia Shanghai Regional Programming Contest)

Two dfs Ancestors at all levels that cannot record a point , Only the nearest public ancestor can be found . For two points , Multiply lca Can be applied to 1 A little bit .
Together kruskal Refactoring tree and lca Topics combined with multiplication , The code is clear , Don't write two dfs and lca function .
Ideas ：
1. The problem can be analyzed based on the minimum spanning tree , In ascending order .
2.fa[j][i] node j Of the 2 Of i-1 Power parent node . This way of recording records the parent-child relationship of binary tree more clearly . It is more conducive to the operation of reconstructing the tree .

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=5e5+100;
int n,m,q,a[N],f[N],tol,val[N],fa[N][20],down[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];
}
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;
        }
    }
}
int build(int x)  //fa[j][i]  node j Of the 2 Of i-1 Power parent node 
{
    
    int sum=a[x];
    for(auto j:g[x])
    {
    
        fa[j][0]=x;
        for(int i=1;i<=19;i++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
        sum+=build(j);
    }
    down[x]=sum;
    return sum;
}
signed main()
{
    
    IOS;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>e[i].x>>e[i].y>>e[i].z;
    kruskal();
    build(tol);
    val[0]=1e18;
    while(q--)
    {
    
        int x,k;cin>>x>>k;
        int ans=a[x]+k;
        while(x!=tol)
        {
    
            int xx=x;
            for(int i=19;i>=0;i--)
                if(val[fa[x][i]]<=ans)
                    x=fa[x][i];
            if(x==xx)   break;
            ans=down[x]+k;
        }
        cout<<ans<<endl;
    }
    return 0;
}

P3379 【 Templates 】 Recent public ancestor （LCA）

lca The template of .

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

using namespace std;
const int N=1e6+100;
int n,m,s,f[N],tol,val[N];
vector<int>g[N];
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;
}

signed main()
{
    
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
    
        int x,y;cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(s,0);
    dfs2(s,s);
    while(m--)
    {
    
        int u,v;cin>>u>>v;
        cout<<lca(u,v)<<endl;
    }
    return 0;
}

Thinking training

C. George and Job

The question ： Given n Number , find k A length of m The interval of makes the sum of intervals maximum . Subject requirements ：[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m), , It can be seen that each interval does not overlap , A number can only be used once .
Ideas : I haven't written for a long time dp 了 , Really have no clue ....
1.n Number , The length is m by 1 Span .
2. Design status ：dp[i[[j] Means up to subscript i, among j Sum of subsequences . State transition equation ：dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m]);
3.dp[n][k] That's the answer. .

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

using namespace std;
const int N=5e5+100;
int n,m,k,a[N],sum[N],dp[5005][5005];

signed main()
{
    
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)   
    {
    
        for(int j=1;j<=k;j++)
        {
    
            //dp[i][j]=dp[i-1][j];
            if(i>=m)
                dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m]);
        }
    }
    cout<<dp[n][k]<<endl;
    return 0;
}

C. Qpwoeirut And The City

The question ：n A building , Remove the first and last houses , If meet a[i]>a[i-1]&&a[i]>a[i+1], It can be called a cool house , It is required that in the case of cool houses at most , At least how many additional floors need to be built .

Ideas ：
1. First of all, you can think of the circumstances under which cool houses are the most ？ stay n In the case of odd numbers , The number of cool houses requires the most , Then only the buildings in the even subscript position are cool houses , To meet the most ; stay n In the case of an even number , The location of the cool house is not fixed .
2. You can think of maintaining two prefixes and arrays . There are three situations , Cool house in even subscript position (2,4,6,……,n-2); Cool house subscript (n-1,n-3,n-5,……,3); The third case is the mixed selection of the first two cases . Prefix and for other records

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

using namespace std;
const int N=5e5+100;
int n,a[N],sum1[N],sum2[N];

signed main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int sum=0;
        if(n&1)
        {
    
            for(int i=2;i<n;i+=2)
                sum+=max(0ll,max(a[i-1],a[i+1])-a[i]+1);
            cout<<sum<<endl;
            continue;
        }
        sum=0;
        for(int i=2;i<n;i+=2)
        {
    
            sum+=max(0ll,max(a[i-1],a[i+1])-a[i]+1);
            sum1[i]=sum;
        }
        sum=0;
        for(int i=n-1;i>1;i-=2)
        {
    
            sum+=max(0ll,max(a[i-1],a[i+1])-a[i]+1);
            sum2[i]=sum;
        }
        int ans=min(sum1[n-2],sum2[3]);
        for(int i=2;i<n-2;i+=2)
            ans=min(ans,sum1[i]+sum2[i+3]);
        cout<<ans<<endl;
    }
    return 0;
}

A daily topic

because D yes A Upgraded version , As the first A Did .
A. Robot Cleaner
(A Not much , Look directly at D)

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

using namespace std;
const int N=5e5+100;
int n,m,rb,cb,rd,cd;

signed main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n>>m>>rb>>cb>>rd>>cd;
        int ans=0;
        if(rb<=rd&&cb<=cd)
            ans=min(rd-rb,cd-cb);
        else if(rb<=rd&&cb>cd)
            ans=min(rd-rb,m-cb+m-cd);
        else if(rb>rd&&cb<=cd)
            ans=min(n-rb+n-rd,cd-cb);
        else if(rb>rd&&cb>cd)
            ans=min(n-rb+n-rd,m-cb+m-cd);
        cout<<ans<<endl;

    }
    return 0;
}

D. Robot Cleaner Revisit
1. The points that the robot passes through in a cycle are fixed . If the column or row where the point is located can clear the garbage , Then it is marked with 1; Otherwise, mark as 0.
2. The expectation of time , What is related is time . Whether it is possible to remove garbage in this second p To express ;1-p Indicates the probability of unsuccessful cleaning .
3. Suppose you successfully cleaned it at the beginning , Then the time consumption is 0; If cleaning is not successful , It takes time to get to the next location , Then the problem can be transformed into when the initial position is i+1 Time consumption expectation at a point .
Derivation formula

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=5e5+100;
const int mod=1e9+7;
int n,m,rb,cb,rd,cd,p;
int ksm(int a,int b)
{
    
    int res=1;
    while(b)
    {
    
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getv(int a) {
    return ksm(a,mod-2);}
signed main()
{
    
    IOS;
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n>>m>>rb>>cb>>rd>>cd>>p;
        int d1=1,d2=1;
        if(rb==n) d1=-1;
        if(cb==m) d2=-1;
        int f1=d1,f2=d2;
        vector<int>a;
        int x=rb,y=cb;
        do{
    
            if(x==rd||y==cd)
                a.push_back(1);
            else
                a.push_back(0);
            x+=f1,y+=f2;
            if(x==1)   f1=1;
            if(x==n)   f1=-1;
            if(y==1)   f2=1;
            if(y==m)   f2=-1;
            if(x==rb&&y==cb&&f1==d1&&f2==d2)
                break;
        }while(1);
        int ans=0,tmp=1;
        p=(100-p)*getv(100)%mod;
        for(auto i:a)
        {
    
            if(i==1)
                tmp=tmp*p%mod;
            ans=(ans+tmp)%mod;
        }
        cout<<ans*getv((1-tmp+mod)%mod)%mod<<endl;
    }
    return 0;
}