头像

回忆如风




离线:19小时前


最近来访(7)
用户头像
NZX
用户头像
今天你爆int了吗
用户头像
Segment_Tree
用户头像
RyanMoriarty
用户头像
凛_9
用户头像
E_huan
用户头像
snkz5qing

活动打卡代码 AcWing 3438. 数制转换

回忆如风
19小时前
#include "bits/stdc++.h"
using namespace std;

int main() {
    unordered_map<char, int> mp;
    unordered_map<int, char> rmp;
    for(int i = 0; i < 16; i++) {
        if(i < 10) {
            mp['0' + i] = i;
            rmp[i] = '0' + i;
        }
        else {
            mp['a' + i % 10] = i;
            mp['A' + i % 10] = i;
            rmp[i] = 'A' + i % 10;
        }
    }

    int a, b;
    string s;
    cin>>a>>s>>b;
    int num = 0;
    for(int i = 0; i < s.size(); i++) {
        num = num * a + mp[s[i]];
    }
    string t;
    while(num) {
        t +=  rmp[(num % b)];
        num /= b;
    }
    reverse(t.begin(), t.end());
    cout<<t<<endl;
    return 0;
}


活动打卡代码 AcWing 3531. 哈夫曼树

#include "bits/stdc++.h"
using namespace std;

int main() {

    int n;
    cin>>n;

    priority_queue<int, vector<int>, greater<int>> q;
    for(int i = 1; i <= n; i++) {
        int d;
        cin>>d;
        q.push(d);
    }
    int ans = 0;
    while(q.size() > 1) {
        int x1 = q.top(); q.pop();
        int x2 = q.top(); q.pop();
        ans += (x1 + x2);
        q.push(x1 + x2);
    }

    cout<<ans<<endl;

    return 0;
}


活动打卡代码 AcWing 3477. 简单排序

#include "bits/stdc++.h"
using namespace std;

int main() {


    int n;
    cin>>n;
    set<int> st;
    for(int i = 0; i < n; i++) {
        int d;
        cin>>d;
        st.insert(d);
    }
    for(auto x : st) {
        cout<<x<<" ";
    }

    return 0;
}


活动打卡代码 AcWing 3428. 放苹果

#include "bits/stdc++.h"
using namespace std;
int m, n;
vector<int> v;
int ans;

void dfs(int x) {
    if(v.size() == n) {
        if(x == 0) ans++;
        return;
    }

    for(int i = (v.size() ? v.back() : 0); i <= x; i++) {
        v.push_back(i);
        dfs(x - i);
        v.pop_back();
    }
}
int main() {

    while(cin>>m>>n) {
        ans = 0;
        dfs(m);
        cout<<ans<<endl;
    }    


    return 0;
}


活动打卡代码 AcWing 693. 行程排序

#include "bits/stdc++.h"
using namespace std;

int main() {

    int t;
    cin>>t;

    for(int Case = 1; Case <= t; Case++) {

        int n;
        cin>>n;
        unordered_map<string, vector<string>> mp;
        unordered_map<string, int> degree;
        while(n--) {
            string s, e;
            cin>>s>>e;
            mp[s].push_back(e);
            degree[e]++;
            degree[s];
        }

        queue<string> q;
        for(auto x :  degree) {
            if(x.second == 0) q.push(x.first);
        }

        vector<string> v;
        while(q.size()) {
            string t = q.front();
            q.pop();
            v.push_back(t);
            for(int i = 0; i < mp[t].size(); i++) {
                string next = mp[t][i];
                degree[next]--;
                if(degree[next] == 0) {
                    q.push(next);
                }
            }
        }

        printf("Case #%d:", Case);
        for(int i = 1; i < v.size(); i++) {
            cout<<" "<<v[i - 1]<<"-"<<v[i];
        }

        cout<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 3311. 最长算术

#include "bits/stdc++.h"
using namespace std;

int main() {


    int T;
    cin>>T;

    for(int Case = 1; Case <= T; Case++) {


        int n, d;
        cin>>n;
        vector<int> v(n);
        int ans = 1;
        int cnt = 1;
        vector<int> res;
        for(int i = 0; i < n; i++) cin>>v[i];

        for(int i = 1; i < n; i++) {
            res.push_back(v[i] - v[i - 1]);   
        }

        for(int i = 1; i < res.size(); i++) {
            if(res[i] == res[i - 1]) {
                cnt++;
                ans = max(ans, cnt);
            }
            else cnt = 1;
        }

        printf("Case #%d: %d\n", Case, ans + 1);
    }

    return 0;
}



题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

// 递归建立二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = NULL;
        root = build(preorder, inorder);
        return root;
    }

    TreeNode* build(vector<int> x, vector<int> z) {
        if(x.size() == 0) return NULL;

        TreeNode *root = new TreeNode(x[0]);
        x.erase(x.begin());

        vector<int> xl, xr, zl, zr;

        for(int i = 0; i < z.size(); i++) {

            if(z[i] == root->val) break;
            zl.push_back(z[i]);
        }

        for(int i = zl.size() + 1; i < z.size(); i++) {
            zr.push_back(z[i]);
        }

        for(int i = 0; i < zl.size(); i++) {
            xl.push_back(x[i]);
        }

        for(int i = xl.size(); i < x.size(); i++) {
            xr.push_back(x[i]);
        } 

        root->left = build(xl, zl);
        root->right = build(xr, zr);

        return root;
    }
};


活动打卡代码 AcWing 691. 立方体IV

#include "bits/stdc++.h"
using namespace std;
const int N = 1100;
int v[N][N];
int dis[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n;
int dfs(int x, int y) {
    if(dis[x][y] != -1) return dis[x][y];

    for(int i = 0; i < 4; i++) {
        int a = x + dx[i];
        int b = y + dy[i];
        if(a >= 0 && b >= 0 && a < n && b < n) {
            if(v[a][b] == v[x][y] + 1) {
                return dfs(a, b) + 1;
            }
        }
    }

    return 1;
}
int main() {


    int t;
    cin>>t;

    for(int _ = 1; _ <= t; _++) {

        memset(dis, -1, sizeof dis);

        cin>>n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cin>>v[i][j];
            }
        }

        int idx;
        int step = 0;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dis[i][j] = dfs(i, j);
                if(dis[i][j] > step || (dis[i][j] == step && v[i][j] < idx)) {
                    step = dis[i][j];
                    idx = v[i][j];
                }
            }
        }
        printf("Case #%d: %d %d\n", _, idx, step);

    }

    return 0;
}



活动打卡代码 AcWing 4279. 笛卡尔树

//每次把最小的值当作根节点
#include "bits/stdc++.h"
using namespace std;
struct node {
    int val;
    node* lchild;
    node* rchild;
};
node* build(node* root, vector<int> v) {
    if(v.size() == 0) return NULL;
    root = new node;
    int idx, m = INT_MAX;
    for(int i = 0; i < v.size(); i++) {
        if(v[i] < m) {
            idx = i;
            m = v[i];
        }
    }
    root->val = m;
    vector<int> vl, vr;
    for(int i = 0; i < idx; i++) {
        vl.push_back(v[i]);
    }
    for(int i = idx + 1; i < v.size(); i++) {
        vr.push_back(v[i]);
    }
    root->lchild = build(root->lchild, vl);
    root->rchild = build(root->rchild, vr);

    return root;

}
int main() {

    int n;
    cin>>n;

    vector<int> v(n);

    for(int i = 0; i < n; i++) cin>>v[i];

    node* root = NULL;
    root = build(root, v);

    vector<int> res;
    if(root == NULL) return 0;

    queue<node*> q;
    q.push(root);
    while(q.size()) {
        int len = q.size(); 

        for(int i = 0; i < len; i++) {
            node *cur = q.front(); 
            q.pop();
            res.push_back(cur->val);
            if(cur->lchild) q.push(cur->lchild);
            if(cur->rchild) q.push(cur->rchild);
        }
    }

    for(int i = 0; i < res.size(); i++) {
        if(i == 0) {
            cout<<res[i];
        }
        else cout<<" "<<res[i];
    }
    cout<<endl;
    return 0;
}



class Solution {
public:
    int longestSubsequence(string s, int k) {
        int sum = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '0') sum++;
        }
        reverse(s.begin(), s.end());
        long long res = 0;
        int cnt = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '1' && i > 30) {
                return cnt + sum;
            }
            if(s[i] == '1')
                res += (1 << i);

            if(res > k) {
                return cnt + sum;
            }
            if(s[i] == '1') cnt ++;
        }

        return s.size();
    }
};