头像

lovebecky




离线:2021-09-04 17:38


最近来访(103)
用户头像
热带企鹅
用户头像
yxc的小迷妹
用户头像
香格里拉
用户头像
宇宙有边
用户头像
HD_7
用户头像
是阿亮啊
用户头像
ceer
用户头像
好人一生平安
用户头像
163.com
用户头像
594699
用户头像
小王今天吃什么
用户头像
Cabin-65--
用户头像
John_0
用户头像
zxy123
用户头像
可乐可口
用户头像
一切皆有解
用户头像
天涯墨客
用户头像
NothingAtall.
用户头像
垫底抽風
用户头像
冰语晨星


lovebecky
2019-04-27 16:47
#include <cstdio>
#include <cstring>

using namespace std;
using ll = long long;
const int maxn = 1e5 + 10;

int n, m;
int a[maxn], s[maxn], c[maxn]; // a为原数组,s为前缀和数组,c为树状数组

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

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

int ask(int x)
{
    int ans = a[x];
    for (; x; x -= lowbit(x))
        ans += c[x];
    return ans;
}

int main()
{
    freopen("/Users/zhbink/Documents/C++/C++/in.txt","r",stdin);
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    char ops[2];
    int l, r, d;

    for (int i = 1; i <= m; i++)
    {
        scanf("%s%d", ops, &l);
        if (ops[0] == 'Q')
            printf("%d\n", ask(l));
        else
        {
            scanf("%d%d", &r, &d);
            add(l, d);
            add(r+1, -d);
        }
    }

    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

lovebecky
2019-04-19 14:59
#include <iostream>
#include <deque>
using namespace std;
const int maxn = 1000100;
int a[maxn], ans1[maxn], ans2[maxn];
int n, k;
deque<int>q1, q2;
int main()
{
    // freopen("/Users/zhbink/Documents/C++/C++/in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        while(!q1.empty() && i - q1.front() >= k) q1.pop_front();
        while(!q1.empty() && a[i] <= a[q1.back()]) q1.pop_back();
        q1.push_back(i);
        if(i >= k - 1) ans1[i+1-k] = a[q1.front()];

        while(!q2.empty() && i - q2.front() >= k) q2.pop_front();
        while(!q2.empty() && a[i] >= a[q2.back()]) q2.pop_back();
        q2.push_back(i);
        if(i >= k - 1) ans2[i+1-k] = a[q2.front()];
    }


    for (int i = 0; i + k <= n; i++)
        cout << ans1[i] << " \n"[i+k==n];
    for (int i = 0; i + k <= n; i++)
        cout << ans2[i] << " \n"[i+k==n];
    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

lovebecky
2019-04-16 14:24
#include <iostream>
#include <deque>
using namespace std;

int n, m;
const int INF = 0x3f3f3f3f;
const int maxn = 3000010;
int a[maxn], s[maxn];
deque<int> q;

int main()
{
    // freopen("/Users/zhbink/Documents/C++/C++/in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin >> n >> m;

    int ans = -INF;
    for (int i = 1; i <= n; i ++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        while (q.size() && q.front() + m < i) q.pop_front();
        ans = max(ans, s[i] - s[q.front()]);
        while (q.size() && s[q.back()] >= s[i]) q.pop_back();
        q.push_back(i);
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

lovebecky
2019-01-28 18:50
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 100050;
int a[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
        scanf("%d", &a[i]);

    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n; i ++ ) 
        ans += abs(a[n >> 1] - a[i]);

    cout << ans << endl;
    return 0;
}




活动打卡代码 AcWing 103. 电影

lovebecky
2019-01-28 18:20
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 200050;

struct movie {
    int i, very, like; // 电影的编号,很高兴的人,比较高兴的人
}movies[N];

inline bool cmp(const movie &a, const movie &b) {
    return a.very > b.very || a.very == b.very && a.like > b.like;
}

unordered_map<int, int> map1; // 会first语言的人有second个

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

    // 第i个科学家会语言t
    for (int i = 0; i < n; i ++ ) {
        int t;
        scanf("%d", &t);
        map1[t] ++;
    }

    scanf("%d", &m);

    // 电影i的语言
    for (int i = 0; i < m; i ++ ) {
        int lang;
        scanf("%d", &lang);
        movies[i].i = i;
        // 如果有会lang的人,电影i可以very的人 = map1[i]
        if (map1.count(lang)) movies[i].very = map1[lang];
    }

    // 电影i的字幕
    for (int i = 0; i < m; i ++ ) {
        int subtitle;
        scanf("%d", &subtitle);
        // 如果有会subtitle的人,电影i可以like的人 = map1[i]
        if (map1.count(subtitle)) movies[i].like = map1[subtitle];
    }

    sort(movies, movies + m, cmp);

    printf("%d\n", movies[0].i + 1);
    return 0;
}



lovebecky
2019-01-27 22:32
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int l = lower_bound(nums.begin(), nums.end(), k) - nums.begin();
        int r = upper_bound(nums.begin(), nums.end(), k) - nums.begin();
        return r - l;
    }
};



lovebecky
2019-01-27 22:29
class Solution {
public:
    char firstNotRepeatingChar(string s) {
        unordered_map<char, int> hash;
        for (auto x : s) hash[x]++;
        char ans = '#';
        for (auto ch : s){
            if (hash[ch] == 1){
                ans = ch;
                break;
            }
        }
        return ans;
    }
};



lovebecky
2019-01-27 22:12
class Solution {
public:
    unordered_map<char, int> hash;
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char, int> hash;
        int ans = 0;
        for(int i = 0, j = 0; j < s.size(); j ++){
            if(++ hash[s[j]] > 1){
                while(hash[s[j]] != 1){
                    hash[s[i]] --;
                    i ++;
                }
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};



lovebecky
2019-01-27 21:44
class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> f(m + 1, vector<int>(n, -1));

        for (int i = 0; i < m; i ++ ) 
            for (int j = 0; j < n; j ++ ) {
                f[i][j] = grid[i][j];
                if (i && j) {
                    f[i][j] += max(f[i-1][j], f[i][j-1]);
                }
                else {
                    if (i) f[i][j] += f[i-1][j];
                    if (j) f[i][j] += f[i][j-1];
                }
            }
        return f[m-1][n-1];
    }
};



lovebecky
2019-01-27 20:56
class Solution {
public:
    map<int ,char> map1;
    unordered_set<string> hash;
    int getTranslationCount(string s) {
        for (int i = 0; i <= 25; i ++ ) {
            map1[i] = 'a' + i;
        }
        dfs(s, 0, "");
        return hash.size();
    }

    void dfs(string s, int pos, string str) {
        if (pos == s.size()) {
            hash.insert(str);
            return ;
        }
        if (pos > s.size()) return;

        int cur = s[pos] - '0', next = cur; 
        if (pos < s.size() - 1) 
            next = (next * 10) + (s[pos + 1] - '0');

        dfs(s, pos + 1, str + map1[cur]);
        if (next >= 10 && next <= 25) dfs(s, pos + 2, str + map1[next]);
    }

};