头像

KevinYao1224

SCP-Foundation


访客:337

离线:6小时前


活动打卡代码 AcWing 136. 邻值查找

KevinYao1224
6小时前
#include <bits/stdc++.h>


using namespace std;


int main(void) {
    int n;
    scanf("%d", &n);
    set<pair<int, int> > nums;
    nums.insert(make_pair(-2e9-1, -1));
    nums.insert(make_pair(2e9+1, -1));
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        pair<int, int> now = make_pair(x, i);
        if (i > 1) {
            set<pair<int, int> >::iterator less_res, greater_res;
            greater_res = nums.lower_bound(now);
            less_res = nums.upper_bound(now);
            --less_res;

            int delta_greater_res = greater_res->first - now.first,
                delta_less_res = now.first - less_res->first;
            if (delta_greater_res < delta_less_res) {
                printf("%d %d\n", delta_greater_res, greater_res->second);
            } else {
                printf("%d %d\n", delta_less_res, less_res->second);
            }
        }
        nums.insert(now);
    }
    return 0;
}


活动打卡代码 AcWing 133. 蚯蚓

#include <bits/stdc++.h>


using namespace std;


long long a[100010];


int main(void) {
    int n, m, q, u, v, t;
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }

    sort(a + 1, a + n + 1, greater<int>());

    queue<long long> st_worms_que, new_worms_que1, new_worms_que2;
    for (int i = 1; i <= n; ++i) {
        st_worms_que.push(a[i]);
    }

    long long delta = 0;
    for (int i = 1; i <= m; ++i) {
        long long maxi_worm;
        if (!st_worms_que.empty() && (new_worms_que1.empty() ||
            st_worms_que.front() > new_worms_que1.front())) {

            if (new_worms_que2.empty() ||
                st_worms_que.front() > new_worms_que2.front()) {

                maxi_worm = st_worms_que.front();
                st_worms_que.pop();
            } else {
                maxi_worm = new_worms_que2.front();
                new_worms_que2.pop();
            }
        } else {
            if (new_worms_que2.empty() ||
                new_worms_que1.front() > new_worms_que2.front()) {

                maxi_worm = new_worms_que1.front();
                new_worms_que1.pop();
            } else {
                maxi_worm = new_worms_que2.front();
                new_worms_que2.pop();
            }
        }
        maxi_worm += delta;

        if (i % t == 0) {
            printf("%lld ", maxi_worm);
        }

        long long new_worm1 = maxi_worm * u / v,
                  new_worm2 = maxi_worm - new_worm1;
        new_worms_que1.push(new_worm1 - delta - q);
        new_worms_que2.push(new_worm2 - delta - q);

        delta += q;
    }
    putchar('\n');

    for (int i = 1; i <= n + m; ++i) {
        long long maxi_worm;
        if (!st_worms_que.empty() && (new_worms_que1.empty() ||
            st_worms_que.front() > new_worms_que1.front())) {

            if (new_worms_que2.empty() ||
                st_worms_que.front() > new_worms_que2.front()) {

                maxi_worm = st_worms_que.front();
                st_worms_que.pop();
            } else {
                maxi_worm = new_worms_que2.front();
                new_worms_que2.pop();
            }
        } else {
            if (!new_worms_que1.empty() && (new_worms_que2.empty() ||
                new_worms_que1.front() > new_worms_que2.front())) {

                maxi_worm = new_worms_que1.front();
                new_worms_que1.pop();
            } else {
                maxi_worm = new_worms_que2.front();
                new_worms_que2.pop();
            }
        }
        maxi_worm += delta;

        if (i % t == 0) {
            printf("%lld ", maxi_worm);
        }
    }
    putchar('\n');

    return 0;
}



显然,每个小组要么没有成员在队列中,要么有连续的一段成员。那么很容易想到在大队列里套着一个个小队列,每个小队列是一个小组。入队时检查当前小组是否已经有了,有了就直接插在小队列末端,否则创建新的小队列;这个检查过程使用指针来完成可以O(1)。删除时从第一个小队列的对头删除,如果发现空了就把这个小队列整个弹出去,并修改指针数组。

#include <bits/stdc++.h>


using namespace std;


struct group_que_t {
    int id;
    queue<int> que;
};


int group_id[1000010];
group_que_t *ptr[2010];


int main(void) {
    int n;
    int testcase_id = 0;
    while ((cin >> n, n) != 0) {
        ++testcase_id;
        cout << "Scenario #" << testcase_id << endl;
        for (int i = 1; i <= n; ++i) {
            int m;
            cin >> m;
            for (int j = 1; j <= m; ++j) {
                int member_id;
                cin >> member_id;
                group_id[member_id] = i;
            }
            ptr[i] = NULL;
        }

        queue<group_que_t*> que;
        while (1) {
            string opt;
            cin >> opt;
            if (opt == "ENQUEUE") {
                int member_id;
                cin >> member_id;
                int now_group_id = group_id[member_id];
                if (ptr[now_group_id] == NULL) {
                    group_que_t *tmp = new group_que_t;
                    tmp->id = now_group_id;
                    tmp->que.push(member_id);
                    ptr[now_group_id] = tmp;
                    que.push(tmp);
                } else {
                    ptr[now_group_id]->que.push(member_id);
                }
            } else if (opt == "DEQUEUE") {
                cout << que.front()->que.front() << endl;
                que.front()->que.pop();
                if (que.front()->que.size() == 0) {
                    ptr[que.front()->id] = NULL;
                    delete que.front();
                    que.pop();
                }
            } else {
                break;
            }
        }

        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 132. 小组队列

#include <bits/stdc++.h>


using namespace std;


struct group_que_t {
    int id;
    queue<int> que;
};


int group_id[1000010];
group_que_t *ptr[2010];


int main(void) {
    int n;
    int testcase_id = 0;
    while ((cin >> n, n) != 0) {
        ++testcase_id;
        cout << "Scenario #" << testcase_id << endl;
        for (int i = 1; i <= n; ++i) {
            int m;
            cin >> m;
            for (int j = 1; j <= m; ++j) {
                int member_id;
                cin >> member_id;
                group_id[member_id] = i;
            }
            ptr[i] = NULL;
        }

        queue<group_que_t*> que;
        while (1) {
            string opt;
            cin >> opt;
            if (opt == "ENQUEUE") {
                int member_id;
                cin >> member_id;
                int now_group_id = group_id[member_id];
                if (ptr[now_group_id] == NULL) {
                    group_que_t *tmp = new group_que_t;
                    tmp->id = now_group_id;
                    tmp->que.push(member_id);
                    ptr[now_group_id] = tmp;
                    que.push(tmp);
                } else {
                    ptr[now_group_id]->que.push(member_id);
                }
            } else if (opt == "DEQUEUE") {
                cout << que.front()->que.front() << endl;
                que.front()->que.pop();
                if (que.front()->que.size() == 0) {
                    ptr[que.front()->id] = NULL;
                    delete que.front();
                    que.pop();
                }
            } else {
                break;
            }
        }

        cout << endl;
    }
    return 0;
}



单调栈算法。

#include <bits/stdc++.h>


using namespace std;


long long h[100010];


struct rect_t {
    long long height, len;
};


int main(void) {
    int n;
    while ((scanf("%d", &n), n) != 0) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &h[i]);
        }
        h[n + 1] = 0;

        stack<rect_t> rects_st;
        long long res = 0;
        for (int i = 1; i <= n + 1; ++i) {
            long long sum_len = 0;
            while (!rects_st.empty() && rects_st.top().height >= h[i]) {
                sum_len += rects_st.top().len;
                res = max(res, sum_len * rects_st.top().height);
                rects_st.pop();
            }

            rect_t tmp;
            tmp.height = h[i];
            tmp.len = sum_len + 1;
            rects_st.push(tmp);
        }

        printf("%lld\n", res);
    }
    return 0;
}



#include <bits/stdc++.h>


using namespace std;


long long h[100010];


struct rect_t {
    long long height, len;
};


int main(void) {
    int n;
    while ((scanf("%d", &n), n) != 0) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &h[i]);
        }
        h[n + 1] = 0;

        stack<rect_t> rects_st;
        long long res = 0;
        for (int i = 1; i <= n + 1; ++i) {
            long long sum_len = 0;
            while (!rects_st.empty() && rects_st.top().height >= h[i]) {
                sum_len += rects_st.top().len;
                res = max(res, sum_len * rects_st.top().height);
                rects_st.pop();
            }

            rect_t tmp;
            tmp.height = h[i];
            tmp.len = sum_len + 1;
            rects_st.push(tmp);
        }

        printf("%lld\n", res);
    }
    return 0;
}



Rt。
tmp.jpg



活动打卡代码 AcWing 129. 火车进栈

#include <bits/stdc++.h>


using namespace std;


int n;
stack<int> st;
int res[30], tot;
int num;


void dfs(int now) {
    if (tot == n) {
        for (int i = 1; i <= n; ++i) {
            printf("%d", res[i]);
        }
        putchar('\n');
        if (++num == 20) {
            exit(0);
        }
        return;
    }
    if (!st.empty()) {
        res[++tot] = st.top();
        st.pop();
        dfs(now);
        st.push(res[tot]);
        --tot;
    }
    if (now <= n) {
        st.push(now);
        dfs(now + 1);
        st.pop();
    }
}


int main(void) {
    scanf("%d", &n);
    tot = 0;
    num = 0;
    dfs(1);
    return 0;
}



RT,不是进站吗



活动打卡代码 AcWing 128. 编辑器

#include <bits/stdc++.h>


using namespace std;


int st1[1000010], st2[1000010];
int top1, top2;
int max_sum[1000010];


int main(void) {
    int n;
    scanf("%d", &n);
    top1 = top2 = 0;
    int sum = 0;
    max_sum[0] = INT_MIN;
    while (n--) {
        char opt;
        cin >> opt;
        int x;
        switch (opt) {
            case 'I': {
                cin >> x;
                ++top1;
                sum += x;
                st1[top1] = x;
                max_sum[top1] = max(max_sum[top1 - 1], sum);
                break;
            }

            case 'D': {
                if (top1 != 0) {
                    sum -= st1[top1];
                    --top1;
                }
                break;
            }

            case 'L': {
                if (top1 != 0) {
                    ++top2;
                    st2[top2] = st1[top1];
                    sum -= st1[top1];
                    --top1;
                }
                break;
            }

            case 'R': {
                if (top2 != 0) {
                    ++top1;
                    st1[top1] = st2[top2];
                    sum += st2[top2];
                    max_sum[top1] = max(max_sum[top1 - 1], sum);
                    --top2;
                }
                break;
            }

            case 'Q': {
                cin >> x;
                cout << max_sum[x] << endl;
                break;
            }
        }
    }
    return 0;
}