头像

yhz0416




离线:27分钟前


最近来访(2)
用户头像
-浪漫主义狗-
用户头像
理塘的无人机终于回到我手里

活动打卡代码 AcWing 1623. 中缀表达式

yhz0416
3小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int l[N],r[N];
int n;
string s[N];
bool has_father[N];
bool is_leaf[N];

string dfs(int u)
{
    string left,right;
    if(l[u]!=-1) 
    {
        left=dfs(l[u]);
        if(!is_leaf[l[u]]) left="("+left+")"; 
    }
    if(r[u]!=-1) 
    {
        right=dfs(r[u]);
        if(!is_leaf[r[u]]) right="("+right+")"; 
    }
    return left+s[u]+right;
}

int main()
{
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i]>>l[i]>>r[i];
        if(l[i]!=-1) has_father[l[i]]=true;
        if(r[i]!=-1) has_father[r[i]]=true;
        if(l[i]==-1 && r[i]==-1) is_leaf[i]=true;
    }
    int root;
    for(root=1;root<=n;root++)
        if(!has_father[root])
            break;
    cout<<dfs(root)<<endl;

    return 0;
}


活动打卡代码 AcWing 1649. 堆路径

yhz0416
4小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int l[N],r[N],w[N];
bool isleave[N];
vector<int> path;
vector<vector<int>> res;

void dfs(int u)
{
    if(isleave[u])
    {
        res.push_back(path);
        return;
    }
    if(r[u])
    {
        path.push_back(w[r[u]]);
        dfs(r[u]);
        path.pop_back();
    }
    if(l[u])
    {
        path.push_back(w[l[u]]);
        dfs(l[u]);
        path.pop_back();
    }
    return;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        if(2*i<=n) l[i]=2*i;
        if(2*i+1<=n) r[i]=2*i+1;
        if(l[i]==0 && r[i]==0) isleave[i]=true;
    }
    path.push_back(w[1]);
    dfs(1);
    bool ismax=true,ismin = true;
    for(auto a:res)
    {
        for(int i=0;i<a.size();i++){
            if(i && a[i]<=a[i-1]) ismin=false;
            if(i && a[i]>=a[i-1]) ismax=false;
        }
        if(ismin==false && ismax==false) break;
    }
    for(auto i:res)
    {
        cout<<i[0];
        for(int j=1;j<i.size();j++) cout<<' '<<i[j];
        cout<<endl;
    }
    if(ismin==false && ismax==false) cout<<"Not Heap"<<endl;
    else if(ismin) cout<<"Min Heap"<<endl;
    else if(ismax) cout<<"Max Heap"<<endl;
    return 0;
}



yhz0416
4小时前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
int n;
double p,r;
vector<int> g[N];
int mindep=N;
int cnt[N];
bool isleave[N];

void bfs(int root)
{
    queue<PII> q;
    q.push({root,0});
    while(!q.empty())
    {
        int t=q.front().first;
        int d=q.front().second;
        q.pop();
        if(isleave[t]){
            cnt[d]++;
            mindep=min(mindep,d);
        }
        for(int i=0;i<g[t].size();i++){
            int to=g[t][i];
            q.push({to,d+1});
        }
    }
}


int main()
{
    cin>>n>>p>>r;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        if(t!=0)
        {
            while(t--)
            {
                int x;
                cin>>x;
                g[i].push_back(x);
            }
        }
        else
        {
            isleave[i]=true;
        }
    }
    bfs(0);
    printf("%.4lf %d\n",p*pow(1.0+r/100,mindep),cnt[mindep]);

    return 0;
}



yhz0416
5小时前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
int n;
double p,r;
vector<int> g[N];
int maxdep;
int cnt[N];

void bfs(int root)
{
    queue<PII> q;
    q.push({root,0});
    while(!q.empty())
    {
        int t=q.front().first;
        int d=q.front().second;
        q.pop();
        cnt[d]++;
        maxdep=max(maxdep,d);
        for(int i=0;i<g[t].size();i++){
            int to=g[t][i];
            q.push({to,d+1});
        }
    }
}


int main()
{
    int root=0;
    cin>>n>>p>>r;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x==-1) root=i;
        else g[x].push_back(i);
    }
    bfs(root);
    printf("%.2lf %d\n",p*pow(1.0+r/100,maxdep),cnt[maxdep]);

    return 0;
}



yhz0416
7小时前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5+10;
int n;
double p,r;
unordered_map<int,int> num;
vector<int> g[N];
bool isleave[N];

double qmi(int n) // (1.0 + r / 100) ^ n 
{
    double res = 1.0, t = 1.0 + r / 100; 
    while (n) 
    {
        if (n & 1) res = res * t ; 
        t = t * t ; 
        n >>= 1; 
    }
    return res; 
}

double bfs(int root)
{
    double sum=0;
    queue<PII> q;
    q.push({root,0});
    while(!q.empty())
    {
        int t=q.front().first;
        int d=q.front().second;
        q.pop();
        // if(isleave[t]) sum+=num[t]*p*qmi(d);
        if(isleave[t]) sum+=num[t]*p*pow((1.0+r/100),d);
        for(int i=0;i<g[t].size();i++){
            int to=g[t][i];
            q.push({to,d+1});
        }
    }
    return sum;
}

int main()
{
    cin>>n>>p>>r;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        if(t!=0){
            while(t--)
            {
                int x;
                cin>>x;
                g[i].push_back(x);
            }
        }
        else{
            int x;
            cin>>x;
            num[i]=x;
            isleave[i]=true;
        }
    }
    double res=bfs(0);
    printf("%.1lf\n",res);
    return 0;
}


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

yhz0416
7小时前
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n,m;
vector<int> g[N];
int cnt[N];
int maxdep;

void bfs(int root)
{
    queue<PII> q;
    q.push({root,1});
    while(!q.empty())
    {
        int t=q.front().first;
        int d=q.front().second;
        q.pop();
        cnt[d]++;
        maxdep=max(maxdep,d);
        for(int i=0;i<g[t].size();i++){
            int to=g[t][i];
            q.push({to,d+1});
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, k;
        cin >> x >> k;
        while(k--)
        {
            int y;
            cin>>y;
            g[x].push_back(y);
        }
    }
    bfs(1);
    int maxsize=-1,maxnum=-1;
    for(int i=1;i<=maxdep;i++)
    {
        if(cnt[i]>maxsize)
        {
            maxsize=cnt[i];
            maxnum=i;
        }
    }
    cout<<maxsize<<' '<<maxnum<<endl;
    return 0;
}


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

yhz0416
7小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, s;
int w[N];
bool isleave[N];
vector<int> g[N];
vector<int> path;
vector<vector<int>> res;
bool vis[N];

void dfs(int u,int d)
{
    if(isleave[u] && d == s){
        res.push_back(path);
        return;
    }
    for(int i=0;i<g[u].size();i++){
        int to=g[u][i];
        path.push_back(w[to]);
        dfs(to,d+w[to]);
        path.pop_back();
    }
}

int main()
{
    memset(isleave,true,sizeof isleave);
    cin>>n>>m>>s;
    for(int i=0;i<n;i++) cin>>w[i];
    for(int i=0;i<m;i++)
    {
        int x,k;
        cin>>x>>k;
        while(k--)
        {
            int y;
            cin>>y;
            g[x].push_back(y);
            isleave[x]=false;
        }
    }
    path.push_back(w[0]);
    dfs(0,w[0]);
    sort(res.begin(),res.end(),greater<vector<int>>());
    for(auto i:res){
        auto t=i;
        cout<<t[0];
        for(int j=1;j<t.size();j++) cout<<' '<<t[j];
        cout<<endl;
    }  
    return 0;
}


活动打卡代码 AcWing 1628. 判断红黑树

yhz0416
8小时前
#include <bits/stdc++.h>
using namespace std;
const int N = 40;
int pre[N], in[N];
bool ans;
unordered_map<int, int> pos;

int build(int il, int ir, int pl, int pr, int &sum)
{
    int root = pre[pl];
    int k = pos[abs(root)];
    if (k < il || k > ir)
    {
        ans = false;
        return 0; // 随便返回一个值 不影响结果
    }
    int left = 0, right = 0; // 左右儿子结点
    int lsum = 0, rsum = 0;  // 左右子树上黑色结点数
    if (il < k)
        left = build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), lsum);
    if (k < ir)
        right = build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, rsum);

    if (lsum != rsum) // 左右子树的黑色节点数不相等
    {
        ans = false;
        return 0;
    }
    sum = lsum;   // 因为sum是返回上一层的,所以两条子树上的相同,赋值一个即可
    if (root < 0) // 如果当前结点是红色,看看它的子节点是否是黑色
    {

        if (left < 0 || right < 0) // 左右儿子有一个是红色就不成立
        {
            ans = false;
            return 0;
        }
    }
    else    // 如果当前结点是黑色,则它到子结点的黑色数目等于,子路上的+它一个
        sum++; 

    return root;
}

int main()
{
    int k;
    cin >> k;
    while (k--)
    {
        memset(pre, 0, sizeof pos);
        memset(in, 0, sizeof in);
        pos.clear();
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> pre[i]; // <0是红色 >0是黑色
            in[i] = abs(pre[i]);
        }
        sort(in, in + n);

        for (int i = 0; i < n; i++)
            pos[in[i]] = i;

        ans = true;
        int sum; //从当前结点到叶子结点上的黑色结点数目
        int root = build(0, n - 1, 0, n - 1, sum);
        if (root < 0)
            ans = false; // 结点是红色,不符合
        if (ans)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}



yhz0416
21小时前
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 30;
int n,root,idx;
int l[N],r[N],w[N],h[N];
int maxid;
vector<int> res;

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

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 x)
{
    if(!u)
    {
        u=++idx;
        w[u]=x;
    }
    else if(x<w[u])
    {
        insert(l[u],x);
        if(get_balance(u)==2){
            if(get_balance(l[u])==1){
                R(u);
            }else{
                L(l[u]);
                R(u);
            }
        }
    }
    else if(x>w[u])
    {
        insert(r[u],x);
        if(get_balance(u)==-2){
            if(get_balance(r[u])==-1){
                L(u);
            }else{
                R(r[u]);
                L(u);
            }
        }
    }
    else return;
    update(u);
}

void bfs(int root)
{
    queue<PII> q;
    q.push({root,1});
    while(!q.empty())
    {
        int t=q.front().first;
        int d=q.front().second;
        // cout<<t<<' '<<w[t]<<' '<<d<<endl;
        q.pop();
        res.push_back(w[t]);
        maxid=max(maxid,d);
        if(l[t]) q.push({l[t],d*2});
        if(r[t]) q.push({r[t],d*2+1});
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        insert(root,x);
    }
    bfs(root);
    cout<<res[0];
    for(int i=1;i<res.size();i++) cout<<' '<<res[i];
    cout<<endl;
    if(maxid==n) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

    return 0;
}


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

yhz0416
21小时前
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int n, root, idx;
int l[N], r[N], w[N], h[N];

// 更新当前节点的最大高度
void update(int u)
{
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}

// 右旋
void R(int &u) // u是当前根节点
{
    int p = l[u]; // p为原根节点的左儿子,p是旋转之后的根节点
    l[u] = r[p];  // p的右儿子变为原根节点的左儿子
    r[p] = u;     // 原根节点变成新根节点的右儿子
    update(u);    // 重新计算高度
    update(p);
    u = p; // p变为新根节点
}

// 左旋
void L(int &u) // u是当前根节点
{
    int p = r[u]; // p为原根节点的右儿子,p是旋转之后的根节点
    r[u] = l[p];  // p的左儿子变为原根节点的右儿子
    l[p] = u;     // 原根节点变成新根节点的左儿子
    update(u);
    update(p);
    u = p; // p变为新根节点
}

// 判断左右子树的高度差(左子树-右子树)
int get_balance(int u)
{
    return h[l[u]] - h[r[u]];
}

// insert建平衡树(二叉搜索树 + 高度差小于等于1)
void insert(int &u, int x)
{
    if (!u) // 节点不存在,则新建
    {
        u = ++idx;
        w[u] = x;
    }
    else if (x < w[u]) 
    {
        insert(l[u], x); // 插入左子树
        if (get_balance(u) == 2) // 左子树比右子树高2
        {
            if (get_balance(l[u]) == 1) // 以左儿子为根,其左子树以右子树高1
                R(u); // 右旋
            else // 以左儿子为根,其右子树比左子树高1
            {
                L(l[u]); // 左旋左儿子 
                R(u); // 右旋根节点
            }
        }
    }
    else 
    {
        insert(r[u], x); // 插入右子树
        if (get_balance(u) == -2) // 右子树比左子树高2
        {
            if (get_balance(r[u]) == -1) // 以右儿子为根,其右子树比左子树高1
                L(u); // 左旋
            else // 以右儿子为根,其左子树比右子树高1
            {
                R(r[u]); // 右旋右儿子
                L(u); // 左旋根节点
            }
        }
    }
    update(u); // 更新u节点的高度
}

int main()
{
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        insert(root, x);
    }

    cout << w[root] << endl;
    return 0;
}