个人空间 - AcWing

hbq

$\underbrace{\color{lime}{\Huge ACCCCC}}_{\infty\text{ times}}$

阅读量

3340

+关注发消息

离线：19分钟前

最近来访(186)

石头_44

acwing_xyy

13386306663

zero1

meiis

硝基苯_5

Codemon

chtld

不拿周赛牌不改名

Kazimierz

欧耶

陈容升

Cola_85

平凡的小苏

incra

L-China

Egbert-Lannister.

度_7

acwing_5735

心里没有一点AC数

活动打卡代码 AcWing 243. 一个简单的整数问题2（算法提高课）

hbq
20分钟前

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

using namespace std;

const int N = 100010;

typedef long long LL;

int n, m;
int w[N];

struct Node
{
    int l, r;
    LL sum, add;
}tr[N << 2];

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1],  tr[u << 1 | 1]);
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) // 如果有标记的话
    {
        left.add += root.add, left.sum += (left.r + 1ll  - left.l) * root.add;
        right.add += root.add, right.sum += (right.r + 1ll - right.l) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    // 这里初始化的代码写法多种多样 很自由
    tr[u] = {l, r};
    if (l == r)
    {
        tr[u].add = 0;
        tr[u].sum = w[r];
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r) 
    {
        tr[u].sum += (tr[u].r + 1ll - tr[u].l) * d;
        tr[u].add += d;
    }
    else // 分裂区间
    {
        pushdown(u); // 懒标记  // 一定要放在最前
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u); // 由子节点向父节点传递
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}


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

    build(1, 1, n);

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

    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C')
        {
            scanf("%d", &d);
            modify(1, l, r, d);
        }
        else printf("%lld\n", query(1, l, r));
    }
    return 0;
}

            

活动打卡代码 AcWing 3805. 环形数组（每日一题）

hbq
20分钟前

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

using namespace std;

typedef long long LL;
const int N = 200010;
const LL INF = 1e18;

int n, m;
int w[N];

struct Node
{
    int l, r;
    LL dt, mn;
}tr[N * 4];

void pushup(int u)
{
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}

void pushdown(int u)
{
    auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.dt += root.dt, l.mn += root.dt;
    r.dt += root.dt, r.mn += root.dt;
    root.dt = 0;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, w[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].dt += d, tr[u].mn += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].mn;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = INF;
        if (l <= mid ) res = query(u << 1, l, r);
        if (r > mid) res = min(res, query(u << 1 | 1, l, r));
        return res;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
    build(1, 0, n - 1);
    scanf("%d", &m);
    while (m -- )
    {
        int l, r, d;
        char c;
        scanf("%d %d%c", &l, &r, &c);
        if (c == '\n') //是换行符 表示只有两个数字 == 求最小值
        {
            if (l <= r) printf("%lld\n", query(1, l, r));
            else printf("%lld\n", min(query(1, l, n - 1), query(1, 0, r)));
        }
        else // 是空格 表示有三个数字 : 添加操作
        {
            scanf("%d", &d);
            if (l <= r) update(1, l, r, d);
            else update(1, l, n - 1, d), update(1, 0, r, d);
        }
    }

    return 0;
}

            

活动打卡代码 AcWing 3805. 环形数组

hbq
20分钟前

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

using namespace std;

typedef long long LL;
const int N = 200010;
const LL INF = 1e18;

int n, m;
int w[N];

struct Node
{
    int l, r;
    LL dt, mn;
}tr[N * 4];

void pushup(int u)
{
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}

void pushdown(int u)
{
    auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.dt += root.dt, l.mn += root.dt;
    r.dt += root.dt, r.mn += root.dt;
    root.dt = 0;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, w[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].dt += d, tr[u].mn += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].mn;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = INF;
        if (l <= mid ) res = query(u << 1, l, r);
        if (r > mid) res = min(res, query(u << 1 | 1, l, r));
        return res;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
    build(1, 0, n - 1);
    scanf("%d", &m);
    while (m -- )
    {
        int l, r, d;
        char c;
        scanf("%d %d%c", &l, &r, &c);
        if (c == '\n') //是换行符 表示只有两个数字 == 求最小值
        {
            if (l <= r) printf("%lld\n", query(1, l, r));
            else printf("%lld\n", min(query(1, l, n - 1), query(1, 0, r)));
        }
        else // 是空格 表示有三个数字 : 添加操作
        {
            scanf("%d", &d);
            if (l <= r) update(1, l, r, d);
            else update(1, l, n - 1, d), update(1, 0, r, d);
        }
    }

    return 0;
}

            

活动打卡代码 AcWing 3804. 构造字符串

hbq
33分钟前

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

using namespace std;

const int N = 100010;

int n, k;
char s1[N], s2[N];
bool st[26]; // 存储每个字母是否出现过  // 实现 get_min 和 get_next

char get_min()
{
    // 这样写也可以
    // char c = s1[0];
    // for (int i = 1; i < n; i ++ )
    //     if (s1[i] < c)
    //         c = s1[i];
    // return c;

    for (int i = 0; i < 26; i ++ )
        if (st[i])
            return i + 'a';
    return -1; // 数据保证一定有解
}

char get_next(int t) // 返回比 t 大的下一个字母
{
    for (int i = t + 1; i < 26; i ++ )
        if (st[i])
            return i + 'a';
    return -1; // 找不到返回 -1 
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &k);
        scanf("%s", s1);
        memset(st, 0, sizeof st); // 多组数据 注意清空
        for (int i = 0; i < n; i ++ ) st[s1[i] - 'a'] = true;
        if (k > n)
        {
            printf("%s", s1);
            char c = get_min();
            // 然后输出最小的 s1 中最小的字符
            for (int i = n; i < k; i ++ ) printf("%c", c);
            puts("");
        }
        else
        {
            s2[k] = 0; // 字符串结尾 // puts遇到 '\0'停止  // 表示字符串结尾
            for (int i = k - 1; ~i; i -- ) // 从 `t` 的最后一位开始找 
            {
                char c = get_next(s1[i] - 'a');
                if (c != -1)
                {
                    s2[i] = c;
                    for (int j = 0; j < i; j ++ ) s2[j] = s1[j];
                    break; // 能找到直接 break
                }
                s2[i] = get_min(); // 如果找不到的话  这一位就填最小值 ： 为了保证字典序最小
            }
            puts(s2); 
        }
    }
    return 0;
}

            

活动打卡代码 AcWing 3803. 数组去重

hbq
15小时前

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

using namespace std;

const int N = 55;

int w[N];
int n;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        vector<bool> st(1010); // 判重数组
        vector<int> b; // 答案
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> w[i];
        for (int i = n - 1; ~i; i -- ) 
        {
            if (st[w[i]]) continue;
            b.push_back(w[i]);
            st[w[i]] = true;
        }

        cout << b.size() << endl;
        for (int i = b.size() - 1; ~i; i -- ) printf("%d ", b[i]);
        puts("");
    }
    return 0;
}


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

using namespace std;

const int N = 55;

int n;
int w[N];

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
        for (int i = 0; i < n; i ++ )
            for (int j = i + 1; j < n; j ++ ) 
                if (w[i] == w[j])
                    w[i] = -1; // 表示删掉这个数
        int k = 0;
        for (int i = 0; i < n; i ++ )
            if (w[i] != -1) k ++ ;
        printf("%d\n", k);
        for (int i = 0; i < n; i ++ )
            if (w[i] != -1) printf("%d ", w[i]);
        puts("");
    }
    return 0;
}

            

活动打卡代码 AcWing 1277. 维护序列

hbq
17小时前

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

using namespace std;

const int N = 100010;

typedef long long LL;

int n, m, p;
int w[N];

struct Node
{
    int l, r;
    int sum, add, mul;
}tr[N << 2];

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = (l.sum + r.sum) % p;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void eval(Node &t, int add, int mul)  // 推公式
{
    t.sum = (1ll * t.sum * mul + (t.r + 1ll - t.l) * add) % p; // 更新 sum 
    t.mul = 1ll * t.mul * mul % p;
    t.add = (1ll * t.add * mul + add) % p;
}

void pushdown(int u)
{
    eval(tr[u << 1], tr[u].add, tr[u].mul);
    eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
    tr[u].add = 0, tr[u].mul = 1; // 清空根节点的懒标记 
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0, 1};
    else
    {
        tr[u] = {l, r, 0, 0, 1}; // 这里主要作用是 初始化 l, r 和 add、mul    其中 sum由于 会pushup 这里可以 = 随机数
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}   

void modify(int u, int l, int r, int add, int mul)
{
    if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, add, mul);
        if (r > mid) modify(u << 1 | 1, l, r, add, mul);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum % p;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;  // 这里不能写 += ？？？？ 否则即使 += 完再 % 

    return sum;
}

int main()
{
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    scanf("%d", &m);

    build(1, 1, n);

    while (m -- )
    {
        int t, l, r, d;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1)
        {
            scanf("%d", &d);
            modify(1, l, r, 0, d);
        }
        else if (t == 2)
        {
            scanf("%d", &d);
            modify(1, l, r, d, 1);
        }
        else printf("%d\n", query(1, l, r));
    }

    return 0;
}

            

活动打卡代码 AcWing 797. 差分

                #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

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

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        insert(i, i, a[i]);
    }
    while (m --)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

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

            

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

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

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], 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()
{
    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]);
        }
    while (q -- )
    {
        int x1, y1, x2, y2, c;
        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]; // 将 b[] 转化为自己的前缀和 即 转化为 a[]
            printf("%d ", b[i][j]);
        }
        puts("");
    }
    return 0;
}

            

活动打卡代码 AcWing 1270. 数列区间最大值

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

using namespace std;

const int N = 100010;

int n, m;
int w[N];

struct Node
{
    int l, r;
    int v;
}tr[N << 2];


void pushup(Node &u, Node &l, Node &r)
{
    u.v = max(l.v, r.v);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r)
    {
        tr[u].v = w[l];
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int val = INT_MIN;
    if (l <= mid) val = max(val, query(u << 1, l, r));
    if (r > mid) val = max(val, query(u << 1 | 1, l, r));
    return val;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);

    int l, r;
    while (m -- )
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}


            

活动打卡代码 AcWing 1273. 天才的记忆

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

using namespace std;

const int N = 200010, M = 18; // 2^17 > 200010;

int n, m;
int w[N];
int f[N][M];

void init()
{
    for (int j = 0; j < M; j ++ ) // 枚举区间长度
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )  // 枚举左右区间
            if (!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r)
{
    int k = log(r - l + 1) / log(2); // 2^k <= len 
    return max(f[l][k],  f[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); // 基于dp  下标从 1 开始

    init(); // 初始化st表

    scanf("%d", &m);
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}


线段树
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, w[N];
int m;

struct Node
{
    int l, r;
    int v;
}tr[N << 2];

void pushup(Node &u, Node &l, Node &r)
{
    u.v = max(l.v, r.v);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) tr[u].v = w[l];
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int val = -(1 << 30);
    if (l <= mid) val = max(val, query(u << 1, l, r));
    if (r > mid) val = max(val, query(u << 1 | 1, l, r));
    return val;
}

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

    scanf("%d", &m);
    int l, r;
    while (m -- )
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}

            