头像

Nana_4




离线:4天前


最近来访(4)
用户头像
吴梦涵2022
用户头像
clouds._7
用户头像
violet_garden


Nana_4
14天前

AcWing《算法提高课》拼团优惠!https://www.acwing.com/activity/content/introduction/16/group_buy/106772/




Nana_4
14天前
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

const int N = 110;
int n;
int a[N],w[N],res[N],l[N],r[N];
int j = 0;

void dfs(int root){
    if(l[root]!= -1) dfs(l[root]);
    w[root] = a[j++]; 
    if(r[root]!= -1) dfs(r[root]);
}

void bfs(int root){
    queue<int> q;
    q.push(root);
    int m = 0;
    while(!q.empty()){
        int index = q.front();
        res[m++] = w[index];
        q.pop();
        if(l[index]!=-1) q.push(l[index]);
        if(r[index]!=-1) q.push(r[index]);
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i<n; i++){
        scanf("%d %d", &l[i], &r[i]);
    }
    for(int i = 0; i<n; i++){
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    dfs(0);
    bfs(0);
    cout << res[0];
    for(int i = 1; i<n; i++){
        cout << ' ' << res[i];
    }
    return 0;
}


活动打卡代码 AcWing 1576. 再次树遍历

Nana_4
14天前
#include<iostream>
#include<stack>
#include<unordered_map>
using namespace std;

const int N = 40;
int preorder[N], inorder[N];
unordered_map<int, int> l, r, pos;
int u;

int build(int pl, int pr, int il, int ir){
    int root = preorder[pl];
    int k = pos[root];
    if(k > il) l[root] = build(pl+1,k-il+pl,il,k-1);
    if(k < ir) r[root] = build(k-il+pl+1,pr,k+1,ir);
    return root;
}

void dfs(int root){
    if(l.count(root)){
        dfs(l[root]);
    }
    if(r.count(root)){
        dfs(r[root]);
    }
    cout << root;
    if(root != u) cout << ' ';
}

int main()
{
    int n;
    cin >> n;
    int m= 2*n;
    int i = 0, j = 0;
    stack<int> st;
    while(m--){
        string s;
        int val;
        cin >> s;
        if(s == "Push"){
            cin >> val;
            preorder[i++] = val;
            st.push(val);
        }
        else if(s == "Pop"){
            if(!st.empty()){
                inorder[j] = st.top();
                pos[inorder[j]] =  j;
                j++;
            }
            st.pop();
        }
    }
    int root = build(0, n-1, 0, n-1);
    u = root;
    dfs(root);
    return 0;
}



活动打卡代码 AcWing 1506. 中位数

Nana_4
14天前
#include<iostream>
using namespace std;

const int N = 2e5;
int p[N],q[N],c[N*2];
int m, n;

int main(){
    cin >> m;
    for(int i = 0; i < m; i++){
        scanf("%d", &p[i]);
    }
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &q[i]);
    }
    int i = 0, j = 0, index = 0;
    while(i < m && j < n){
        if(p[i]<q[j]) c[index++] = p[i++];
        else c[index++] = q[j++];
    }
    while(i<m) c[index++] = p[i++];
    while(j<n) c[index++] = q[j++];

    cout << c[(m+n-1)/2];
    return 0;
}



Nana_4
14天前

AcWing《算法提高课》拼团优惠!https://www.acwing.com/activity/content/introduction/16/group_buy/106772/



活动打卡代码 AcWing 1480. 电梯

Nana_4
15天前
#include<iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int per = 0;
    int res = 0;
    while(N--){
        int m;
        cin >> m;
        if(m-per>=0){
            res += (m-per)*6+5;
        }
        else{
            res += (per-m)*4+5;
        }
        per = m;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1521. 魔术卷

Nana_4
15天前
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
    vector<int> arr1_1, arr1_2;
    vector<int> arr2_1, arr2_2;   
    int m;
    cin >> m;
    while(m--){
        int v;
        cin >> v;
        if(v>0)
        arr1_1.push_back(v);
        else if(v<0)
        arr1_2.push_back(v);
    }
    cin >> m;
    while(m--){
        int v;
        cin >> v;
        if(v>0)
        arr2_1.push_back(v);
        else if(v<0)
        arr2_2.push_back(v);
    }
    sort(arr1_1.begin(), arr1_1.end());
    sort(arr1_2.begin(), arr1_2.end());
    sort(arr2_1.begin(), arr2_1.end());
    sort(arr2_2.begin(), arr2_2.end());

    int res = 0, i = 0;
    while(i<min(arr1_1.size(), arr2_1.size())){
        res += arr1_1[arr1_1.size()-1-i]*arr2_1[arr2_1.size()-1-i];
        i++;
    }
    i = 0;
    while(i<min(arr1_2.size(), arr2_2.size())){
        res += arr1_2[i]*arr2_2[i];
        i++;
    }
    cout << res << endl;
}



活动打卡代码 AcWing 1485. 战争中的城市

Nana_4
15天前
#include<iostream>
using namespace std;

const int N = 1010, M = 500010;
int p[N];
struct edge{
    int a, b;
}e[M];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];    
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++) scanf("%d %d", &e[i].a, &e[i].b);

    for(int i = 0; i < k; i++){
        int cnt = n-1; // 去掉x一共有n-1个连通块。
        int x;
        scanf("%d", &x);
        for(int j = 1; j<=n; j++) p[j] = j;
        for(int j = 0; j< m; j++){
            int a = e[j].a;
            int b = e[j].b;
            if(a!=x&&b!=x){
                int pa = find(a), pb = find(b);
                if(pa!=pb){
                    p[pa] = pb;
                    cnt--;
                }
            }
        }
        printf("%d\n", cnt-1);
    }
}


活动打卡代码 AcWing 1532. 找硬币

Nana_4
15天前
#include<iostream>
#include<unordered_set>
using namespace std;
int INF = 10000;
int m, n;

int main(){
    cin >> m >> n;
    unordered_set<int> s;
    int v1 = INF, v2;
    for(int i = 0; i<m ; i++){
        int a;
        cin >> a;
        int diff = n-a;
        if(s.count(diff)){
            s.insert(a);
            if(a > diff) swap(a, diff);
            if(v1 > a) v1 = a, v2 = diff;    
        }
        else s.insert(a);
    }
    if(v1 == INF) puts("No Solution");
    else cout << v1 << ' ' << v2 << endl;
    return 0;
}


活动打卡代码 AcWing 1479. 最大子序列和

Nana_4
16天前
#include<iostream>
using namespace std;

const int N = 10010;
int nums[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> nums[i];
    int f = 0;
    int res = -1, l, r, start = 0;
    for(int i = 0; i < n; i++){
        if(f < 0){
            f = 0;
            start = i;
        }
        f += nums[i];
        if(f > res){
            res = f;
            l = nums[start];
            r = nums[i];
        }
    }
    if(res < 0) cout << 0 << ' ' << nums[0] << ' ' << nums[n-1] << endl;
    else cout << res << ' ' << l << ' ' << r << endl;
    return 0;
}