头像

Siriuss




离线:2天前


最近来访(42)
用户头像
取什么名字好呢
用户头像
用户头像
nickxiao
用户头像
Bsqaq
用户头像
Fatin
用户头像
Uncle
用户头像
种花家的蒟蒻
用户头像
Qjwwww
用户头像
加勒比海带_1
用户头像
NWNU
用户头像
偷偷打周赛上分
用户头像
yuanheci
用户头像
睡不饱
用户头像
-俺很苗条-
用户头像
jinyc
用户头像
Irana
用户头像
麻瓜子
用户头像
Cloudddddd
用户头像
Wing_wing_wing
用户头像
jzz2002


Siriuss
12天前

若干个平行坐标轴的矩形(可能重叠),找到他所有的顶点。
凸多边形.png

内部不算顶点,求指教~



活动打卡代码 AcWing 876. 快速幂求逆元

Siriuss
13天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int qmi(int a, int b, int p) {
    int res = 1 % p;
    while (b) {
        if (b & 1) res = (long long)res * a % p;
        b >>= 1;
        a = (long long)a * a % p;
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n --) {
        int a, p;
        scanf("%d%d", &a, &p);

        int t = qmi(a, p - 2, p);

        if (a % p) printf("%d\n", t);
        else printf("impossible\n");
    }

    return 0;
}



Siriuss
13天前

我昨天看到一道题,没有什么好的思路,所以求助一下大家

N个非负数,每次找到M个(不足m个连续的区间不能删除)连续非负的区间将他们减去1,求若干次操作之后总和最小值多少?
输入N, M:
样例1:
5 3
2 1 5 3 2
输出: 4

样例1说明:
先将 1 5 3 区间减少 1, 样例变为2 0 4 2 2
然后将 4 2 2 区间减少2,样例变为2 0 2 0 0, 答案为4

样例2:
5 3
5 5 5 0 5
输出:5

样例1说明:
将 5 5 5 区间减去5,答案为5

数据范围: 1 <= N <= 500000, 1 <= M <= N

大家有好的做法嘛?



活动打卡代码 AcWing 3068. 扫描线

Siriuss
14天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e3 + 5;

int n;
PII l[N], r[N];
PII q[N];


LL cal(int a, int b) {
    LL res = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (l[i].first <= a && r[i].first >= b) 
            q[cnt ++] = {l[i].second, r[i].second};

    if (!cnt) return 0;
    sort(q, q + cnt);

    int st = q[0].first, ed = q[0].second;
    for (int i = 1; i < cnt; i++)
        if (q[i].first <= ed) ed = max(ed, q[i].second);
        else {
            res += ed - st;
            st = q[i].first, ed = q[i].second;
        }

    res += ed - st;
    return res * (b - a);
}


int main() {
    cin >> n;
    vector<int> xs;
    for (int i = 0; i < n; i ++) {
        cin >> l[i].first >> l[i].second >> r[i].first >> r[i].second;
        xs.push_back(l[i].first), xs.push_back(r[i].first);
    }

    sort(xs.begin(), xs.end());
    LL res = 0;
    for (int i = 0; i + 1 < xs.size(); i++)
        res += cal(xs[i], xs[i + 1]);

    cout << res << endl;

    return 0;
}



Siriuss
22天前
class Solution {
public:
    unordered_map<int, int> h;
    int dp(int x) {
        if (h[x] > 0) return h[x];
        if (x == 1) return 0;
        if (x & 1) h[x] = dp(x * 3 + 1) + 1;
        else h[x] = dp(x / 2) + 1;
        return h[x];
    }
    int getKth(int lo, int hi, int k) {
        for (int i = lo; i <= hi; i++) h[i] = dp(i);
        vector<pair<int, int>> w;
        for (int i = lo; i <= hi; i++) w.push_back({h[i], i});
        sort(w.begin(), w.end());
        return w[k - 1].second;
    }
};



Siriuss
23天前
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int cnt = 0, res = 0;
        for (int i = 0; i < arr1.size(); i++) {
            int cnt = 0;
            for (int j = 0; j < arr2.size(); j++) 
                if (abs(arr1[i] - arr2[j]) > d) cnt++;
            res += (cnt == arr2.size());
        }
        return res;
    }
};



Siriuss
25天前
/**
 * 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* getTargetCopy(TreeNode* u, TreeNode* v, TreeNode* target) {
        if (!u) return nullptr;
        if (u->val == target->val) return v;
        auto left = getTargetCopy(u->left, v->left, target);
        if (left) return left;
        return getTargetCopy(u->right, v->right, target);
    }
};



Siriuss
26天前
/**
 * 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 Solution {
public:
    static const int INF = 1e5;
    struct Range {
        int l, r, sum;
        bool flag;
        bool operator!= (Range& W) const {
            return l != W.l || r != W.r || sum != W.sum || flag != W.flag;
        };
        bool operator== (Range& W) const {
            return l == W.l && r == W.r && sum == W.sum && flag == W.flag;
        };
    };
    Range null = {INF, INF, INF, true};
    int ans;

    int maxSumBST(TreeNode* root) {
        dfs(root);
        return ans;
    }

    Range dfs(TreeNode* u) {
        if (!u) return null;
        Range t = {0, 0, 0, false};
        auto left = dfs(u->left), right = dfs(u->right);

        if (left == null && right == null) t = {u->val, u->val, u->val, true};
        else if (left == null) {
            if (u->val < right.l && right.flag) t = {u->val, right.r, u->val + right.sum, true};
        } else if (right == null) {
            if (u->val > left.r && left.flag) t = {left.l, u->val, u->val + left.sum, true};
        } else {
            if (u->val > left.r && u->val < right.l && left.flag && right.flag) t = {left.l, right.r, u->val + left.sum + right.sum, true};
        }
        if (t.flag) ans = max(ans, t.sum);
        return t;
    }
};


活动打卡代码 LeetCode 2402. 会议室 III

Siriuss
26天前
class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& a) {
        typedef pair<long long, int> PII;
        priority_queue<PII, vector<PII>, greater<PII>> m, r;
        for (int i = 0; i < n; i++) r.push({-1, i});
        for (auto& c: a) m.push({c[0], c[1]});

        vector<int> cnt(n);

        int maxv = -1, res = -1;
        while (m.size()) {
            auto y = m.top(); m.pop();

            vector<PII> q;
            while (r.size() && r.top().first <= y.first) {
                auto x = r.top();
                r.pop();
                q.push_back(x);
            }

            PII x;
            if (q.size()) {
                sort(q.begin(), q.end(), [](PII& aa, PII& bb) {
                    return aa.second < bb.second;
                });
                x = q[0];
                for (int i = 1; i < q.size(); i++) r.push(q[i]);
            } else {
                x = r.top();
                r.pop();
            }

            int id = x.second;
            cnt[id]++;
            long long end = y.second;
            if (y.first < x.first) end = x.first + y.second - y.first;
            else end = y.second;
            r.push({end, id});    
        }

        for (int i = 0; i < n; i++) {
            if (cnt[i] > maxv) {
                maxv = cnt[i];
                res = i;
            }
        }

        return res;
    }
};



Siriuss
26天前
class Solution {
public:
    bool check(vector<int>& a) {
        for (int i = 0; i < 32; i++)
            if (a[i] >= 2) return false;
        return true;
    }

    int longestNiceSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> cnt(35);
        int res = 0;
        for (int i = 0, j = 0; i < n; i++) {
            int x = nums[i];
            for (int j = 0; j < 31; j++)
                if (nums[i] >> j & 1) cnt[j] ++;
            while (j < i && !check(cnt)) {
                int t = nums[j];
                j++;
                for (int k = 0; k < 31; k++)
                    if (t >> k & 1) cnt[k]--;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};