头像

田所浩二

Shandong University of Technology


访客:5600

离线:5天前


活动打卡代码 AcWing 1584. 最大的一代

#include<bits/stdc++.h>
using namespace std;
const int N=110;
bool g[N][N];
int n,m;
vector<int> level[N];
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int id,k;
        cin>>id>>k;
        while(k--)
        {
            int son;
            cin>>son;
            g[id][son]=true;
        }
    }
    level[1].push_back(1);
    int l=1;
    while(level[l].size())
    {
        for(int i=0;i<level[l].size();i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(g[level[l][i]][j])
                {
                    level[l+1].push_back(j);//下一层填数字
                }
            }
        }
        l++;//勿忘层数加一
    }
    int k=1;
    for(int i=1;i<l;i++)
    {
        if(level[i].size()>level[k].size())
        {
            k=i;
        }
    }
    cout<<level[k].size()<<" "<<k<<endl;
    return 0;
}


活动打卡代码 AcWing 1539. 等重路径

#include<bits/stdc++.h>
using namespace std;
const int N=110;
bool g[N][N];
int w[N];
vector<vector<int>>ans;//用到需要一维插入到二维ans的时候写成这种形式
int n,m,S;
void dfs(int u,int s,vector<int>&path)
{
    bool is_leaf=true;
    for(int i=0;i<n;i++)
    {
        if(g[u][i])
        {
            is_leaf=false;
            break;
        }
    }
    if(is_leaf)
    {
        if(s==S)
        {
            ans.push_back(path);
        }
        return ;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(g[u][i])
            {
                path.push_back(w[i]);
                dfs(i,s+w[i],path);
                path.pop_back();
            }
        }
    }
}
int main()
{
    cin>>n>>m>>S;
    for(int i=0;i<n;i++)
    {
        cin>>w[i];
    }
    while(m--)
    {
        int id,k;
        cin>>id>>k;
        while(k--)
        {
            int son;
            cin>>son;
            g[id][son]=true;
        }
    }
    vector<int>path({w[0]});
    dfs(0,w[0],path);
    sort(ans.begin(),ans.end(),greater<vector<int>>());
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
        {
            if(j!=ans[i].size()-1)
            {
                cout<<ans[i][j]<<" ";
            }
            else
            {
                cout<<ans[i][j]<<endl;
            }
        }
    }
    return 0;

}



#include<bits/stdc++.h>
using namespace std;
int t;
int n;
bool check(int x)
{
    if(x==1)
    {
        return false;
    }
    else if(x==2)
    {
        return true;
    }
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(check(n))
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 842. 排列数字

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int path[N];
int vis[N];
void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)
        {
            cout<<path[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            path[u]=i;
            vis[i]=1;
            dfs(u+1);
            path[u]=0;
            vis[i]=0;
        }

    }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

#include<bits/stdc++.h>
using namespace std;
const int N=110000;
int n,k;
int a[N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cout<<a[k]<<endl;
    return 0;
}


活动打卡代码 AcWing 785. 快速排序

#include<bits/stdc++.h>
using namespace std;
const int N=110000;
int n;
int a[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
const int N=21;
int n;
int l[N],r[N],v[N],h[N],q[N];
int idx=0;
int maxidx;
void update(int u)//更新此时这个结点的深度
{
    h[u]=max(h[l[u]],h[r[u]])+1;
}
void R(int &u)//引用类型要改变根
{
    int p=l[u];
    l[u]=r[p];//原先下一层的结点如果右边有子树,要挂在平衡过来根节点的左边
    r[p]=u;
    update(u),update(p);
    u=p;//将结点改为p
}
void L(int &u)
{
    int p=r[u];
    r[u]=l[p];
    l[p]=u;
    update(u),update(p);
    u=p;
}
int get_balance(int u)
{
    return h[l[u]]-h[r[u]];
}
void insert(int &u,int w)
{
    if(!u)
    {
        u=++idx;
        v[u]=w;
    }
    else if(v[u]>w)
    {
        insert(l[u],w);
        if(get_balance(u)==2)
        {
            if(get_balance(l[u])==1)//情况1
            {
                R(u);
            }
            else//情况3,先扭转u的左节点,扭成情况1
            {
                L(l[u]);
                R(u);
            }
        }
    }
    else 
    {
        insert(r[u],w);
        if(get_balance(u)==-2)//情况2
        {
           if(get_balance(r[u])==-1)
           {
                L(u);
           }
           else
           {
                R(r[u]);
                L(u);
           }
        }
    }
    update(u);//计算每个根的深度
}
void dfs(int u,int idx)
{
    if(u==0)
    {
        return ;
    }
    maxidx=max(maxidx,idx);
    dfs(l[u],idx*2);
    dfs(r[u],idx*2+1);
}
void bfs(int root)
{
    q[0]=root;
    int tt=0,hh=0;
    while(tt<=hh)
    {
        int t=q[tt++];
        if(l[t])
        {
            q[++hh]=l[t];
        }
        if(r[t])
        {
            q[++hh]=r[t];
        }
    }
}
int main()
{
    cin>>n;
    int root=0;
    for(int i=0;i<n;i++)
    {
        int w;
        cin>>w;
        insert(root,w);
    }
    dfs(root,1);
    bfs(root);
    for(int i=0;i<n;i++)
    {
        if(i!=n-1)
        {
            cout<<v[q[i]]<<" ";
        }
        else
        {
            cout<<v[q[i]]<<endl;
        }
    }
    if(maxidx==n)
    {
        cout<<"YES";
    }
    else
    {
        cout<<"NO";
    }
    return 0;
}




模板类写法:
1.这种写法中,我把y总的bfs代码拆分成了dfs(之前做过的判断是否完全搜索二叉树)和bfs(普通的层序遍历)
2.整理了y总上课画的4中avl树模型
20200802081914.png

#include<bits/stdc++.h>
using namespace std;
const int N=21;
int n;
int l[N],r[N],v[N],h[N],q[N];
int idx=0;
int maxidx;
void update(int u)//更新此时这个结点的深度
{
    h[u]=max(h[l[u]],h[r[u]])+1;
}
void R(int &u)//引用类型要改变根
{
    int p=l[u];
    l[u]=r[p];//原先下一层的结点如果右边有子树,要挂在平衡过来根节点的左边
    r[p]=u;
    update(u),update(p);
    u=p;//将结点改为p
}
void L(int &u)
{
    int p=r[u];
    r[u]=l[p];
    l[p]=u;
    update(u),update(p);
    u=p;
}
int get_balance(int u)
{
    return h[l[u]]-h[r[u]];
}
void insert(int &u,int w)
{
    if(!u)
    {
        u=++idx;
        v[u]=w;
    }
    else if(v[u]>w)
    {
        insert(l[u],w);
        if(get_balance(u)==2)
        {
            if(get_balance(l[u])==1)//情况1
            {
                R(u);
            }
            else//情况3,先扭转u的左节点,扭成情况1
            {
                L(l[u]);
                R(u);
            }
        }
    }
    else 
    {
        insert(r[u],w);
        if(get_balance(u)==-2)
        {
           if(get_balance(r[u])==-1)//情况2
           {
                L(u);
           }
           else//情况4
           {
                R(r[u]);
                L(u);
           }
        }
    }
    update(u);//计算每个根的深度
}
void dfs(int u,int idx)
{
    if(u==0)
    {
        return ;
    }
    maxidx=max(maxidx,idx);
    dfs(l[u],idx*2);
    dfs(r[u],idx*2+1);
}
void bfs(int root)
{
    q[0]=root;
    int tt=0,hh=0;
    while(tt<=hh)
    {
        int t=q[tt++];
        if(l[t])
        {
            q[++hh]=l[t];
        }
        if(r[t])
        {
            q[++hh]=r[t];
        }
    }
}
int main()
{
    cin>>n;
    int root=0;
    for(int i=0;i<n;i++)
    {
        int w;
        cin>>w;
        insert(root,w);
    }
    dfs(root,1);
    bfs(root);
    for(int i=0;i<n;i++)
    {
        if(i!=n-1)
        {
            cout<<v[q[i]]<<" ";
        }
        else
        {
            cout<<v[q[i]]<<endl;
        }
    }
    if(maxidx==n)
    {
        cout<<"YES";
    }
    else
    {
        cout<<"NO";
    }
    return 0;
}



活动打卡代码 AcWing 1552. AVL树的根

四种情况
20200802081914.png

#include<bits/stdc++.h>
using namespace std;
const int N=21;
int n;
int l[N],r[N],v[N],h[N];
int idx=0;
void update(int u)//更新此时这个结点的深度
{
    h[u]=max(h[l[u]],h[r[u]])+1;
}
void R(int &u)//引用类型要改变根
{
    int p=l[u];
    l[u]=r[p];//原先下一层的结点如果右边有子树,要挂在平衡过来根节点的左边
    r[p]=u;
    update(u),update(p);
    u=p;//将结点改为p
}
void L(int &u)
{
    int p=r[u];
    r[u]=l[p];
    l[p]=u;
    update(u),update(p);
    u=p;
}
int get_balance(int u)
{
    return h[l[u]]-h[r[u]];
}
void insert(int &u,int w)
{
    if(!u)
    {
        u=++idx;
        v[u]=w;
    }
    else if(v[u]>w)
    {
        insert(l[u],w);
        if(get_balance(u)==2)
        {
            if(get_balance(l[u])==1)//情况1
            {
                R(u);
            }
            else//情况3,先扭转u的左节点,扭成情况1
            {
                L(l[u]);
                R(u);
            }
        }
    }
    else 
    {
        insert(r[u],w);
        if(get_balance(u)==-2)//情况2
        {
           if(get_balance(r[u])==-1)
           {
                L(u);
           }
           else
           {
                R(r[u]);
                L(u);
           }
        }
    }
    update(u);//计算每个根的深度
}
int main()
{
    cin>>n;
    int root=0;
    for(int i=0;i<n;i++)
    {
        int w;
        cin>>w;
        insert(root,w);
    }
    cout<<v[root]<<endl;
    return 0;
}


活动打卡代码 AcWing 1631. 后序遍历

//注意,这里的后序遍历的第一个数不等于中序遍历的第一个数(可能无左子树)
//所以求的是最左边子树中最后一层(左右根)三者中存在的第一个
//N很大用map优化
#include<bits/stdc++.h>
using namespace std;
const int N=51000;
unordered_map<int,int>pos;
int pre[N],in[N];
int n;
int ans;
void build(int il,int ir,int pl,int pr)
{
    int root=pre[pl];
    int k=pos[root];
    if(k>il)
    {
        build(il,k-1,pl+1,pl+k-1-il+1);
    }
    if(ir>k)
    {
        build(k+1,ir,pl+k-il+1,pr);
    }
    if(!ans)
    {
        ans=root;
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>pre[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>in[i];
        pos[in[i]]=i;
    }
    build(0,n-1,0,n-1);
    cout<<ans<<endl;
    return 0;
}