CLYZ-NOIP2021 国庆集训 B 组 Day1

题面：https://files.cnblogs.com/files/blogs/575626/day1B.zip

撰写博客

感觉很厉害，不明觉厉

我们令 \(dp_i\) 状态表示强制选择删除 \(i\) 位置并且干掉了 \(i\) 之前的和 \(i\) 所覆盖的线段的最小花费。

考虑状态转移，很显然就是

\[dp_i=\min_{pre_{i-1}}^{i-1}{dp_j}+w_i \]

其中 \(pre_{i}\) 为右端点为 \(i\) 的线段中，左端点最大值的前缀max。可以用 \(\text{KMP}\) 算法来预处理出来。

然后用单调队列转移即可。

时间复杂度为 \(O(n)\)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, N = 2e5 + 10;
inline long long read()
{
    long long ret = 0;
    char ch = ' ', c = getchar();
    while (!(c >= '0' && c <= '9'))
        ch = c, c = getchar();
    while (c >= '0' && c <= '9')
        ret = (ret << 1) + (ret << 3) + c - '0', c = getchar();
    return ch == '-' ? -ret : ret;
}
int n, m, nxt[N], pre[N];
char s[N], c[11][N];
int a[N], dp[N], q[N], l = 1, r;

void pretreat(int op)
{
    int j = 0, len = strlen(c[op] + 1);
    for (int i = 1; i < len; i++) {
        while (j && c[op][j + 1] != c[op][i + 1])
            j = nxt[j];
        if (c[op][j + 1] == c[op][i + 1])
            j++;
        nxt[i + 1] = j;
    }
}
void kmp(int op)
{
    int j = 0, len = strlen(s + 1), lenc = strlen(c[op] + 1);
    for (int i = 0; i < len; i++) {
        pre[i + 1] = max(pre[i], pre[i + 1]);
        while (j && c[op][j + 1] != s[i + 1])
            j = nxt[j];
        if (c[op][j + 1] == s[i + 1])
            j++;
        if (j == lenc)
            pre[i + 1] = max(pre[i + 1], i + 1 - lenc + 1), j = nxt[j];
    }
}
int main()
{
	freopen("wzadx.in", "r", stdin);
	freopen("wzadx.out", "w", stdout);
    n = read(), m = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i <= m; i++) {
        scanf("%s", c[i] + 1);
        pretreat(i);
        kmp(i);
    }
    n++;
    l = 1, r = 0;
    for (int i = 0; i <= n; i++) {
        while (l <= r && q[l] < pre[i - 1])
            l++;
        dp[i] = dp[q[l]] + a[i];
        while (l <= r && dp[q[r]] >= dp[i])
            r--;
        q[++r] = i;
    }
    printf("%d", dp[n]);
    return 0;
}

逛动物园

我们考虑这玩意，每个笼子最开始的答案应该是 \(3^n\)。

然后发现每次合并，左边的应该会乘上 \(\frac{2}{3}\)，右边的会乘上 \(\frac{1}{3}\)。

考虑离线下来，然后整一个类似于克鲁斯卡尔重构树的结构，用线段树维护 \(dfs\) 序列即可了。

似乎并没有什么方法可以在低于 \(O(n\log n)\) 的复杂度内解决。

#include <bits/stdc++.h>
using std::cerr;
using std::cin;
using std::cout;
using std::vector;
const int N = 4e5 + 10, mod = 998244353;
int n, m, f[N], op[N], x[N], y[N], dfc, st[N], ed[N], sz[N], F[N];
vector<int> v[N];
int ksm(int x, int y) {
    int res = 1;
    for (; y; y /= 2, x = (long long)x * x % mod) {
        if (y & 1) {
            res = (long long)res * x % mod;
        }
    }
    return res;
}
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void dfs(int u) {
    st[u] = dfc + 1;
    if (u <= n && u) {
        ed[u] = ++dfc;
        return;
    }
    for (auto &j : v[u]) {
        dfs(j);
    }
    ed[u] = dfc;
}
inline int ls(int k) { return k << 1; }
inline int rs(int k) { return k << 1 | 1; }
int val[N * 4];
inline void down(int k) {
    if (val[k] != 1) {
        val[ls(k)] = (long long)val[ls(k)] * val[k] % mod;
        val[rs(k)] = (long long)val[rs(k)] * val[k] % mod;
        val[k] = 1;
    }
}
void modify(int k, int l, int r, int ql, int qr, int x) {
    if (ql <= l && r <= qr) {
        val[k] = (long long)val[k] * x % mod;
        return;
    }
    down(k);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        modify(ls(k), l, mid, ql, qr, x);
    }
    if (mid < qr) {
        modify(rs(k), mid + 1, r, ql, qr, x);
    }
    return;
}
int query(int k, int l, int r, int x) {
    if (l == r) {
        return val[k];
    }
    down(k);
    int mid = (l + r) >> 1;
    return x <= mid ? query(ls(k), l, mid, x) : query(rs(k), mid + 1, r, x);
}
void build(int k, int l, int r) {
    val[k] = l == r ? 3 : 1;
    if (l != r) {
        int mid = (l + r) >> 1;
        build(ls(k), l, mid);
        build(rs(k), mid + 1, r);
    }
}
int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    std::ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
    }
    int tot = n;
    for (int i = 1; i <= m; ++i) {
        cin >> op[i] >> x[i];
        if (op[i] == 1) {
            cin >> y[i];
            ++tot;
            f[tot] = tot;
            v[tot].push_back(find(x[i]));
            v[tot].push_back(find(y[i]));
            f[find(x[i])] = tot;
            f[find(y[i])] = tot;
        }
    }
    for (int i = 1; i <= tot; ++i) {
        if (i == f[i]) {
            v[0].push_back(i);
        }
    }
    dfs(0);
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        sz[i] = 1;
    }
    tot = n;
    build(1, 1, dfc);
    for (int i = 1; i <= m; ++i) {
        if (op[i] == 1) {
            int _x = find(x[i]), _y = find(y[i]);
            modify(1, 1, dfc, st[_x], ed[_x], 2 * ksm(3, sz[_y] - 1) % mod);
            modify(1, 1, dfc, st[_y], ed[_y], ksm(3, sz[_x] - 1));
            ++tot;
            f[_x] = f[_y] = f[tot] = tot;
            sz[tot] = sz[_x] + sz[_y];
        } else {
            cout << (long long)query(1, 1, dfc, st[x[i]]) * ksm(3, n - sz[find(x[i])]) % mod << '\n';
        }
    }
    return 0;
}

序列修改

感觉也很厉害。

首先手玩一下发现只可能修改每个值第一次出现的位置，不妨设我们修改的位置是 \(x\)，那么肯定要修改成另外的一个值 \(a_y\)， \(y\) 也是第一次出现。

考虑 \(y\) 和 \(x\) 的大小关系，如果在前边的话，收益就是 \(|a_x-a_y|-S_x+S_y\)。

否则的话，讨论一下应该有 \(y<z\)，收益就是 \(|a_x-a_y|-S_y+S_z\)。这个东西可以根据 \(a_x\) 和 \(a_y\) 的大小关系用数据结构维护。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, N = 5e5 + 5;
int n, m, a[N], b[N], nxt[N];
long long sum[N], ans, del;
bool vis[N];
set<int> s;
map<int, int> lst;
struct BIT {
    long long c[N];
    BIT() { memset(c, -63, sizeof c); }
    void add(int x, long long v) {
        for (int i = x; i <= n; i += i & -i) {
            c[i] = max(c[i], v);
		}
    }
    long long query(int x) {
        long long ret = -INF;
        for (int i = x; i; i -= i & -i) {
            ret = max(ret, c[i]);
		}
        return ret;
    }
} tr1, tr2;
int main() {
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
	scanf("%d", &n);
    for (int i = n; i; i--) {
        sum[i] = sum[i + 1] + i;
    }
    for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
        if (!lst[a[i]]) {
            ans += sum[i];
            vis[i] = 1;
            b[++m] = a[i];
        } else {
            nxt[lst[a[i]]] = i;
        }
        lst[a[i]] = i;
        nxt[i] = n + 1;
    }
    sort(b + 1, b + m + 1);
    s.insert(-INF);
	s.insert(INF);
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            set<int>::iterator it = s.lower_bound(a[i]);
            del = min(del, -sum[i] + sum[nxt[i]] + *it - a[i]);
            del = min(del, -sum[i] + sum[nxt[i]] - *(--it) + a[i]);
            s.insert(a[i]);
        }
    }
    for (int i = n; i; i--) {
        if (vis[i]) {
            int pos = lower_bound(b + 1, b + m + 1, a[i]) - b;
            del = min(del, sum[nxt[i]] + a[i] - tr1.query(pos));
            del = min(del, sum[nxt[i]] - a[i] - tr2.query(n - pos + 1));
            tr1.add(pos, sum[i] + a[i]);
            tr2.add(n - pos + 1, sum[i] - a[i]);
        }
	}
    printf("%lld", ans + del);
    return 0;
}

摆放鞋子

考虑每个鞋子会有一个权值，左上右下为0123，那么总是可以在总权值模四不变的情况下对于图做调整。

考虑直接根据左右鞋子的关系跑出来一个二分图匹配。

然后如果设答案是 \(ans\)。在不是完美匹配的情况下，答案就是 \(ans\)。否则，我们看看匹配之后的图是不是和之前的权值和一样，然后不一样就是搞一个答案减一。