NOIP2022 题解

Un1quAIoid · 2022-11-29 10:18:45 · 个人记录

T2 数组开小+多测没清干净，估计会挂得比较惨（不过在洛谷上居然有75pts），没什么心情，题解随便写写吧。

2022/12/6 upd：昨天出成绩了，T2 好歹有35pts，不过听说 O(nm) 能过TAT。。。

T1.plant

记 A_{i,j} 表示从点 (i,j) 最多能向右延伸多少格，那么以 (x1,y1),(x2,y1) 为拐点的 C 的个数就是 A_{x1,y1} \cdot A_{x2,y1}，F 的个数还要再乘上点 (x2,y1) 最多向下延伸的格数，这个东西用前缀和维护一下就能做到 O(nm)。

考场代码：

//-O2 -std=c++14 -Wl,-stack=134217728 -Wall -Wextra -Wshadow
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define lowbit(x) (x & -x)
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 1005;
const int Mod = 998244353;

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

int n, m, c, f, ansc, ansf;
int dc[MAXN], rc[MAXN][MAXN], sumc[MAXN][MAXN], sumf[MAXN][MAXN];
char a[MAXN][MAXN];

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

void solve() {
    n = read(), m = read(), c = read(), f = read();
    for (int i = 1; i <= n; i++) {
        scanf(" %s", a[i] + 1);
        rc[i][m + 1] = 0;
        for (int j = m; j; j--) {
            sumc[i][j] = sumf[i][j] = 0;
            if (a[i][j] == '1') rc[i][j] = 0;
            else rc[i][j] = rc[i][j + 1] + 1;
        }
    }

    ansc = ansf = 0;

    for (int i = 1; i <= m; i++) dc[i] = n + 1, sumc[n + 1][i] = sumf[n + 1][i] = 0;
    for (int i = n; i; i--) {
        for (int j = 1; j <= m; j++) {
            sumc[i][j] = sumc[i + 1][j];
            sumf[i][j] = sumf[i + 1][j];
            if (rc[i][j]) {
                if (i < n && a[i + 1][j] != '1') {
                    Add(ansc, (ll) (rc[i][j] - 1) * (sumc[i + 2][j] - sumc[dc[j]][j] + Mod) % Mod);
                    Add(ansf, (ll) (rc[i][j] - 1) * (sumf[i + 2][j] - sumf[dc[j]][j] + Mod) % Mod);
                }
                Add(sumc[i][j], rc[i][j] - 1);
                Add(sumf[i][j], (ll) (rc[i][j] - 1) * (dc[j] - i - 1) % Mod);
            } else {
                dc[j] = i;
            }
        }
    }

//  for (int i = 1; i <= n; i++, puts(""))
//      for (int j = 1; j <= m; j++) printf("%d ", sumf[i][j]);
    printf("%d %d\n", c * ansc, f * ansf);
}

int main() {
    freopen("plant.in", "r", stdin);
    freopen("plant.out", "w", stdout);

    int T = read(), id = read();
    while (T--) {
        solve();
    }
    return 0;
}

T2.meow

为什么不把这题放T4 /fn/fn/fn

考场看到这个构造都懵了，虽然看了眼T3发现很简单，但心态还是快崩了，一直在想我不会连NOIP T2都做不出来吧，好在吃了块巧克力冷静了下来，连想带码一共花了两个半小时总算写出来了，虽然最后还是因为数组开小+多测没清空挂飞了，点这看公开处刑。

首先 k=2n-2 时非常容易构造，我们可以保持一个栈时刻为空，另外 n-1 个栈各最多有 2 个元素，这样 2n-2 个元素恰好可以放进这 n-1 个栈中且要么是栈顶，要么是栈底，这样下一个元素如果在栈顶，那就直接消去，如果在栈底，则刚好可以利用空栈消去。

接下来考虑 k=2n-1 时的情况，依然可以延续 k=2n-2 时的想法，时刻保证一个栈为空，另外 n-1 个栈保持上限 2 个元素，此时我们就要考虑已经放入 2n-2 个元素，即 n-1 个栈已经填满时，如果再加入新的元素 x 是应怎么操作。

注意到只有元素在栈底时我们才需要用到空栈来消除，假设当前要操作的新元素 x 是 a_i，那么我们从 i 开始往后找到第一个出现在栈底的元素 y，假设它是 a_j（当然也可能先遇到了一个新的 x），也就是说 a_{i+1 \dots j-1} 全都是出现在栈顶的元素，我们去看 y 所在栈的栈顶是否在 a_{i+1 \dots j-1} 中出现过，接下来有三种情况：

3. 若在遇到出现在栈底的元素之前先遇到了一个新的 x，即 a_j=x 时，此时因为 a_{i+1 \dots j-1} 中元素全部在栈顶出现，所以用不到空栈，直接将 a_i 压入空栈，操作到 a_j 时再将 a_i 消去即可。

考场我写的实现是 O(n \sum m) 的，瓶颈在于需要 O(n) 时间找到一个还没满两个元素的栈，这个用队列可以做到 O(1) 查找。

代码（在考场代码的基础上改成了可以AC洛谷数据的代码）：

//-O2 -std=c++14 -Wl,-stack=134217728 -Wall -Wextra -Wshadow
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define lowbit(x) (x & -x)
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 2e6+5;

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

int n, m, k, a[MAXN];
int stt[605], cur[605], tag[605], ban, cnt;//考场数组才开到305，，，

deque<int> Q[605];

struct info {
    int op, x, y;
} ans[MAXN * 2];

inline void bk_in(int num, int x) {
    ans[++cnt] = (info) { 1, num, num };
    if (!Q[num].empty()) stt[Q[num].back()] -= 2;
    Q[num].push_back(x);
    stt[x] = 2;
    cur[x] = num;
    if (Q[num].size() == 1) stt[x] = 3;
}

inline void bk_out(int num, int x) {
    ans[++cnt] = (info) { 1, num, num };
    stt[x] = 0;
    Q[num].pop_back();
    if (!Q[num].empty()) stt[Q[num].back()] |= 2;
}

inline void ft_out(int num, int x) {
    ans[++cnt] = (info) { 1, ban, ban };
    ans[++cnt] = (info) { 2, ban, num };
    stt[x] = 0;
    Q[num].pop_front();
    if (!Q[num].empty()) stt[Q[num].front()] |= 1;
}

void solve() {
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; i++) a[i] = read();
    for (int i = 1; i <= k; i++) tag[i] = 0;//考场才循环到n，，，

    ban = n; cnt = 0;
    for (int i = 1; i <= m; i++) {
        if (stt[a[i]] & 2) {
            bk_out(cur[a[i]], a[i]);
        } else if (stt[a[i]] & 1) {
            ft_out(cur[a[i]], a[i]);
        } else {
            for (int j = 1; j <= n; j++)
                if (Q[j].size() < 2 && j != ban) {
                    bk_in(j, a[i]);
                    break;
                }

            if (!stt[a[i]]) {//出现第2n+1种 
                for (int j = i + 1; j <= m; j++) {
                    if (stt[a[j]] == 1) {
                        if (tag[Q[cur[a[j]]].back()] == i) {
                            bk_in(ban, a[i]);
                            ban = cur[a[j]];
                        } else {
                            bk_in(cur[a[j]], a[i]);
                        }
                        break;
                    } else if (!stt[a[j]]) {
                        bk_in(ban, a[i]);
                        break;
                    } else {
                        tag[a[j]] = i;
                    }
                }
            }
        }
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++) {
        if (ans[i].op == 1) printf("1 %d\n", ans[i].x);
        else printf("2 %d %d\n", ans[i].x, ans[i].y);
    }
}

int main() {
    // freopen("meow.in", "r", stdin);
    // freopen("meow.out", "w", stdout);

    int T = read();
    while (T--) {
        solve();
    }
    return 0;
}

T3.barrack

为什么不把这题放T2 /fn/fn/fn

首先因为 B 只会摧毁一条道路，所以显然 e-DCC 中的边是可选可不选的，用 Tarjan 缩点（Tarjan还是我现糊的写法QAQ）以后无向图就变成了一颗树，问题就变成了在树上选出一个非空点集，这些点的虚树上的边必选，其他边可选可不选，求方案数，使用树形 dp 即可解决：

设状态 f_{i,0/1/2} 表示考虑以 i 为根的子树的方案数，0 为子树内没选点，1 为子树内选点的 lca 不是 i，2 为子树内选点的 lca 是 i 。转移比较基础，不写了。

出来以后群里就有人说T3样例缩完点全是链，我看大样例范围这么大以为很强就没拍，，，有点哈人，幸亏没挂。

考场代码：

//-O2 -std=c++14 -Wl,-stack=134217728 -Wall -Wextra -Wshadow
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define lowbit(x) (x & -x)
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 1e6+5;
const int Mod = 1e9+7;

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

int n, m, pw2[MAXN * 2], ans;
int dfn[MAXN], low[MAXN], sd[MAXN];
int stk[MAXN], top, cnte[MAXN], cntc[MAXN];
ll t[3][3], f[MAXN][3];

struct edge {
    int u, v;
} E[MAXN];

vector<int> G[MAXN], T[MAXN];

void Tarjan(int x, int fa) {
    dfn[x] = low[x] = ++dfn[0];
    stk[++top] = x;
    for (auto to : G[x]) {
        if (!dfn[to]) {
            Tarjan(to, x);
            low[x] = min(low[x], low[to]);
        } else if (to != fa) low[x] = min(low[x], dfn[to]);
    }

    if (!fa || low[x] == dfn[x]) {
        sd[stk[top]] = x;
        cntc[x] = 1;
        while (stk[top--] != x) sd[stk[top]] = x, cntc[x]++;
    }
}

void dfs(int x, int fa) {
    f[x][0] = pw2[cnte[x]];
    f[x][2] = (pw2[cntc[x] + cnte[x]] - f[x][0] + Mod) % Mod;
    for (auto son : T[x]) {
        if (son == fa) continue;
        dfs(son, x);
        cnte[x] += cnte[son] + 1;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                t[i][j] = f[x][i] * f[son][j] % Mod;

        f[x][0] = 2 * t[0][0] % Mod;
        f[x][1] = (2 * t[1][0] + t[0][1] + t[0][2]) % Mod;
        f[x][2] = (t[1][1] + t[1][2] + 2 * t[2][0] + t[2][1] + t[2][2]) % Mod;
    }

    ans = (ans + f[x][2] * pw2[m - cnte[x]]) % Mod;
}

int main() {
//  freopen("barrack.in", "r", stdin);
//  freopen("barrack.out", "w", stdout);
    n = read(), m = read();

    pw2[0] = 1;
    for (int i = 1; i <= n + m; i++) pw2[i] = (ll) pw2[i - 1] * 2 % Mod; 

    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        E[i].u = u, E[i].v = v;
        G[u].pb(v), G[v].pb(u);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            Tarjan(i, 0);

    for (int i = 1; i <= m; i++) {
        int u = E[i].u, v = E[i].v;
        if (sd[u] == sd[v]) cnte[sd[u]]++;
        else T[sd[u]].pb(sd[v]), T[sd[v]].pb(sd[u]);
    }

    dfs(1, 0);

    printf("%d", ans);
    return 0;
}
/*
4 4
1 2
2 3
3 1
1 4
*/

T4.match

为什么不把这题放 T3 /fn/fn/fn

套路题。

看到对区间的所有子区间求和，一眼扫描线模型，还是维护最大值，更套路了，直接用单调栈维护，修改是区间覆盖，查询区间 \sum A_iB_i 历史版本和，直接上线段树 O(n \log n) 解决，缺点是 tag 有点多，常数稍大，听说有分治 O(n \log^2 n) 的小常数做法，但是我不会/kk

关于维护历史版本信息的思路可以参考我写的博客线段树历史信息维护，不过感觉我写的也不是很明白嘛QAQ。

代码：

//P8868 [NOIP2022] 比赛
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef unsigned long long ll;
const int MAXN = 2.5e5+5;
const int Mod = 998244353;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

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

int n, q, a[MAXN], b[MAXN];
int stka[MAXN], topa, stkb[MAXN], topb;
ll ans[MAXN];

vector<pair<int, int> > Q[MAXN];

struct node {
    int ca, cb, len, t;
    ll sum, sa, sb, hs, ha, hb, h;
} T[MAXN << 2];

#define ls (p << 1)
#define rs (p << 1 | 1)

inline void push_up(int p) {
    T[p].sa = T[ls].sa + T[rs].sa;
    T[p].sb = T[ls].sb + T[rs].sb;
    T[p].sum = T[ls].sum + T[rs].sum;
    T[p].hs = T[ls].hs + T[rs].hs;
}

inline void cova(int p, ll k) { T[p].sa = T[p].len * k, T[p].ca = k, T[p].sum = k * T[p].sb; }
inline void covb(int p, ll k) { T[p].sb = T[p].len * k, T[p].cb = k, T[p].sum = k * T[p].sa; }
inline void adda(int p, ll k) {
    T[p].hs += T[p].sb * k;
    if (!T[p].cb) T[p].ha += k;
    else T[p].h += k * T[p].cb;
}

inline void addb(int p, ll k) {
    T[p].hs += T[p].sa * k;
    if (!T[p].ca) T[p].hb += k;
    else T[p].h += k * T[p].ca;
}

inline void addh(int p, ll k) { T[p].hs += T[p].len * k, T[p].h += k; }
inline void addt(int p, ll k) {
    T[p].hs += T[p].sum * k;                                    
    if (!T[p].ca && !T[p].cb) T[p].t += k;
    else if (!T[p].cb) T[p].ha += T[p].ca * k;
    else if (!T[p].ca) T[p].hb += T[p].cb * k;
    else T[p].h += k * T[p].ca * T[p].cb;
}

inline void push_down(int p) {
    if (int &t = T[p].t) addt(ls, t), addt(rs, t), t = 0;
    if (ll &t = T[p].ha) adda(ls, t), adda(rs, t), t = 0;
    if (ll &t = T[p].hb) addb(ls, t), addb(rs, t), t = 0;
    if (ll &t = T[p].h) addh(ls, t), addh(rs, t), t = 0;
    if (int &t = T[p].ca) cova(ls, t), cova(rs, t), t = 0;
    if (int &t = T[p].cb) covb(ls, t), covb(rs, t), t = 0;
}

void build(int p, int l, int r) {
    T[p].len = r - l + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void upd_a(int p, int l, int r, int gl, int gr, int k) {
    if (l >= gl && r <= gr) return cova(p, k);
    push_down(p);
    int mid = (l + r) >> 1;
    if (mid >= gl) upd_a(ls, l, mid, gl, gr, k);
    if (mid < gr) upd_a(rs, mid + 1, r, gl, gr, k);
    push_up(p);
}

void upd_b(int p, int l, int r, int gl, int gr, int k) {
    if (l >= gl && r <= gr) return covb(p, k);
    push_down(p);
    int mid = (l + r) >> 1;
    if (mid >= gl) upd_b(ls, l, mid, gl, gr, k);
    if (mid < gr) upd_b(rs, mid + 1, r, gl, gr, k);
    push_up(p);
}

ll qry(int p, int l, int r, int gl, int gr) {
    if (l >= gl && r <= gr) return T[p].hs;
    push_down(p);
    int mid = (l + r) >> 1; ll ret = 0;
    if (mid >= gl) ret = qry(ls, l, mid, gl, gr);
    if (mid < gr) ret += qry(rs, mid + 1, r, gl, gr);
    return ret;  
}

#undef ls
#undef rs

int main() {
    n = (read(), read());
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();

    q = read();
    for (int i = 1; i <= q; i++) {
        int l = read(), r = read();
        Q[r].eb(l, i);
    }

    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        while (topa && a[stka[topa]] < a[i]) topa--;
        while (topb && b[stkb[topb]] < b[i]) topb--;
        upd_a(1, 1, n, stka[topa] + 1, i, a[i]);
        upd_b(1, 1, n, stkb[topb] + 1, i, b[i]);
        stka[++topa] = stkb[++topb] = i;

        addt(1, 1);

        for (auto j : Q[i])
            ans[j.second] = qry(1, 1, n, j.first, i);
    }

    for (int i = 1; i <= q; i++) printf("%llu\n", ans[i]);
    return 0;
}