头像

就是个渣渣




离线:23天前


最近来访(17)
用户头像
多财多亿
用户头像
arisingstar
用户头像
zzp
用户头像
jasonho
用户头像
Leonis
用户头像
edgdcgxgbx
用户头像
Positive_5
用户头像
zombotany
用户头像
NBxiang
用户头像
阿P
用户头像
Jackyc
用户头像
qwwjh
用户头像
itdef
用户头像
Gn_6

活动打卡代码 AcWing 2816. 判断子序列

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n, m, a[N], b[N];

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int j = 0; j < m; j ++) cin >> b[j];

    bool flag = false;
    for (int i = 0, j = 0; i < n && j < m; i ++, j ++) {
        while (j < m && b[j] != a[i]) j ++;
        if (i == n - 1) flag = true;
    }

    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


活动打卡代码 LeetCode 7. 整数反转

class Solution {
public:
    int reverse(int x) {
        int res = 0;

        while (x) {
            if (res > 0 && res > (INT_MAX - x % 10) / 10) return 0;
            if (res < 0 && res < (INT_MIN - x % 10) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};


活动打卡代码 LeetCode 6. Z 字形变换

class Solution {
public:
    string convert(string s, int n) {
        string res;

        if (n == 1) return s;
        for (int i = 0; i < n; i ++) {
            if (i == 0 || i == n - 1) {
                for (int j = i; j < s.size(); j += 2 * n - 2) {
                    res += s[j];
                }
            } else {
                for (int j = i, k = 2 * n - 2 - i; j < s.size() || k < s.size(); j += 2 * n - 2, k += 2 * n - 2) {
                    if (j < s.size()) res += s[j];
                    if (k < s.size()) res += s[k];
                }
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i < s.size(); i ++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);

            l = i, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
        }
        return res;
    }
};



class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) {
            return find(nums2, j, nums1, i, k);
        }

        if (k == 1) {
            if (nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }

        if (nums1.size() == i) return nums2[j + k - 1];
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1]) {
            return find(nums1, i, nums2, sj, k - (sj - j));
        } else {
            return find(nums1, si, nums2, j, k - (si - i));
        }
    }
};



class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> heap;

        int res = 0;
        for (int i = 0, j = 0; i < s.size(); i ++) {
            heap[s[i]] ++;
            while (heap[s[i]] > 1) heap[s[j ++]] --;
            res = max(res, i - j + 1);
        } 
        return res;
    }
};


活动打卡代码 LeetCode 2. 两数相加

/**
 * 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:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), cur = dummy;

        int t = 0;
        while (l1 || l2 || t) {
            if (l1) t += l1->val, l1 = l1->next;
            if (l2) t += l2->val, l2 = l2->next;
            cur = cur->next = new ListNode(t % 10);
            t /= 10;
        }

        return dummy->next;
    }
};


活动打卡代码 LeetCode 1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // O(n)时间,即是否前面存在一个数。
        // si, target - si
        unordered_map<int, int> heap;
        for (int i = 0; i < nums.size(); i ++) {
            int r = target - nums[i];
            if (heap.count(r)) return {heap[r], i};
            heap[nums[i]] = i;
        }

        return {};
    }
};


活动打卡代码 AcWing 244. 谜一样的牛

就是个渣渣
2020-03-25 02:10
// 首先模拟,得到解题需要倒着做
// 倒着做,剩下牛中第ai + 1小的数, 再删除数
// 核心操作:1. 从剩余的数中找出第k小的数; 2. 删除某一个数
// 有size的平衡树可以找.
// a1 - an = 1, 树状数组维护前缀和
// x - 1; add(i, -1);
// 找最小的x使得 sum(x) == k, 二分法做
// 为什么?因为这里特殊,每一位为标志位,sum[k]表示前面有k个数,而每个索引递增,所以即第k小的数。
#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], ans[N], tr[N]; // 数学题

int lowbit(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int sum(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main() {
    scanf("%d", &n);

    for (int i = 2; i <= n; i ++) cin >> a[i];

    for (int i = 1; i <= n; i ++) add(i, 1);

    for (int i = n; i; i --) {
        int k = a[i] + 1; // 最小的第k小的数
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans[i] = l; // 找到的坐标就是该数
        add(l, -1);
    }

    for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
    return 0;
}





就是个渣渣
2020-03-24 16:41

sum_i sum_x bi

b1
b1 b2
b1 b2 b3

b1 … bx

于是
= (b1 + b2 + .. + bx) * (x + 1) - sum(x * bx)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
LL tr1[N];  // 维护b[i]的前缀和
LL tr2[N];  // 维护b[i] * i的前缀和

int lowbit(int x)
{
    return x & -x;
}

void add(LL tr[], int x, LL c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(LL tr[], int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL prefix_sum(int x)
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ )
    {
        int b = a[i] - a[i - 1];
        add(tr1, i, b);
        add(tr2, i, (LL)b * i);
    }

    while (m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q')
        {
            printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
        }
        else
        {
            scanf("%d", &d);
            // a[l] += d
            add(tr1, l, d), add(tr2, l, l * d);
            // a[r + 1] -= d
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
    }

    return 0;
}