striving & singing

2020-09-05

ZhengruIOI 提高组十连测 Day2。

A. [2020提高组十连测day2] 小W与伙伴招募

http://www.zhengruioi.com/contest/689/problem/1539

每个月可以增加若个次购买某种钻石的机会，那么可以直接贪心，把所有方案按照单价排序，然后每次买最便宜的即可。可以直接用权值线段树维护，复杂度$O(nlogm)$。

#include<cstdio>
#include<algorithm>

const long long INF = 0x7fffffffffffffff;
int n, m, c[200100];
long long sumb[200100], ans;
struct plan {
    int a, b;
    bool operator < (const plan &b) const { return a < b.a; }
}pls[200100];
inline long long min(long long a, long long b) { return a < b ? a : b; }
struct segtreenode { int asntag; long long sum; bool inf; };
struct segtree {
    segtreenode nodes[800100];
    inline long long sum(int l, int r, int k) { return (sumb[r] - sumb[l - 1]) * k; }
    inline long long rest(int x, int l, int r, int k) { return nodes[x].inf ? INF : sum(l, r, k) - nodes[x].sum; }
    inline int lson(int x) { return x << 1; }
    inline int rson(int x) { return x << 1 | 1; }
    inline void pushup(int x) { nodes[x].sum = nodes[lson(x)].sum + nodes[rson(x)].sum; }
    inline void pushdown(int x, int l, int r) {
        if (!nodes[x].asntag) return;
        int mid = l + (r - l >> 1);
        nodes[lson(x)].sum = sum(l, mid, nodes[x].asntag); nodes[rson(x)].sum = sum(mid + 1, r, nodes[x].asntag);
        nodes[lson(x)].asntag = nodes[rson(x)].asntag = nodes[x].asntag;
        nodes[x].asntag = 0;
    }
    inline void build(int x, int l, int r) {
        if (l == r) {
            if (pls[l].b == -1) nodes[x].inf = true;
            return;
        }
        int mid = l + (r - l >> 1);
        build(lson(x), l, mid);
        build(rson(x), mid + 1, r);
        nodes[x].inf = nodes[lson(x)].inf || nodes[rson(x)].inf;
    }
    void add(int x, int l, int r, const int v, const int k) {
        if (v <= 0) return;
        if (v >= rest(x, l, r, k)) {
            nodes[x].asntag = k;
            nodes[x].sum = sum(l, r, k);
            return;
        }
        if (l == r) {
            nodes[x].sum += v;
            return;
        }
        pushdown(x, l, r);
        int mid = l + (r - l >> 1); long long lv = min(v, rest(lson(x), l, mid, k));
        add(lson(x), l, mid, lv, k);
        add(rson(x), mid + 1, r, v - lv, k);
        pushup(x);
    }
    long long calc(int x, int l, int r) {
        if (l == r) return nodes[x].sum * pls[l].a;
        pushdown(x, l, r);
        int mid = l + (r - l >> 1);
        return calc(lson(x), l, mid) + calc(rson(x), mid + 1, r);
    }
}segtree;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i <= m; i++) scanf("%d%d", &pls[i].a, &pls[i].b);
    std::sort(pls + 1, pls + m + 1);
    for (int i = 1; i <= m; i++) sumb[i] = sumb[i - 1] + (pls[i].b == -1 ? 0 : pls[i].b);
    segtree.build(1, 1, m);
    for (int i = 1; i <= n; i++) segtree.add(1, 1, m, c[i], i);
    ans = segtree.calc(1, 1, m);
    printf("%lld\n", ans);
    return 0;
}

B. [2020提高组十连测day2] 小W与制胡串谜题

http://www.zhengruioi.com/contest/689/problem/1540

显然可以直接排序。

#include<cstdio>
#include<algorithm>

const long long INF = 0x7fffffffffffffff;
int n, m, c[200100];
long long sumb[200100], ans;
struct plan {
    int a, b;
    bool operator < (const plan &b) const { return a < b.a; }
}pls[200100];
inline long long min(long long a, long long b) { return a < b ? a : b; }
struct segtreenode { int asntag; long long sum; bool inf; };
struct segtree {
    segtreenode nodes[800100];
    inline long long sum(int l, int r, int k) { return (sumb[r] - sumb[l - 1]) * k; }
    inline long long rest(int x, int l, int r, int k) { return nodes[x].inf ? INF : sum(l, r, k) - nodes[x].sum; }
    inline int lson(int x) { return x << 1; }
    inline int rson(int x) { return x << 1 | 1; }
    inline void pushup(int x) { nodes[x].sum = nodes[lson(x)].sum + nodes[rson(x)].sum; }
    inline void pushdown(int x, int l, int r) {
        if (!nodes[x].asntag) return;
        int mid = l + (r - l >> 1);
        nodes[lson(x)].sum = sum(l, mid, nodes[x].asntag); nodes[rson(x)].sum = sum(mid + 1, r, nodes[x].asntag);
        nodes[lson(x)].asntag = nodes[rson(x)].asntag = nodes[x].asntag;
        nodes[x].asntag = 0;
    }
    inline void build(int x, int l, int r) {
        if (l == r) {
            if (pls[l].b == -1) nodes[x].inf = true;
            return;
        }
        int mid = l + (r - l >> 1);
        build(lson(x), l, mid);
        build(rson(x), mid + 1, r);
        nodes[x].inf = nodes[lson(x)].inf || nodes[rson(x)].inf;
    }
    void add(int x, int l, int r, const int v, const int k) {
        if (v <= 0) return;
        if (v >= rest(x, l, r, k)) {
            nodes[x].asntag = k;
            nodes[x].sum = sum(l, r, k);
            return;
        }
        if (l == r) {
            nodes[x].sum += v;
            return;
        }
        pushdown(x, l, r);
        int mid = l + (r - l >> 1); long long lv = min(v, rest(lson(x), l, mid, k));
        add(lson(x), l, mid, lv, k);
        add(rson(x), mid + 1, r, v - lv, k);
        pushup(x);
    }
    long long calc(int x, int l, int r) {
        if (l == r) return nodes[x].sum * pls[l].a;
        pushdown(x, l, r);
        int mid = l + (r - l >> 1);
        return calc(lson(x), l, mid) + calc(rson(x), mid + 1, r);
    }
}segtree;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i <= m; i++) scanf("%d%d", &pls[i].a, &pls[i].b);
    std::sort(pls + 1, pls + m + 1);
    for (int i = 1; i <= m; i++) sumb[i] = sumb[i - 1] + (pls[i].b == -1 ? 0 : pls[i].b);
    segtree.build(1, 1, m);
    for (int i = 1; i <= n; i++) segtree.add(1, 1, m, c[i], i);
    ans = segtree.calc(1, 1, m);
    printf("%lld\n", ans);
    return 0;
}

C. [2020提高组十连测day2] 小W与屠龙游戏

http://www.zhengruioi.com/contest/689/problem/1541

到现在还没读懂题，以后再补。

2020-09-06

ZhengruIOI 普转提七连测 Day1。

A. [2020普转提七连测day1] 机器人指令

http://www.zhengruioi.com/contest/690/problem/1535

可以直接$O(n)$模拟这个命令序列，得到这个序列对应的位移向量，然后再做$t$次向量加法即可，复杂度$O(n+t)$。

上面是我的思路，题解的思路是因为$4a\bmod 4=0,a\in N$所以每执行$4$次命令序列后会回到原来的方向，然后模拟$4$次命令序列，再对$t\bmod 4$的零散部分模拟即可。

下面是我的思路的代码。

#include<cstdio>

const int vct[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
const int vct2[4][2] = { {1, 1}, {1, -1}, {-1, -1}, {-1, 1} };
int n, t, dir;
long long x, y;

inline long long abs(long long x) { return x > 0 ? x : -x; }

int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i++) {
        int a; scanf("%d", &a);
        x += a * vct[dir][0], y += a * vct[dir][1];
        dir = (dir + a) % 4;
    }
    long long x1 = x, y1 = y; int dir1 = dir;
    x = 0, y = 0, dir = 0;
    for (int i = 1; i <= t; i++) x += x1 * vct2[dir][0], y += y1 * vct2[dir][1], dir = (dir + dir1) % 4;
    printf("%lld\n", abs(x) + abs(y));
    return 0;
}

B. [2020普转提七连测day1] 逛餐馆

http://www.zhengruioi.com/contest/690/problem/1536

可以枚举最后走到了哪个餐馆，设最后走到了第$i$个餐馆，那么现在要找到一个元素个数最大的集合${k\in N|k\in [1,i]}$使得元素的$t_k$之和小于等于$m-x_i$。显然直接贪心找$t_k$最小的那些位置是最优的，可以用一个大根堆维护，每枚举一个位置$i$就把这个位置$i$加入到堆中，然后一直 pop 直到堆中位置的$t_k$之和小于等于$m-x_i$。

#include<cstdio>
#include<queue>
#include<algorithm>

int n, ans, cnt;
long long m, sum;
struct res {
    long long x; int t;
    bool operator < (const res &b) const { return x < b.x; }
}rs[100100];
std::priority_queue<int> q;

inline int max(int a, int b) { return a > b ? a : b; }

int main() {
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld%d", &rs[i].x, &rs[i].t);
    std::sort(rs + 1, rs + n + 1);
    for (int i = 1; i <= n; i++) {
        if (rs[i].x > m) break;
        long long x = rs[i].x;
        q.push(rs[i].t); sum += rs[i].t; cnt++;
        while (sum > m - x) {
            sum -= q.top(); cnt--;
            q.pop();
        }
        ans = max(ans, cnt);
    }
    printf("%d\n", ans);
    return 0;
}

C. [2020普转提七连测day1] 符文师

http://www.zhengruioi.com/contest/690/problem/1537

因为有第一种操作所以可以把问题看作环上的问题，然后就不用管第一种操作了。接下来有个结论，一个符卡集合能够全部使用的充要条件是这个集合的$l_i$之和小于等于$n$。必要性在于如果$\sum l_i> n$那么显然没法全部使用。充分性的证明可以用归纳法，设一个符卡到下一个符卡的距离为$d_i$，那么因为$\sum d_i=n,\sum l_i\le n$所以由抽屉原理总存在一个$i$使得$l_i\le s_i$，那么这张符卡就可以使用。

然后问题就转化为了 01 背包问题，背包大小为$n$。

#include<cstdio>

int n, l[1010], d[1010], dp[1010], ans;

inline int max(int a, int b) { return a > b ? a : b; }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &l[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
    for (int i = 1; i <= n; i++)
        for (int j = n; j >= 0; j--)
            if (j >= l[i]) dp[j] = max(dp[j], dp[j - l[i]] + d[i]);
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}

D. [2020普转提七连测day1] 魔法师

http://www.zhengruioi.com/contest/690/problem/1538

可以维护所有不同种类的集合，以及一个集合$S$蕴含所有不同种类的集合中前$t$大的数，然后每次输出$S$中前$n$大的数即可。可以用动态开点权值线段树维护集合。

#include<cstdio>
#include<algorithm>

int n, m, pv[300100], cnt;
struct operation {
    char opt; int t, p;
}opts[300100];
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
struct segtreenode { int lson, rson, cnt; long long sum; }nodes[6000100];
struct segtree {
    int root;
    inline void pushup(int x) {
        nodes[x].cnt = nodes[nodes[x].lson].cnt + nodes[nodes[x].rson].cnt;
        nodes[x].sum = nodes[nodes[x].lson].sum + nodes[nodes[x].rson].sum;
    }
    int insert(int x, int l, int r, int v) {
        if (v == -1) return x;
        if (!x) x = ++cnt;
        if (l == r) {
            nodes[x].cnt++; nodes[x].sum += pv[v];
            return x;
        }
        int mid = l + (r - l >> 1);
        if (v <= mid) nodes[x].lson = insert(nodes[x].lson, l, mid, v);
        else if (mid + 1 <= v) nodes[x].rson = insert(nodes[x].rson, mid + 1, r, v);
        pushup(x);
        return x;
    }
    void remove(int x, int l, int r, int v) {
        if (!x || v == -1) return;
        if (l == r) {
            nodes[x].cnt--; nodes[x].sum -= pv[v];
            return;
        }
        int mid = l + (r - l >> 1);
        if (v <= mid) remove(nodes[x].lson, l, mid, v);
        else if (mid + 1 <= v) remove(nodes[x].rson, mid + 1, r, v);
        pushup(x);
    }
    int rnk(int x, int l, int r, int v) {
        if (l == r) return 1;
        int mid = l + (r - l >> 1);
        if (v <= mid) return rnk(nodes[x].lson, l, mid, v);
        else if (mid + 1 <= v) return nodes[nodes[x].lson].cnt + rnk(nodes[x].rson, mid + 1, r, v);
    }
    int kth(int x, int l, int r, int k) {
        if (l == r) return l;
        int mid = l + (r - l >> 1);
        if (k <= nodes[nodes[x].lson].cnt) return kth(nodes[x].lson, l, mid, k);
        else if (k <= nodes[x].cnt) return kth(nodes[x].rson, mid + 1, r, k - nodes[nodes[x].lson].cnt);
        else return -1;
    }
    long long ksum(int x, int l, int r, int k) {
        k = min(k, nodes[x].cnt);
        if (l == r) return pv[l] * k;
        int mid = l + (r - l >> 1);
        if (k <= nodes[nodes[x].lson].cnt) return ksum(nodes[x].lson, l, mid, k);
        else return nodes[nodes[x].lson].sum + ksum(nodes[x].rson, mid + 1, r, k - nodes[nodes[x].lson].cnt);
    }
}tr[300100], s;

inline bool cmp(int a, int b) { return a > b; }

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        char opt = getchar(), c;
        while (!('A' <= opt && opt <= 'Z')) opt = getchar();
        c = getchar();
        while ('A' <= c && c <= 'Z') c = getchar();
        int t, p; scanf("%d%d", &t, &p);
        opts[i].opt = opt; opts[i].t = t; opts[i].p = p;
        pv[i] = p;
    }
    std::sort(pv + 1, pv + m + 1, cmp);
    int pn = std::unique(pv + 1, pv + m + 1) - 1 - pv;
    for (int i = 1; i <= m; i++) opts[i].p = std::lower_bound(pv + 1, pv + pn + 1, opts[i].p, cmp) - pv;
    for (int i = 1; i <= m; i++) {
        char &opt = opts[i].opt; int &t = opts[i].t, &p = opts[i].p;
        if (opt == 'B') {
            tr[t].root = tr[t].insert(tr[t].root, 1, pn, p);
            int k = tr[t].rnk(tr[t].root, 1, pn, p);
            if (k <= t) {
                s.root = s.insert(s.root, 1, pn, p);
                if (k == t) s.remove(s.root, 1, pn, tr[t].kth(tr[t].root, 1, pn, t + 1));
            }
        }
        else if (opt == 'R') {
            int k = tr[t].rnk(tr[t].root, 1, pn, p);
            if (k <= t) {
                s.remove(s.root, 1, pn, p);
                if (k == t) s.root = s.insert(s.root, 1, pn, tr[t].kth(tr[t].root, 1, pn, t + 1));
            }
            tr[t].remove(tr[t].root, 1, pn, p);
        }
        printf("%lld\n", s.ksum(s.root, 1, pn, n));
    }
    return 0;
}

return