头像

Snowlanuck




离线:2小时前


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

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, A[N], B[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> A[i];
    for (int i = 1; i <= m; i ++) cin >> B[i];

    for (int i = 1, j = 1; i <= n; i ++, j ++)
    {
        while (j <= m && B[j] != A[i]) j ++;
        if (j > m) { puts("No"); return 0; }
    }

    puts("Yes");

    return 0;
}


活动打卡代码 AcWing 102. 最佳牛围栏

Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-6;
int n, f;
double A[N], s[N];

bool check(double x)
{
    for (int i = 1; i <= n; i ++)
        s[i] = A[i] + s[i - 1] - x;
    double mins = 0;
    for (int i = f; i <= n; i ++)
    {
        mins = min(mins, s[i - f]);
        if (s[i] >= mins) return true;
    }
    return false;
}

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

    double l = 0, r = 0;
    for (int i = 1; i <= n; i ++)
    {
        cin >> A[i];
        r = max(r, A[i]);
    }

    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    cout << (int)(r * 1000);

    return 0;
}


活动打卡代码 AcWing 99. 激光炸弹

Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 1;
int n, r, A[N + 10][N + 10];

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

    int x, y, v;
    while (n -- && cin >> x >> y >> v)
        A[x + 1][y + 1] += v;

    for (int i = 1; i < N; i ++)
        for (int j = 1; j < N; j ++)
            A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];

    int ans = 0;
    for (int i = 1; i < N; i ++)
        for (int j = 1; j < N; j ++)
        {
            int nx = i + r - 1; if (nx >= N) nx = 5000;
            int ny = j + r - 1; if (ny >= N) ny = 5000;
            int v = A[nx][ny] - A[nx][j - 1] - A[i - 1][ny] + A[i - 1][j - 1];
            //printf("%d %d, %d %d = %d\n", i, j, nx, ny, v);
            ans = max(ans, v);
        }

    cout << ans;

    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 6, INF = 0x3f3f3f3f,
dx[5] = {0,0,1,-1,0},
dy[5] = {1,-1,0,0,0};
int n, A[N][N], B[N][N];

void turn(int x, int y)
{
    for (int i = 0; i < 5; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > 5 || ny < 1 || ny > 5) continue;
        B[nx][ny] = !B[nx][ny];
    }
}

int main()
{
    int T; cin >> T;
    while (T --)
    {
        for (int i = 1; i <= 5; i ++)
            for (int j = 1; j <= 5; j ++)
                scanf("%1d", &A[i][j]);

        int res = INF;
        for (int i = 0; i < 32; i ++)
        {
            int cnt = 0;
            memcpy(B, A, sizeof A);
            for (int j = 0; j < 5; j ++)
                if (!(i >> j & 1)) turn(1, j + 1), cnt ++;

            for (int j = 1; j <= 4; j ++)
                for (int k = 1; k <= 5; k ++)
                    if (!B[j][k]) turn(j + 1, k), cnt ++;

            bool flag = true;
            for (int j = 1; j <= 5; j ++)
                for (int k = 1; k <= 5; k ++)
                    if (!B[j][k]) { flag = false; break; }

            if (flag) res = min(res, cnt);
        }

        if (res > 6) res = -1;
        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
    LL a, b, mod;
    cin >> a >> b >> mod;

    LL res = 0;

    while (a)
    {
        if (a & 1) res = (res + b) % mod;
        b = (b + b) % mod;
        a >>= 1;
    }

    cout << res;

    return 0;
}


活动打卡代码 AcWing 1282. 搜索关键词

Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10, S = 55, M = 1e6 + 10;

int n, tr[N * S][26], cnt[N * S], idx;
int ne[N * S];

void insert(string str)
{
    int p = 0;
    for (int i = 0; i < str.size(); i ++)
    {
        int u = str[i] - 'a';
        if (!tr[p][u]) tr[p][u] = ++ idx;
        p = tr[p][u];
    }
    cnt[p] ++;
}

void build()
{
    queue<int> q;
    for (int i = 0; i < 26; i ++)
        if (tr[0][i]) q.push(tr[0][i]);

    while (q.size())
    {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i ++)
        {
            int p = tr[u][i];
            if (!p) tr[u][i] = tr[ ne[u] ][i];
            else
            {
                ne[p] = tr[ ne[u] ][i];
                q.push(p);
            }
        }
    }
}

int main()
{
    int T; cin >> T;
    while (T --)
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        cin >> n; string str;
        for (int i = 0; i < n; i ++)
        {
            cin >> str;
            insert(str);
        }

        build();
        cin >> str;

        int res = 0;
        for (int i = 0, j = 0; i < str.size(); i ++)
        {
            int u = str[i] - 'a';
            j = tr[j][u];

            int p = j;
            while (p)
            {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }

        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 265. 营业额统计

Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef long long LL;
set<int> s;

int main()
{
    int n, x; cin >> n;

    LL ans = 0; s.insert(-INF), s.insert(INF);
    while (n -- && cin >> x)
    {
        if (s.size() == 2) ans += x, s.insert(x);
        else
        {
            auto k = s.lower_bound(x);
            if (*k != x)
            {
                auto a = k;
                ans += min(abs(*(-- a) - x), abs(*k - x));
                s.insert(x);
            }
        }
    }

    cout << ans;

    return 0;
}


活动打卡代码 AcWing 253. 普通平衡树

Snowlanuck
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
struct Node 
{
    int l, r;
    int key, val;
    int cnt, size;
}tr[N];

int root, idx;

void push_up(int u)
{
    tr[u].size = tr[ tr[u].l ].size + tr[ tr[u].r ].size + tr[u].cnt;
}

int get_node(int key)
{
    tr[ ++ idx ].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int& u) //右旋
{
    int p = tr[u].l;
    tr[u].l = tr[p].r, tr[p].r = u, u = p;
    push_up(tr[u].r), push_up(u);
}

void zag(int& u) //左旋
{
    int p = tr[u].r;
    tr[u].r = tr[p].l, tr[p].l = u, u = p;
    push_up(tr[u].l), push_up(u);
}

void build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    push_up(root);

    if (tr[1].val < tr[2].val) zag(root);
}

void insert(int& p, int key)
{
    if (!p) p = get_node(key);
    else if (tr[p].key == key) tr[p].cnt ++;
    else if (tr[p].key > key)
    {
        insert(tr[p].l, key);
        if (tr[ tr[p].l ].val > tr[p].val) zig(p);
    }
    else
    {
        insert(tr[p].r, key);
        if (tr[ tr[p].r ].val > tr[p].val) zag(p);
    }
    push_up(p);
}

void remove(int& p, int key)
{
    if (!p) return;
    if (tr[p].key == key)
    {
        if (tr[p].cnt > 1) tr[p].cnt --;
        else if (tr[p].l || tr[p].r)
        {
            if (!tr[p].r || tr[ tr[p].l ].val > tr[ tr[p].r ].val)
            {
                zig(p);
                remove(tr[p].r, key);
            }
            else
            {
                zag(p);
                remove(tr[p].l, key);
            }
        }
        else p = 0;
    }
    else if (tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);

    push_up(p);
}

int get_rank_by_key(int p, int key)
{
    if (!p) return 0;
    if (tr[p].key == key) return tr[ tr[p].l ].size + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
    return tr[ tr[p].l ].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank)
{
    if (!p) return INF;
    if (tr[ tr[p].l ].size >= rank) return get_key_by_rank(tr[p].l, rank);
    if (tr[ tr[p].l ].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[ tr[p].l ].size - tr[p].cnt);
}

int get_prev(int p, int key)
{
    if (!p) return -INF;
    if (tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key)
{
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();

    cin >> n;
    int op, x;
    while (n -- && cin >> op >> x)
    {
        if (op == 1) insert(root, x);
        else if (op == 2) remove(root, x);
        else if (op == 3) cout << (get_rank_by_key(root, x) - 1) << endl;
        else if (op == 4) cout << get_key_by_rank(root, x + 1) << endl;
        else if (op == 5) cout << get_prev(root, x) << endl;
        else cout << get_next(root, x) << endl;
    }

    return 0;
}


活动打卡代码 AcWing 255. 第K小数

Snowlanuck
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 1e4 + 10;
int n, m, A[N];
vector<int> nums;

struct Node{int l, r, cnt;}tr[N * 4 + N * 17];
int root[N], idx;

int find(int x)
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int build(int l, int r)
{
    int p = ++ idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if (l == r) { tr[q].cnt ++; return q; }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[ tr[q].l ].cnt + tr[ tr[q].r ].cnt;
    return q;

}

int query(int q, int p, int l, int r, int k)
{
    if (l == r) return r;
    int cnt = tr[ tr[q].l ].cnt - tr[ tr[p].l ].cnt;
    int mid = l + r >> 1;
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> A[i];
        nums.push_back(A[i]);
    }

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

    root[0] = build(0, nums.size() - 1);

    for (int i = 1; i <= n; i ++)
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(A[i]));

    int l, r, k;
    while (m -- && cin >> l >> r >> k)
        cout << nums[ query(root[r], root[l - 1], 0, nums.size() - 1, k) ] << endl;

    return 0;
}


活动打卡代码 AcWing 247. 亚特兰蒂斯

Snowlanuck
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct Segment
{
    double x, y1, y2;
    int k;
}seg[N * 2];

struct Node
{
    int l, r, cnt;
    double len;
}tr[N * 8];

int n;
vector<double> ys;

int find(double y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void push_up(int u)
{
    if (tr[u].cnt) tr[u].len = ys[ tr[u].r + 1 ] - ys[ tr[u].l ];
    else if (tr[u].l != tr[u].r) tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    else tr[u].len = 0;
}

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

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        push_up(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        push_up(u);
    }
}

int main()
{
    int T = 1;
    while (cin >> n && n)
    {
        ys.clear();
        for (int i = 0, j = 0; i < n; i ++)
        {
            double x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            seg[j ++] = {x1, y1, y2, 1};
            seg[j ++] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);
        }

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

        build(1, 0, ys.size() - 2);

        sort(seg, seg + n * 2, [](Segment A, Segment B){ return A.x < B.x; });

        double res = 0;
        for (int i = 0; i < n * 2; i ++)
        {
            if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
        }

        printf("Test case #%d\n", T ++);
        printf("Total explored area: %.2lf\n\n", res);
    }

    return 0;
}