2021-10-11 22:19 春田花花幼稚园服装/纺织设计

关注

2021牛客OI赛前集训营-普及组题解（第四场）

Problem A. 多国语言

做法

设 $cnt_a(i):= \sum_{j=1}^{n} [a_j=i]$
$cnt_b(i):= \sum_{j=1}^{n} [a_j=i \mbox{ and }b_j=1]$ ，
这两个数组可以扫描一遍 $a,b$ 数组得到。

记 $S = \sum_{i=1}^{m} [cnt_b(i)>0]$ ，
如果 $S = 0$ ，输出 ">-<";
否则如果 $S \geq 2$ ，输出 "^v^";
否则只存在唯一的 $i$ ，满足 $cnt_b(i)>0$ ，如果此时 $cnt_b(i) = cnt_a(i)$ ，则输出 $i$ ，否则输出 "^v^"。

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

代码

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

const int maxn = 100100;
int cnt[maxn], cntb[maxn], a[maxn];

int main(void) {
//    freopen("sample.in", "r", stdin);
    int T; scanf("%d", &T);
    assert(1 <= T && T <= 10);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        assert(1 <= n && n <= 100000);
        assert(1 <= m && m <= 100000);
        for (int i=1; i<=m; i++) cnt[i] = cntb[i] = 0;
        for (int i=1; i<=n; i++) {
            scanf("%d", &a[i]);
            assert(1 <= a[i] && a[i] <= m);
            cnt[a[i]]++;
        }
        for (int i=1; i<=n; i++) {
            int b; scanf("%d", &b);
            assert(b == 0 || b == 1);
            if (b == 1) cntb[a[i]]++;
        }
        int num = 0, idx = 0;
        for (int i=1; i<=m; i++) if (cntb[i]) {
            num++;
            if (cntb[i] == cnt[i]) idx = i;
        }
        if (num == 1 && idx) {
            printf("%d\n", idx);
        } else if (num) {
            printf("^v^\n");
        } else {
            printf(">-<\n");
        }
    }
    return 0;
}

Problem B. double u

做法

将 $t$ 中所有 'w' 替换为 "uu"，所有 'm' 替换为 "nn"，假设替换后长度为 $l$ ，若 $l>n$ ，则贪心的选择最靠前的一个 "uu"/"nn" 子串替换为 'w'/'m'，这样可以使得 $l$ 减少1，一直替换直到 $l=n$ 。由于题意保证存在答案，则这样贪心一定能得到答案。

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

代码

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

const int maxn = 200200;
char s[maxn], t[maxn], u[maxn];

int main(void) {
//    freopen("sample.in", "r", stdin);
    int T; scanf("%d", &T);
    assert(1 <= T && T <= 10);
    while (T--) {
        int n; scanf("%d", &n);
        assert(1 <= n && n <= 100000);
        scanf("%s", t);
        int m = strlen(t);
        assert(1 <= m && m <= 100000);

        int l = 0;
        for (int i=0; i<m; i++) {
            if (t[i] == 'w') u[l++] = 'u', u[l++] = 'u';
            else if (t[i] == 'm') u[l++] = 'n', u[l++] = 'n';
            else u[l++] = t[i];
        }

        assert(l >= n);
        int d = l - n;
        for (int i=0, j=0; i<n; i++) {
            if (d) {
                if (u[j] == 'u' && u[j+1] == 'u') {
                    s[i] = 'w';
                    j += 2;
                    d--;
                } else if (u[j] == 'n' && u[j+1] == 'n') {
                    s[i] = 'm';
                    j += 2;
                    d--;
                } else s[i] = u[j++];
            } else s[i] = u[j++];
        }

        assert(d == 0);
        s[n] = 0;
        printf("%s\n", s);

    }
    return 0;
}

Problem C. 活动

做法

可以观察到，放一个物品必然使得篮子内重量加倍，因此最多只能放 $O(\log(n))$ 件物品。考虑动态规划， $dp(i,j):=$ 篮子内放 $i$ 件物品，当前重量为 $j$ 的方案数，则 $dp(i,j) = \sum_{1\leq k\leq n, k\not= y,k\leq j} dp(i-1,j-k)$
不妨假设 $n,x$ 同阶，那么直接求这个dp的复杂度为 $O(n^2 \log(n))$ 。

考虑到这个转移最多是一个连续的区间 $[l,r]$ 的和减去一个数，维护前缀和即可将转移复杂度优化到 $O(1)$ 。

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

代码

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

const int mod = 998244353;
const int maxn = 100100;

int f[21][maxn], sum[21][maxn];

int main(void) {
//    freopen("sample.in", "r", stdin);
    int n, x, y; scanf("%d%d%d", &n, &x, &y);
    assert(1 <= n && n <= 100000);
    assert(1 <= x && x <= 100000);
    assert(1 <= y && y <= n);
    f[0][0] = 1;
    for (int i=0; i<=x; i++) sum[0][i] = 1;
    for (int i=1; i<=20; i++) {
        for (int j=1; j<=x; j++) {
            f[i][j] = sum[i-1][j/2];
            if (j > n) f[i][j] = (f[i][j] - sum[i-1][j-n-1] + mod) % mod;
            if (j-j/2 <= y && y <= j) f[i][j] = (f[i][j] - f[i-1][j-y] + mod) % mod;
            sum[i][j] = (sum[i][j-1] + f[i][j]) % mod;
        }
    }

    int ans = 0;
    for (int i=0; i<=20; i++) ans = (ans + f[i][x]) % mod;
    printf("%d\n", ans);

    return 0;
}

Problem D. 迷宫

做法

将网络中每个格子到它的下一个格子连一条有向边，得到一个具有特殊性质的图。考虑在图上进行动态规划，具体来说，令 $f(u,0/1):=$ 左/右脚在结点 $u$ 时得到的最大答案，则 $f(u,0/1) = \pm v_u + \max\{0, f(nex_u, 1/0)\}$ 。( $nex_u$ 是 $u$ 指向的下一个结点。)

但这个图是可能存在环的，这意味着动态规划具有后效性。可以发现环上的结点数必然是偶数个。这是因为一个环内指向上的结点必然要和指向下的结点一样多，指向左的结点要和指向右的结点一样多。那么在环上，如果一开始以左脚踏入结点 $u$ ，则永远以左脚踏入结点 $u$ ，右脚同理。由于每次走完后，结点的权值会变成自己的相反数，因此走两圈相当于没走。
由此可以得到一个暴力，即从每个点开始一直走，直到某个点需要访问三次则停下。假设 $n,m$ 同阶，时间复杂度： $O(n^4)$ 。

上述做法复杂度的瓶颈在于求环上每个点的答案。考虑到从环上的结点 $u$ 出发，环的长度为 $l$ ，走第一圈时相当于走了一个从 $u$ 出发的长度 $\leq l$ 的区间，走第二圈时相当于走了一个到 $pre_u$ 结束的长度 $\leq l$ 的区间( $pre_u$ 是 $u$ 在环上的上一个结点)。这两部分的求解是完全相同的，可以把区间和拆成两个前缀和的差，然后求前缀和的一个环上的滑窗max，可以用单调队列做到 $O(l)$ 。因此最终时间复杂度为 $O(n^2)$ 。

代码

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

using ll = long long;
using ull = unsigned long long;

const ll B = (ll)1e15;
const ll C = (ll)2e15 + 21;

const int maxn = 1010;

char d[maxn];
int val[maxn * maxn], nex[maxn * maxn];
int vis[maxn * maxn], st[maxn * maxn], top, in_st[maxn * maxn], is_r[maxn * maxn];
vector <int> e[maxn * maxn];

ll f[maxn * maxn][2], g[maxn * maxn];

void Max(ll & x, ll y) { if (y > x) x = y; }

void ring_max(vector <int> & w) {
    static ll sum[maxn*maxn*2];
    static int que[maxn*maxn*2];

    int n = w.size();

    sum[0] = 0;
    for (int i=1; i<2*n; i++) sum[i] = sum[i-1] + w[(i-1<n)?(i-1):(i-1-n)];

    // g[l] = max(sum[r] - sum[l]), l+1 <= r <= l+n
    int head = 0, tail = 0;
    for (int i=0; i<2*n; i++) {
        while (tail < head && sum[que[head-1]] < sum[i]) head--;
        que[head++] = i;
        if (i-que[tail] >= n) tail++;
        if (i >= n) g[i-n] = sum[que[tail]] - sum[i-n];
    }
}


void fnd_ring(int u) {
    if (in_st[u]) {
        vector <int> a;
        for (int i=in_st[u]; i<=top; i++) {
            is_r[st[i]] = 1;
            a.push_back(st[i]);
        }

        // calc f[a[i]][0 / 1]
        int m = a.size();
        vector <int> w(m);

        for (int u=0; u<2; u++) {
            for (int i=0; i<m; i++) {
                if (i % 2 == u) w[i] = val[a[i]];
                else w[i] = -val[a[i]];
            }

            ring_max(w);
            for (int i=0; i<m; i++) {
                if (i % 2 == 0) Max(f[a[i]][u], g[i]);
                else Max(f[a[i]][!u], g[i]);
            }

            reverse(w.begin(), w.end());
            ring_max(w);
            for (int i=0; i<m; i++) {
                if (i % 2 == 0) Max(f[a[(m-i)%m]][u], g[i]);
                else Max(f[a[(m-i)%m]][!u], g[i]);
            }
        }

        for (int i=0; i<m; i++) Max(f[a[i]][0], 0);
        for (int i=0; i<m; i++) Max(f[a[i]][1], 0);

        return ;
    }
    if (vis[u] || nex[u] == -1) return ;

    vis[u] = 1;
    st[++top] = u;
    in_st[u] = top;

    fnd_ring(nex[u]);

    top--;
    in_st[u] = 0;
}

void dp(int u) {
    for (auto v : e[u]) {
        if (is_r[v]) continue;
        f[v][0] = val[v] + max(0ll, f[u][1]);
        f[v][1] = -val[v] + max(0ll, f[u][0]);
        dp(v);
    }
}

int main(void) {
//    freopen("sample.in", "r", stdin);

    int n, m; scanf("%d%d", &n, &m);
    assert(1 <= n && n <= 1000);
    assert(1 <= m && m <= 1000);
    for (int i=0; i<n; i++) {
        scanf("%s", d);
        assert(strlen(d) == m);
        for (int j=0; j<m; j++) {
            assert(d[j] == '^' || d[j] == 'v' || d[j] == '<' || d[j] == '>');
            int ni, nj;
            if (d[j] == '^') ni = i-1, nj = j;
            else if (d[j] == 'v') ni = i+1, nj = j;
            else if (d[j] == '<') ni = i, nj = j-1;
            else ni = i, nj = j+1;
            if (0 <= ni && ni < n && 0 <= nj && nj < m) {
                nex[i*m+j] = ni*m+nj;
                e[ni*m+nj].push_back(i*m+j);
            } else nex[i*m+j] = -1;
        }
    }

    for (int i=0; i<n*m; i++) {
        scanf("%d", &val[i]);
        assert(-(int)1e9 <= val[i] && val[i] <= (int)1e9);
    }

    for (int i=0; i<n*m; i++) f[i][0] = f[i][1] = -B;

    for (int i=0; i<n*m; i++) if (!vis[i]) fnd_ring(i);

    for (int i=0; i<n*m; i++) {
        if (is_r[i]) dp(i);
        if (nex[i] == -1) {
            f[i][0] = val[i];
            f[i][1] = -val[i];
            dp(i);
        }
    }

    ull ans = 0, c = 1;
    for (int i=0; i<n*m; i++) {
        ans += (ull)(f[i][0] + B) * c;
        c *= C;
    }
    printf("%llu\n", ans);

    return 0;
}