NOI2017 题目分析

NOI2017 D1T1 整数

大体上来看是一道 NOIP 难度的题目,很容易发现题目要求快速维护高精度二进制加减。而我们每次加入或者删去一个数最多只会带来一次高精度的进位或者退位,而一次进退位就是区间赋值为 $0/1$,所以我们拿线段树维护即可。

同时考虑到数据范围很大,而且我们线段树维护的只有 $0/1$,可以一次性压到一个 unsigned int 里来维护,判断同时维护一个区间 or 和区间 and,结合这两个的值即可判定一段内是否全为$0/1$。去年码力实在是不太行,这样一个签到题愣是写了三个多小时,导致后两题,尤其是第二题没有拿到一点分。

时间复杂度 $O(n \log n)$。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define uint         unsigned int
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        ((uint)1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 2e6 + 5;
const int L = 30;
uint all = bin(30) - 1;
const int oo = 0x3f3f3f3f;

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
} 

struct tree {
    uint sor, sand;
    int cov;
}t[MAXN << 2];

inline bool isall1(int k) { return t[k].sor == t[k].sand && t[k].sor == all; }
inline bool isall0(int k) { return t[k].sor == t[k].sand && t[k].sor == 0; }

inline void rel(int k){
    t[k].sor = t[k << 1].sor | t[k << 1 | 1].sor;
    t[k].sand = t[k << 1].sand & t[k << 1 | 1].sand;
}

inline void cg(int k, uint v){
    t[k].cov = v == 0 ? -1 : 1;
    t[k].sor = t[k].sand = v;
}

inline void Pushdown(int k){
    if (t[k].cov == 0) return;
    uint x = t[k].cov == -1 ? 0 : all;
    cg(k << 1, x); cg(k << 1 | 1, x);
    t[k].cov = 0;
}

uint get(int le, int ri, int k, int o){
    if (le != ri) Pushdown(k);
    if (le == ri) return t[k].sor;
    int mi = (le + ri) >> 1;
    o <= mi ? get(le, mi, k << 1, o) : get(mi + 1, ri, k << 1 | 1, o);
}

void cg(int le, int ri, int k, int o, uint v){
    if (le != ri) Pushdown(k);
    if (le == ri) return (void)(t[k].sor = t[k].sand = v);
    int mi = (le + ri) >> 1;
    o <= mi ? cg(le, mi, k << 1, o, v) : cg(mi + 1, ri, k << 1 | 1, o, v);
    rel(k);
}

struct ROOT {
    int le, ri, k;
    inline ROOT (int le = 0, int ri = 0, int k = 0) : le(le), ri(ri), k(k) {}
}rts[MAXN];

int siz;

void get(int le, int ri, int k, int L, int R){
    if (le != ri)        Pushdown(k);
    if (L <= le && ri <= R)    return (void)(rts[++siz] = ROOT(le, ri, k));
    int mi = (le + ri) >> 1;
    if (L <= mi)    get(le, mi, k << 1, L, R);
    if (mi + 1 <= R)    get(mi + 1, ri, k << 1 | 1, L, R);
}

int get0(int le, int ri, int k){
    if (le != ri) Pushdown(k);
    if (le == ri) return le;
    int mi = (le + ri) >> 1, x;
    if (isall1(k << 1)) {
        cg(k << 1, 0);
        x = get0(mi + 1, ri, k << 1 | 1);
    }else x = get0(le, mi, k << 1);
    rel(k);
    return x;
}

int get1(int le, int ri, int k){
    if (le != ri) Pushdown(k);
    if (le == ri) return le;
    int mi = (le + ri) >> 1, x;
    if (isall0(k << 1)) {
        cg(k << 1, all);
        x = get1(mi + 1, ri, k << 1 | 1);
    }else x = get1(le, mi, k << 1);
    rel(k);
    return x;
}

void Rel(int k){ while (k >>= 1) rel(k); }

int Q, n;

void add(int o, uint v){
    uint x = get(0, n, 1, o);
    cg(0, n, 1, o, (x += v) & all);
    if (x != (x & all)) {
        get(siz = 0, n, 1, o + 1, n);
        up (i, 1, siz) {
            int le = rts[i].le, ri = rts[i].ri, k = rts[i].k;
            if (isall1(k)) {
                cg(k, 0);
                Rel(k);
            }else {
                int w = get0(le, ri, k);
                uint x = get(0, n, 1, w);
                Rel(k);
                cg(0, n, 1, w, ++x);
                break;
            }
        }
    }
}

void pop(int o, uint v){
    uint x = get(0, n, 1, o);
    cg(0, n, 1, o, (x -= v) & all);
    if (x != (x & all)) {
        get(siz = 0, n, 1, o + 1, n);
        up (i, 1, siz) {
            int le = rts[i].le, ri = rts[i].ri, k = rts[i].k;
            if (isall0(k)) {
                cg(k, all);
                Rel(k);
            }else {
                int w = get1(le, ri, k); 
                uint x = get(0, n, 1, w);
                Rel(k);
                cg(0, n, 1, w, --x);
                break;
            }
        }
    }
}

int main(){
    Q = read(); n = Q + 15;
    int t1 = read(), t2 = read(), t3 = read();
    while (Q--) {
        int o = read(), x, v;
        if (o == 1) {
            v = read(); x = read();
            int vv = abs(v), w = x - x / L * L;
            v > 0 ? add(x / L, (vv << w) & all) : pop(x / L, (vv << w) & all);
            w = L - w;
            v > 0 ? add(x / L + 1, vv >> w) : pop(x / L + 1, vv >> w);
        }else {
            x = read();
            uint w = get(0, n, 1, x / L);
            puts(((w >> (x - (x / L * L))) & 1) ? "1" : "0");
        }
    }
    return 0;
}

NOI2017 D1T2 蚯蚓排队

主要考察选手的心态以及读题能力,看懂题后我们拿链表维护一下 Link Cut,每次操作暴力维护 hash 值即可。

时间复杂度 $O((n + m)k)$。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define ull            unsigned long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int mod = 998244353;
const int MOD = 10002333;

const ull step = 17171717;

const int MAXN = 2e5 + 5;
const int MAXM = 1e7 + 5;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

struct H {
    struct edge {
        int next, v;
        ull q;
    }e[MOD + MOD];
    int LINK[MOD], len;
    inline void ins(int p, ull q, int v){
        e[++len].next = LINK[p]; LINK[p] = len;
        e[len].q = q; e[len].v = v;
    }
    int get(ull x){
        int p = x % MOD;
        Auto (i, p) if (e[i].q == x) return e[i].v;
        return 0;
    }
    void cg(ull x, int v){
        int p = x % MOD;
        Auto (i, p) if (e[i].q == x) return (void) (e[i].v += v);
        ins(p, x, v);
    }
}S;

ull bin[MAXN];

int N, Q;

struct LK {
    int pre, nxt, v;
}a[MAXN];

int pre[MAXN], suf[MAXN];

char s[MAXM];

int main(){
    scanf("%d%d", &N, &Q);
    up (i, 1, N) {
        scanf("%d", &a[i].v);
        S.cg(a[i].v, 1);
    }
    bin[0] = 1;
    up (i, 1, N) bin[i] = bin[i - 1] * step;
    while (Q--) {
        int o, x, y;
        scanf("%d", &o);
        if (o == 1) {
            scanf("%d%d", &x, &y);
            int p = 0, q = 0;
            a[x].nxt = y; a[y].pre = x;
            for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
            for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
            up (i, 1, p) {
                int n = min(q, 50 - i);
                ull cur = 0;
                down (j, i, 1) cur = cur * step + pre[j];
                up (j, 1, n) {
                    cur = cur * step + suf[j];
                    S.cg(cur, 1);
                }
            }
        } 
        if (o == 2) {
            scanf("%d", &x); y = a[x].nxt;
            int p = 0, q = 0;
            for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
            for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
            up (i, 1, p) {
                int n = min(q, 50 - i);
                ull cur = 0;
                down (j, i, 1) cur = cur * step + pre[j];
                up (j, 1, n) {
                    cur = cur * step + suf[j];
                    S.cg(cur, -1);
                }
            }
            a[x].nxt = 0; a[y].pre = 0;
        }
        if (o == 3) {
            scanf("%s%d", s + 1, &x); int len = strlen(s + 1);
            ull cur = 0;
            up (i, 1, x - 1) cur = cur * step + (s[i] - '0');
            int ans = 1;
            up (i, x, len) {
                cur = cur * step + (s[i] - '0');
                if (i > x) cur -= bin[x] * (s[i - x] - '0');
                cmul(ans, S.get(cur));
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

NOI2017 D1T3 泳池

首先这题是有一定思维难度的,我在没看题解的前提下大概想了有一个多小时才想到裸的 DP 怎么做。

首先做一点小转化,因为求的是恰好 $K$,我们改为求小于等于 $K$ 的,这样我们求出 $K$ 的答案和 $K - 1$ 时候的答案,相减一下就是答案了。

接着我们容易发现,对于最底下一行来说,任意连续长度为 $K + 1$ 的格子中,至少要有一个格子是危险的。同时对于任意一个危险的格子来说,其左右的计算互相独立,可以用乘法原理直接计算。那么只要我计算出对于长度为 $0..K$ 之内的答案,作为系数来 DP 即可,本质上是一个其次常系数线性递推,最优可以做到 $k \log k$,这道题里我们只用特征多项式做到$k^2 \log k$即可。

然后考虑怎么计算长度在$0..K$之间的答案,沿用我们第一次的思路,对于每一行来说,任意一个黑格子都把左右分为独立的两部分,所以我们设定状态 $f(n,m)$表示长度为$n$,下方$m$行全为不危险格子的同时,满足要求的概率。然后我们直接 DP 即可,这一部分看起来是 $k^3$的,实际上分析一下可以发现是$k^2$的复杂度。

这样我们就算出了系数,结合特征多项式优化矩乘那一套理论直接做即可。

时间复杂度 $O(k^2\log n)$。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int mod = 998244353;
const int MAXN = 2005;
const int oo = 0x3f3f3f3f;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

struct poly {
    int m[MAXN], n;
    inline poly () {}
    inline poly (int n) : n (n) { memset(m, 0, sizeof(m)); }
};

int X[MAXN];

inline poly operator * (const poly & a, const poly & b) {
    poly c = poly(a.n);
    up (i, 0, c.n - 1) up (j, 0, c.n - 1) cadd(c.m[i + j], mul(a.m[i], b.m[j]));
    down (i, c.n + c.n - 2, c.n) {
        up (j, 1, c.n) cadd(c.m[i - j], mul(X[j], c.m[i]));
        c.m[i] = 0;
    }
    return c;
}

int N, M, P, f[MAXN][MAXN], pw[MAXN];

int DP(int n, int m) {
    if (f[n][m] != -1) return f[n][m];
    if (n == 0) return f[n][m] = 1;
    f[n][m] = 0;
    down (i, n, 1) {
        int len = n - i;
        if (len * (m + 1) > M) break;
        cadd(f[n][m], mul(DP(i - 1, m), mul(DP(len, m + 1), mul(pw[len], pop(1, P)))));
    }
    if (n * (m + 1) <= M) cadd(f[n][m], mul(pw[n], DP(n, m + 1)));
    return f[n][m];
}

int g[MAXN];

int calc(int m){
    M = m; 
    memset(f, -1, sizeof(f));
    poly A = poly(M + 1), B = poly(M + 1);
    up (i, 0, M) {
        g[i] = DP(i, 0);
        X[i + 1] = mul(mul(DP(i, 1), pw[i]), pop(1, P));
    }
    up (i, M + 1, M + M) {
        g[i] = 0;
        down (j, i, i - M) {
            int len = i - j, x = mul(pw[len], pop(1, P));
            cmul(x, f[len][1]);
            cadd(g[i], mul(g[j - 1], x));
        }
    }
    if (N <= M + M) return g[N];
    A.m[0] = 1; B.m[1] = 1; 
    int n = N - M, sum = 0;
    while (n) {
        if (n & 1) A = A * B;
        B = B * B; n >>= 1;
    }
    up (i, M, M + M) cadd(sum, mul(A.m[i - M], g[i])); 
    return sum;
}

int main(){
    int p, q, m; scanf("%d%d%d%d", &N, &m, &p, &q);
    P = mul(p, qpow(q, mod - 2));
    pw[0] = 1;
    up (i, 1, m) pw[i] = mul(pw[i - 1], P);
    printf("%d\n", pop(calc(m), calc(m - 1)));
    return 0;
}

D1 小结

总体上来看这场 NOI 是正常的风格,T1T2 基本就可以做到 Cu - Au 的区分了,T3 主要是在 50 人里作出区分。如果想要进队的话,很重要的点就是 T1 T2 不能爆,T1 作为 NOI 赛场上看到的第一道题目,其实还算正常,差不多一眼就能看出来怎么做,但是实现可能相对来说比较困难,T2 是一道实现起来非常简单的题目,但是要求你能耐心读完题目以及那个有点恶心的部分分表格。所以可以是你心态比较好,能在考场上耐心把题读完,或者码力比较棒能快速的实现 t1,然后把 t2 给写掉。

至于 t3,我感觉如果不是在 t1t2 都稳了的情况下,很难静下心来认真思考,去年我在考场上甚至没想到把恰好转化为容斥再进行思考。但是一旦冷静下来撕烤的话,应该还是能拿到不错的分数的。

对考场策略的提示,稳定的心态最重要,对于每道题目都要分配合理的思考时间,不要被一眼看到高分做法的题冲昏头脑。

NOI2017 D2T1 游戏

同样是一道 NOIP 向的题目,知道基本的 2-SAT 相关知识即可。这道题当时考场是因为对 2-SAT 理解并不充分,导致建图有所疏漏,只拿到了 45 分。

时间复杂度 $O(2^d (n + m))$

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 2e5 + 5;
const int oo = 0x3f3f3f3f;

int N, D, M;
char s[MAXN], bu[MAXN];

struct ban {
    int x, vx, y, vy;
    inline ban (int x = 0, int vx = 0, int y = 0, int vy = 0) : x(x), vx(vx), y(y), vy(vy) {}
}w[MAXN];

int pos[MAXN], n = 0;

inline int opp(int x) { return ((x - 1) ^ 1) + 1; }

struct edge {
    int x, y, next;
}e[MAXN << 3];

int LINK[MAXN], len = 0, ID[MAXN][3], cnt, dfn[MAXN], low[MAXN];
int bt[MAXN], ord, sta[MAXN], top, scc;
bool vis[MAXN];

inline void ins(int x, int y){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y; e[len].x = x;
}

void DFS(int node){
    dfn[node] = low[node] = ++ord; 
    sta[++top] = node; vis[node] = 1;
    Auto (i, node) if (!dfn[e[i].y]) {
        DFS(e[i].y);
        cmin(low[node], low[e[i].y]);
    }else if (vis[e[i].y]) cmin(low[node], dfn[e[i].y]);
    if (dfn[node] == low[node]) {
        int tmp; scc++;
        do {
            tmp = sta[top--];
            vis[tmp] = 0;
            bt[tmp] = scc;
        }while (tmp != node);
    }
}

void ers(){
    up (i, 1, cnt) LINK[i] = low[i] = dfn[i] = vis[i] = 0;
    up (i, 1, N) up (j, 0, 2) ID[i][j] = 0;
    ord = len = cnt = top = scc = 0;
}

bool vaild(){
    up (i, 1, N) up (j, 0, 2) if (s[i] != ('a' + j)) ID[i][j] = ++cnt;
    up (i, 1, M) {
        int x = w[i].x, vx = w[i].vx, y = w[i].y, vy = w[i].vy;
        if (ID[x][vx] == 0 && ID[y][vy] == 0) continue;
        if (ID[x][vx] == 0) continue;
        if (ID[y][vy] == 0) {
            ins(ID[x][vx], opp(ID[x][vx]));
            continue;
        } 
        ins(ID[x][vx], ID[y][vy]);
        ins(opp(ID[y][vy]), opp(ID[x][vx]));
    }
    up (i, 1, cnt) if (!dfn[i]) DFS(i); 
    up (i, 1, cnt) if (bt[i] == bt[opp(i)]) {
        ers();
        return 0;
    }
    return 1;
}    

char A[5], B[5];

vector<int> G[MAXN];
int deg[MAXN];

deque<int> q;

int oth[MAXN], col[MAXN];

int main(){
    scanf("%d%d", &N, &D);
    scanf("%s", s + 1);
    up (i, 1, N) if (s[i] == 'x') pos[n++] = i;
    memcpy(bu + 1, s + 1, sizeof(s[0]) * N);
    scanf("%d", &M);
    up (i, 1, M) {
        int x, vx, y, vy; scanf("%d%s%d%s", &x, A, &y, B);
        vx = A[0] - 'A'; vy = B[0] - 'A';
        w[i] = ban(x, vx, y, vy);
    }
    up (ss, 0, bin(n) - 1) {
        memcpy(s + 1, bu + 1, sizeof(s[0]) * N);
        up (i, 0, n - 1) s[pos[i]] = (ss & bin(i)) == 0 ? 'a' : 'b';
        if (vaild()) {
            up (i, 1, len) {
                int x = e[i].x, y = e[i].y;
                if (bt[x] != bt[y]) {
                    G[bt[y]].push_back(bt[x]);
                    deg[bt[x]]++;
                }
            }
            up (i, 1, cnt) oth[bt[i]] = bt[opp(i)];
            up (i, 1, scc) if (!deg[i]) q.push_back(i);
            while (!q.empty()) {
                int node = q.front(); q.pop_front();
                if (col[node]) continue;
                col[node] = 1; col[oth[node]] = -1;
                up (i, 0, SZ(G[node]) - 1) if (!--deg[G[node][i]]) 
                    q.push_back(G[node][i]);
            }
            up (i, 1, N) up (j, 0, 2) if (ID[i][j] && col[bt[ID[i][j]]] == 1) { 
                putchar('A' + j);
            }
            puts("");
            return 0;    
        }
    }    
    puts("-1");
    return 0;
}

NOI2017 D2T2 蔬菜

本题同样考察读题,大概就是我们把题读懂后就可以得到一个裸的费用流做法。然后我们考察费用流的本质,发现每次寻找增光路的过程可以用贪心来替代,然后就做完啦。

维护的时候可能需要一些并查集什么的,复杂度算不太清,反正肯定是能过的。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 4e5 + 5;
const int oo = 0x3f3f3f3f;

int N, M, Q, f[MAXN], c[MAXN], qry[MAXN], n, ord[MAXN];

ll ans[MAXN];

struct W {
    int w, st, n, c;
    inline W (int w = 0, int st = 0, int n = 0, int c = 0) : w(w), st(st), n(n), c(c) {}
    inline bool operator < (const W & v) const { return w == v.w ? st < v.st : w < v.w; }
};

int siz;
pr s[MAXN];

priority_queue<W> pq;

inline bool cmp(int x, int y) { return qry[x] < qry[y]; }

inline int getf(int k) { return k == f[k] ? k : f[k] = getf(f[k]); }

int main(){
    scanf("%d%d%d", &N, &M, &Q);
    up (i, 1, N) {
        int aa, ss, cc, xx; 
        scanf("%d%d%d%d", &aa, &ss, &cc, &xx);
        int ed = xx == 0 ? oo : ((cc + xx - 1) / xx);
        pq.push(W(aa + ss, ed, 1, xx));
        cc--;
        pq.push(W(aa, 1, cc, xx));
    }
    up (i, 1, Q) scanf("%d", &qry[i]);
    up (i, 1, Q) ord[i] = i;
    sort(ord + 1, ord + Q + 1, cmp);
    n = qry[ord[Q]];
    up (i, 1, n) f[i] = i, c[i] = M;
    ll cur = 0, cnt = 0;
    while (!pq.empty()) {
        W w = pq.top(); pq.pop();
        int ed = w.c == 0 ? n : min((w.n + w.c - 1) / w.c + w.st - 1, n), ee = ed;
        ed = getf(ed);
        int x = min(c[ed], w.n - (max(ed - w.st, 0)) * w.c);
        c[ed] -= x; w.n -= x;
        cur += (ll)x * w.w;
        cnt += x;
        if (c[ed] == 0) f[ed] = getf(ed - 1);
        if (x != 0 && w.n != 0) pq.push(w);
        if (x) s[++siz] = make_pair(w.w, x);
    }
    sort(s + 1, s + siz + 1);
    int cr = qry[ord[Q]], cl = 1;
    down (i, Q, 1) {
        while (cr > qry[ord[i]]) {
            cr--;
            if ((ll)cnt > (ll)cr * M) {
                int pop = cnt - cr * M;
                while (pop) {
                    int x = min(pop, s[cl].se);
                    pop -= x;
                    s[cl].se -= x;
                    cur -= (ll)x * s[cl].fi;
                    cnt -= x;
                    if (s[cl].se == 0) cl++;
                }
            }
        }
        ans[ord[i]] = cur;
    }
    up (i, 1, Q) printf("%lld\n", ans[i]);
    return 0;
}

NOI2017 D2T3

强制在线的动态凸包裸题,不太会,弃疗,感觉大家都是 20 分暴力的样子,当这题不存在好了。

D2 小结

和 D1 一样,做好前两题就能进队,只做一个题就是 Ag。t1 可能卡了部分选手的知识点,对 2-SAT 不够了解的话就很难拿到比较高的分数。做 t2 的前提还是 t1 要拿到一个稳定的分数的前提,只要冷静下来好好读题,t2 也可以拿到非常不错的分数。

总结

这次题目其实是比较正常的,题目上如果要进队,并不需要太过生疏的知识点,这场来看你会线段树 hash 2-SAT 其实差不多就可以进队了,但是集训队内比较靠前的名额就需要不少的努力了。

心态还是最重要的,认真做好每一题,确保写的分都能拿到。

只要做好这些,就没有其他需要担心的了。