2022/7/21训练总结

算法训练 “蔚来杯” J Serval and Essay

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

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

#include 
//#define int long long
#define endl '\n'

using namespace std;
const int N=1e6+100;
int n,sz[N],f[N];
bool vis[N];
vectorg[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>t;
    int Ti=0;
    while(t--)
    {
        Ti++;
        cin>>n;
        for(int i=1;ik;
            for(int j=1;j>x;
                g[i].push_back(x);  //记录连接的父亲节点
            }
        }
        while(1)
        {
            int flag=1;
            for(int i=1;ik;
        int ans=a[x]+k;
        while(x!=tol)
        {
            int xx=x;
            for(int i=19;i>=0;i--)
                if(val[fa[x][i]]>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;
        couta[i],sum[i]=sum[i-1]+a[i];
    for(int i=1;i>n;
        for(int i=1;i>a[i];
        int sum=0;
        if(n&1)
        {
            for(int i=2;icb>>rd>>cd;
        int ans=0;
        if(rbcd)
            ans=min(n-rb+n-rd,m-cb+m-cd);
        coutt;
    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;
        vectora;
        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