2022/7/21训练总结

2022-07-23 18:33:00 【钟钟终】

算法训练

“蔚来杯” J Serval and Essay

本题我看到了两种解法：
一种是利用tarjan求反序拓扑序的做法
性质：tarjan每次push_back(s.top()) 就可以得到不缩点的反向拓扑序 (思路是理解了，但是代码就是看不懂，我还特地复习了tarjan算法。。。。。)

第二种做法是并查集的思路，我认为真的非常巧妙。
1.只有当一个点的前驱点(即为准备条件)都在一个集合中时，才可进行合并操作
2.合并时更新集合的大小。每组样例初始化数组。

#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(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);  //记录连接的父亲节点
            }
        }
        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)

两个dfs记录不了一个点的各级祖先，只能找到最近的公共祖先。适用于两个点的，倍增lca可适用于1个点。
一道kruskal重构树和lca倍增相结合的题目，代码较为清晰，不用写两个dfs和lca函数。
思路：
1.可分析出题目基于最小生成树，进行升序排列。
2.fa[j][i] 节点j的第2的i-1次幂级父结点。这种记录方式更清楚的记录了二叉树父子关系。更利于重构树的操作。

#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] 节点j的第2的i-1次幂级父结点
{
    
    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 【模板】最近公共祖先（LCA）

lca的模板。

#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)   //重构树lca初始化
{
    
    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;
}

思维训练

题意：给定n个数，找到k个长度为m的区间使得区间和最大。题目要求：[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m), ，可看出各个区间不重叠，一个数只能用一次。
思路:好久没写dp了，真的没头绪。。。。
1.n个数，长度为m为1个跨度。
2.设计状态：dp[i[[j]表示截至到下标i，其中j个子序列的和。状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m]);
3.dp[n][k]就是答案。

#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

题意：n个建筑，除去第一个和最后一个房子，若满足a[i]>a[i-1]&&a[i]>a[i+1]，则可称为凉爽的房子，要求在凉爽的房子最多的情况下，最少需要额外搭建多少层。

思路：
1.首先可想到什么情况下凉爽的房子最多？在n为奇数的情况下，凉爽的房子数量要求最多，则只有在偶数下标位置上的建筑为凉爽房子，才可满足最多；在n为偶数的情况下，凉爽房子的位置不固定。
2.可想到维护两个前缀和数组。共三种情况，凉爽房子在偶数下标位置(2,4,6,……,n-2)；凉爽房子下标在(n-1,n-3,n-5,……,3);第三种情况为前两种情况的混合选择。前缀和为别记录

#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;
}

每日一题

由于D是A的升级版，就先把A做了。
A. Robot Cleaner
(A就不多说了,直接看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.机器人所在图中一个周期内经过的点是固定的。若该点所在列或行可以清楚垃圾，则标记为1；否则标记为0.
2.时间的期望值，关联的是时间。该秒是否有可能清除垃圾用概率p来表示；1-p 表示不成功清洁的概率。
3.假设初始时就成功清洁了，那么时间消耗为0;如果没有成功清洁，就要花费一个时间到下一个位置，进而可以将问题转化为当初始位置为第i+1个点的时候的时间消耗期望。
推导公式

#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;
}