头像

okjhzwVwUa


访客:204

离线:17小时前


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

#include <cstdio>

const int N = 1000010;

int a[N], q[N], n, k;

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

    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
}


活动打卡代码 AcWing 827. 双链表

```

include [HTML_REMOVED]

using namespace std;

const int N = 100010;

int l[N], r[N], e[N], idx;

void init() {
r[0] = 1;
l[1] = 0;
idx = 2;
}

void add(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}

void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}

int main(){
init();
int m;
cin >> m;
while (m–) {
string op;
int k,x;
cin >> op;
if (op == “L”) {
cin >> x;
add(0, x);
} else if (op == “R”) {
cin >> x;
add(l[1],x);
} else if (op == “D”) {
cin >> k;
remove(k+1);
} else if (op == “IL”) {
cin >> k >> x;
add(l[k+1], x);
} else {
cin >> k >> x;
add(k+1, x);
}
}

 for (int i = r[i]; i != 1; i = r[i]) cout << e[i] << " ";

}
```



活动打卡代码 AcWing 803. 区间合并

课上代码看不懂, 自己拿栈写了一个

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

typedef pair<int,int> PII;

vector<PII> ranges;

int merge(vector<PII> &ranges) {
    if (!ranges.size()) return 0;
    stack<PII> res;
    auto one = ranges[0];
    res.push({one.first,one.second});
    for (int i = 1; i < ranges.size(); i++) {
        auto cur = res.top();
        int st = cur.first, ed = cur.second;
        auto p = ranges[i];
        if (p.first > ed) res.push({p.first,p.second});
        else {
            ed = max(ed, p.second);
            res.pop();
            res.push({st,ed});
        }
    }

    return res.size();
}


int main () {
    int n;
    cin >> n;
    while (n--) {
        int l,r;
        cin >> l >> r;
        ranges.push_back({l,r});
    }
    sort(ranges.begin(), ranges.end());
    cout << merge(ranges);

}




新鲜事 原文

之前我一直很羡慕 python 代码的简洁,虽然现在一直用 C++ 做题,每次看到简洁的 python 代码就跃跃欲试想写 python,最近下手用 python 写了几道题,然后发现只要涉及到数组下标操作的,python 还没 C++ 简洁。。。再加上 auto 和 stl, 妈呀, C++ 真香


活动打卡代码 AcWing 802. 区间和

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> alls;
vector<pair<int,int>> add, query;

int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = (l+r) >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

int main() {
    int n,m;
    cin >> n >> m;
    int a[2*m+n+1] = {0};
    while (n--) {
        int x,c;
        cin >> x >> c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    while (m--) {
        int l,r;
        cin >> l >> r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for (auto item : add) a[find(item.first)] += item.second;

    for (int i = 1; i <= alls.size(); i++) a[i] += a[i - 1];

    for (auto item : query) {
        int l = find(item.first), r = find(item.second);
        cout << a[r] - a[l-1] << endl;
    }

}



#include <iostream>

using namespace std;

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

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        int res = 0;
        while (x) x -= lowbit(x), res++;
        cout << res << " ";
    }
}



#include <iostream>

using namespace std;

const int N = 100010;

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

int main() {
    cin>>n>>m>>x;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    int i = 0, j = m - 1;
    while (i < n && j >= 0) {
        if (a[i] + b[j] > x) j--;
        else if (a[i] + b[j] < x) i++;
        else {
            cout << i << " " << j << endl;
            break;
        }
    }

    // for (int i = 0, j = m - 1; i < n; i++) {
    //     while (j >= 0 && a[i] + b[j] > x) j--;
    //     if (a[i] + b[j] == x) {
    //         cout << i << " " << j << endl;
    //         break;
    //     }
    // }
    return 0;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];
unordered_map<int, int> m;

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

    int res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        m[a[i]]++;
        while (m[a[i]] > 1) {
            m[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res;
}



我喜欢用 cin cout 因为不喜欢打%和&, 但是 cin cout 普遍慢,所以需要加优化,
但是优化代码我懒得次次敲,就整了个模板,如下, 优化后的速度还是很可观的,
不比 scanf printf 慢。

#include <iostream>

using namespace std;

void before() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    before();
    //从下面开始做题

    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

#include <cstdio>

const int N = 1010;

int b[N][N];

void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2+1][y1] -= c;
    b[x1][y2+1] -= c;
    b[x2+1][y2+1] += c;
}

int main() {
    int n,m,q,c,k,x1,y1,x2,y2;
    scanf("%d%d%d", &n,&m,&q);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &k);
            insert(i,j,i,j,k);
        }
    }

    while (q--) {
        scanf("%d%d%d%d%d", &x1,&y1,&x2,&y2,&c);
        insert(x1,y1,x2,y2,c);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] += b[i][j-1] + b[i-1][j] - b[i-1][j-1];
            printf("%d ", b[i][j]);
        }
        puts("");
    }
}