头像

yxc

北京大学




在线 


最近来访(77882)
用户头像
NinjaEric
用户头像
juy89f1
用户头像
ljc666
用户头像
acwing_2127
用户头像
栏杆拍遍的咸鱼
用户头像
TanYIXuan20091207
用户头像
LUO_6
用户头像
罅隙
用户头像
蓝色一定是最幸福的颜色
用户头像
该用户被封禁AcWing
用户头像
我啥也不会
用户头像
神经蛙_84
用户头像
7_48
用户头像
OraCle_9
用户头像
Abracan
用户头像
abandon339
用户头像
冰块煮白开
用户头像
襙性@_4
用户头像
戴启航
用户头像
haimx

活动打卡代码 AcWing 3537. 树查找

yxc
15小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, k;
int w[N];

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

    cin >> k;
    int start = (1 << k - 1) - 1, end = start + (1 << k - 1);
    for (int i = start; i < end && i < n; i ++ )
        cout << w[i] << ' ';
    if (start >= n) puts("EMPTY");

    return 0;
}


活动打卡代码 AcWing 3511. 倒水问题

yxc
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

typedef long long LL;

const LL B = 10000;

int C[3];
unordered_set<LL> states;
unordered_set<int> cs;

LL get(int c[])
{
    return c[2] * B * B + c[1] * B + c[0];
}

void pour(int c[], int i, int j)
{
    int t = min(c[i], C[j] - c[j]);
    c[i] -= t, c[j] += t;
}

void dfs(int c[])
{
    states.insert(get(c));
    cs.insert(c[2]);

    int a[3];
    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            if (i != j)
            {
                memcpy(a, c, sizeof a);
                pour(a, i, j);
                if (!states.count(get(a)))
                    dfs(a);
            }
}

int main()
{
    while (cin >> C[0] >> C[1] >> C[2])
    {
        states.clear();
        cs.clear();
        int c[3] = {0, 0, C[2]};
        dfs(c);
        cout << cs.size() << endl;
    }

    return 0;
}



yxc
1天前
const int N = 1010, MOD = 1e9 + 7;

int f[N][N];

class Solution {
public:
    int n, m;
    vector<vector<int>> g;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int dp(int x, int y) {
        int& v = f[x][y];
        if (v != -1) return v;

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

    int countPaths(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        g = grid;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ ) 
                f[i][j] = -1;

        int res = 0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                res = (res + dp(i, j)) % MOD;
        return res;
    }
};



yxc
1天前
class Solution {
public:
    int peopleAwareOfSecret(int n, int a, int b) {
        const int MOD = 1e9 + 7;
        vector<vector<int>> f(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= b; i ++ ) f[1][i] = 1;
        for (int i = 2; i <= n; i ++ )
            for (int j = 1; j <= b; j ++ ) {
                if (j == 1) f[i][j] = (f[i - 1][b - 1] - f[i - 1][a - 1]) % MOD;
                else f[i][j] = (f[i - 1][j - 1] - f[i - 1][j - 2]) % MOD;
                f[i][j] = (f[i][j] + f[i][j - 1]) % MOD;
            }

        return (f[n][b] + MOD) % MOD;
    }
};


活动打卡代码 LeetCode 2326. 螺旋矩阵 IV

yxc
1天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> spiralMatrix(int n, int m, ListNode* p) {
        vector<vector<int>> res(n, vector<int>(m, -1));
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
        for (int i = 0; i < n * m && p; i ++ ) {
            res[x][y] = p->val;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || res[a][b] != -1) {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
            p = p->next;
        }
        return res;
    }
};


活动打卡代码 LeetCode 2325. 解密消息

yxc
1天前
class Solution {
public:
    string decodeMessage(string key, string message) {
        unordered_map<char, char> hash;
        char t = 'a';
        for (auto c: key)
            if (!hash.count(c) && c != ' ') {
                hash[c] = t;
                t ++ ;
            }

        string res;
        for (auto c: message)
            if (c == ' ') res += c;
            else res += hash[c];
        return res;
    }
};



yxc
1天前
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        const int INF = 1e8;
        int sum = 0;
        int f1 = INF, s1 = INF;
        int f2 = INF, s2 = INF;
        for (auto x: nums) {
            sum += x;
            if (x % 3 == 1) {
                if (x <= f1) s1 = f1, f1 = x;
                else if (x < s1) s1 = x;
            } else if (x % 3 == 2) {
                if (x <= f2) s2 = f2, f2 = x;
                else if (x < s2) s2 = x;
            }
        }

        if (sum % 3 == 0) return sum;
        if (sum % 3 == 1)
            return max(sum - f1, sum - f2 - s2);
        return max(sum - f2, sum - f1 - s1);
    }
};



yxc
1天前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class FindElements {
public:
    unordered_set<int> hash;

    void dfs(TreeNode* root, int x) {
        hash.insert(x);
        root->val = x;
        if (root->left) dfs(root->left, x * 2 + 1);
        if (root->right) dfs(root->right, x * 2 + 2);
    }

    FindElements(TreeNode* root) {
        dfs(root, 0);
    }

    bool find(int target) {
        return hash.count(target);
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */



yxc
1天前
class Solution {
public:
    int n, m;

    void reverse(vector<vector<int>>& grid, int start, int end) {
        for (int i = start, j = end - 1; i < j; i ++, j -- )
            swap(grid[i / m][i % m], grid[j / m][j % m]);
    }

    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        n = grid.size(), m = grid[0].size();
        k %= n * m;
        reverse(grid, 0, n * m);
        reverse(grid, 0, k);
        reverse(grid, k, n * m);
        return grid;
    }
};



yxc
2天前
class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        int tot[26] = {0};
        for (auto c: letters) tot[c - 'a'] ++ ;
        int n = words.size();
        int res = 0;
        for (int i = 0; i < 1 << n; i ++ ) {
            int cnt[26] = {0};
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)
                    for (auto c: words[j])
                        cnt[c - 'a'] ++ ;

            bool flag = true;
            for (int j = 0; j < 26; j ++ )
                if (cnt[j] > tot[j]) {
                    flag = false;
                    break;
                }

            if (flag) {
                int sum = 0;
                for (int j = 0; j < 26; j ++ )
                    sum += cnt[j] * score[j];
                res = max(res, sum);
            }
        }

        return res;
    }
};