头像

leon_ltox




离线:13小时前


最近来访(2)
用户头像
lyxer
用户头像
听风_4

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

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

using namespace std;

const int N = 100010;
int e[N], l[N], r[N], idx;

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

void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[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()
{
    int m;
    cin >> m;

    init();

    int k, x;
    while (m -- )
    {
        string op;
        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 if(op == "IR")
        {
            cin >> k >> x;
            add(k + 1, x);
        }
    }

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


活动打卡代码 AcWing 826. 单链表

leon_ltox
21小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int e[N], ne[N];
int head, idx;

void init()
{
    head = -1;
    idx = 0;
}

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

void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

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


int main()
{
    int m , x, k;

    init();

    cin >> m;
    while (m -- )
    {

        char op;
        cin >> op; 

        if(op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            cin >> k;   
            if(!k) head = ne[head];
            else remove(k - 1);
        }
        else if(op == 'I')
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for(int i = head; i != -1; i = ne[i])
    {
        cout<< e[i]<< " ";
    }

    return 0;
}


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

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

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
vector<PII> segs;

int n;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    int st = -2e9;
    int ed = -2e9;
    sort(segs.begin(), segs.end());
    for(auto seg: segs)
    {
        if(ed < seg.first)
        {
            if(st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else{
            ed = max(ed, seg.second);
        }
    }
    if(ed != -2e9) res.push_back({st, ed});

    segs = res;
}

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

    int st, ed;
    for(int i = 0; i < n; i++ )
    {
        scanf("%d%d", &st, &ed);
        segs.push_back({st, ed});
    }



    merge(segs);

    cout << segs.size();


    return 0;
}


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

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

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;
int a[N], s[N];
int n, m;


vector<int> alls;
vector<PII> 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 r + 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++ )
    {
        int x, c;
        scanf("%d%d", &x, &c);

        add.push_back({x, c});
        alls.push_back(x);
    }

    for(int i = 0; i < m; i++)
    {
        int l, r;
        scanf("%d%d", &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++) s[i] = s[i - 1] + a[i];

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


    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;
int q[N];

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

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

    int i = 0;
    while(i < n)
    {
        if(q[i] == 0) 
        {
            printf("0 ");
            i ++;
            continue;
        }
        int tmp = q[i];
        int t = 0, k = 0, res = 0;
        while (t < tmp)
        {
            if(t == 0) t += 1;
            else
            {
                t *= 2;
                k++;
            }
        }

        res = 1;
        if(t == q[i]) res = 1;
        else
        {
            k--;
            tmp -= pow(2, k);
            for(int j = k - 1; j >= 0 && tmp != 0; j--)
            {
                if(tmp - pow(2, j) >= 0)
                {
                    //printf("%d /", j);
                    res ++;
                    tmp -= pow(2, j);
                }
            }
        }

        printf("%d ", res);
        i++;
    }

    return 0;
}


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

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

using namespace std;

const int N = 100010;
int a[N], b[N];

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

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

    for(int i = 0; i < m; i++ )
    {
        scanf("%d", &b[i]);
    }

    int i = 0, j = 0;
    while(i < n && j < m)
    {
        if(a[i] == b[j]) i++;
        j++;
    }


    // cout<< i << endl<<j << endl;
    if(i == n) puts("Yes");
    else puts("No");



    return 0;
}



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

using namespace std;

const int N = 100010;
int A[N], B[N];

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

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

    for(int i = 0; i < m; i++ )
    {
        scanf("%d", &B[i]);
    }

    for(int i = 0, j = m - 1; i < n && j >= 0; i ++ )
    {
        while(j >= 0)
        {
            if(A[i] + B[j] > x) j -- ;
            else if(A[i] + B[j] == x)
            {
                printf("%d %d\n", i, j);
                j -- ;
                continue;
            }
            else if(A[i] + B[j] < x)
            {
                break;
            }
        }
    }

    return 0;
}



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

using namespace std;

const int N = 100010;
int a[N], s[N];


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

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

    int res = 0;
    for(int i = 0, j = 0; i < n; i++ )
    {
        s[a[i]]++;

        while(s[a[i]] > 1)
        {
            s[a[j]] --;
            j++;
        }
        res = max(res, i - j + 1);
    }

    printf("%d", res);

    return 0;
}


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

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

using namespace std;

const int N = 1010;
int a[N][N], b[N][N];

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

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

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

    }

    int x1, y1, x2, y2, c;
    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 - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            printf("%d ", b[i][j]);
        }
        puts("");
    }

    return 0;

}


活动打卡代码 AcWing 2041. 干草堆

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

using namespace std;

const int N = 1000010;
int b[N];

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

    int l, r;
    while(k--)
    {
        scanf("%d%d", &l, &r);
        b[l]++;
        b[r + 1]--;
    }

    for (int i = 1; i <= n; i ++)
    {
        b[i] += b[i - 1];
    }

    sort(b + 1, b + 1 + n);

    printf("%d", b[n / 2 + 1]);

    return 0;
}