头像

Tie


访客:15706

离线:5天前


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

Tie
1个月前
// Time Limit Exceeded   

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int a[N];

int partition(int a[], int l, int r) {
    int p = a[l]; // 把最左边的点设为pivot
    int m = l; //更新m为最左边的点,m是S1和S2的分界点,位于S1末尾
    // 比pivot小的点放到S1里面去,比pivot大的点放到S2里面去,最开始两者皆为空
    for (int k = m + 1; k <= r; k ++ ) { //遍历数组
        if (a[k] < p) { // 找到数组中小于pivot的值
            m ++ ; // 更新m,让S1区间多1
            swap(a[k], a[m]); // 把小于pivot的值放到S1区间里面
        }
    }
    swap(a[l], a[m]); // 把pivot的值和m交换,使pivot分隔S1和S2
    return m;

}

void quickSort(int a[], int l, int r) {
    if (l < r) {
        int m = partition(a, l, r);
        quickSort(a, l, m - 1); // 递归地将左子阵列排序
        quickSort(a, m + 1, r); // 然后将右子阵列排序
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    quickSort(a, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}



Tie
1个月前
if __name__ == '__main__':
    n = int(input())
    array = list(map(int, input().split()))
    res = quicksort(array)
    for i in res:
        print(i, end=' ')



Tie
1个月前
class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
        return f[n][m];
    }
};


活动打卡代码 AcWing 50. 序列化二叉树

Tie
1个月前
/**
 * 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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root, res);
        return res;
    }

    void dfs_s(TreeNode *root, string &res)
    {
        if (!root) {
            res += "null ";
            return;
        }
        res += to_string(root->val) + ' ';
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data, u);
    }

    TreeNode* dfs_d(string data, int &u)
    {
        //if (u == data.size()) return NULL;
        int k = u;
        while (data[k] != ' ') k ++ ;
        if (data[u] == 'n') {
            u = k + 1;
            return NULL;
        }
        int val = 0, sign = 1;
        if (u < k && data[u] == '-') sign = -1, u ++ ;
        for (int i = u; i < k; i ++ ) val = val * 10 + data[i] - '0';
        val *= sign;
        u = k + 1;
        auto root = new TreeNode(val);
        root->left = dfs_d(data, u);
        root->right = dfs_d(data, u);
        return root;
    }
};



Tie
1个月前
#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;
typedef long long LL;


int n;
int f[N];

int main() {
    cin >> n;

    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j < i; j ++ ) 
            f[i] = (f[i]  + (LL)f[j] * f[i - 1 - j]) % MOD;
    cout << f[n] << endl;

    return 0;
}



Tie
1个月前
/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        if (!head) return head;  // 如果是空节点,特判断
        unordered_map<ListNode*, ListNode*> pos; // 定义hash表来存映射,从一个指针映射到另一个指针

        pos[NULL] = NULL; // 空节点映射到空节点
        for (auto p = head; p; p = p->next)  // 遍历原链表
            pos[p] = new ListNode(p->val); // 先给每个点做个影分身

        for (auto p = head; p; p = p->next) { 
            pos[p]->next = pos[p->next];  // 
            pos[p]->random = pos[p->random];
        }

        return pos[head];
    }
};


活动打卡代码 AcWing 680. 剪绳子

Tie
1个月前
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int l[N];

bool check(double length) {
    int s = 0;
    for (int i = 0; i < n; i ++ ) {
        s += l[i] / length;
        if (s >= m) return true;
    }

    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> l[i];

    double l = 0, r = 1e9;
    while (r - l > 1e-4) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n", r);

    return 0;
}



Tie
1个月前
/**
 * 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:
    vector<int> get_val(vector<TreeNode*> level)
    {
        vector<int> res;
        for (auto &u : level)
            res.push_back(u->val);
        return res;
    }

    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>>res;
        if (!root) return res;
        vector<TreeNode*>level;
        level.push_back(root);
        res.push_back(get_val(level));
        bool zigzag = true;
        while (true)
        {
            vector<TreeNode*> newLevel;
            for (auto &u : level)
            {
                if (u->left) newLevel.push_back(u->left);
                if (u->right) newLevel.push_back(u->right);
            }
            if (newLevel.size())
            {
                vector<int>temp = get_val(newLevel);
                if (zigzag)
                    reverse(temp.begin(), temp.end());
                res.push_back(temp);
                level = newLevel;
            }
            else break;
            zigzag = !zigzag;
        }
        return res;
    }
};


活动打卡代码 AcWing 731. 毕业旅行问题

Tie
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int n;
int w[N][N];
int f[1 << N][N]; // f[i][j]表示已经走遍i中所有城市,并且停留在j城市的所有方案集合;花费最小值
// 状态i化为二进制后,里面为1的位置表示走过了的城市, i <= (1 << n) - 1
// 101010101表示走过了5个城市

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

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0; 

    for (int i = 1; i < 1 << n; i += 2)
        for (int j = 0; j < n; j ++ ) 
            if (i >> j && 1) 
                for (int k = 0; k < n; k ++ )
                    if (i - (1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    int res = 0x3f3f3f3f;
    for (int i = 1; i < n; i ++ ) res = min(res, f[(1 << n) - 1][i] + w[i][0]);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 167. 木棒

Tie
1个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 70;

int n;
int sticks[N];
bool st[N];
int sum, length;

bool dfs(int u, int cur, int start) { // 木棒数量,当前木棒长度,木棍开始位置
    if (u * length == sum) return true;
    if (cur == length) return dfs(u + 1, 0, 0);

    for (int i = start; i < n; i ++ ) {
        if (st[i]) continue;
        int l = sticks[i];
        if (cur + l <= length) {
            st[i] = true;
            if (dfs(u, cur + l, i + 1)) return true;
            st[i] = false;
        }


        if (!cur || cur + l == length) return false;

        int j = i + 1;
        while (j < n && sticks[j] == l) j ++ ;
        i = j - 1;
    }

    return false;
}

int main() {
    while (cin >> n, n) {
        sum = length = 0;
        for (int i = 0; i < n; i ++ ) {
            int l;
            cin >> l;
            sticks[i] = l;
            sum += l;
            length = max(length, l);
        }

        sort(sticks, sticks + n, greater<int>());

        memset(st, 0, sizeof st);
        while(true) {
            if (sum % length == 0 && dfs(0, 0, 0)) {
                cout << length << endl;
                break;
            }
            length ++ ;
        }
    }

    return 0;
}