20231112题解

发表于 2023-11-12 分类于信奥，题解阅读次数：

好了我打脸了，这才是最后一篇。

真的要 AFO 了。

18 号之后可能还会出一下 NOIP 游记，然后退役。

plugin

~~为什么会有占用一个插座贡献 0 个插座的插线板啊。~~

贪心性质非常显然，肯定要从限制最小的手机开始考虑，并且层数较低的插线板应该尽可能的大。

但是直接贪心好像不太行：你不知道那些限制小的手机有几个要抛弃。

所以二分一下手机数量，剩下的贪心判断能否满足就好。

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

const int maxn = 4e5 + 5;
int n, m;
int a[maxn], b[maxn];

int main() {
    auto read = [&](auto &r) -> void {
        r = 0; int ch = getchar(), f = 0;
        while (!isdigit(ch)) { if (ch == 45) f ^= 1; ch = getchar(); }
        while (isdigit(ch)) { (r *= 10) += ch - 48; ch = getchar(); }
        if (f) r = -r;
    };
    // freopen("plugin.in", "r", stdin), freopen("plugin.out", "w", stdout);
    read(m); read(n);
    for (int i = 1; i <= m; i++) read(b[i]);
    for (int i = 1; i <= n; i++) read(a[i]);
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1, [&](int a, int b) -> bool { return a > b; });
    int l = 1, r = n, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if ([&](int x) -> bool {
            int dep = 0, cnt = 1, j = 0;
            for (int i = x; i <= n; i++) {
                while (dep < a[i]) {
                    int tcnt = 0;
                    while (j < m && cnt && b[j + 1]) cnt--, tcnt += b[++j];
                    cnt += tcnt;
                    dep++;
                }
                if (cnt) cnt--;
                else return false;
            }
            return true;
        }(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", n - l + 1);
    return 0;
}

string

哈希妙题。

判断有多少个不同的字符串只要哈希就可以了。但是哈希值怎么支持区间推平呢？

如果原字符串是 \(s\) 的话，我们常见的哈希其实是 \(h=\sum_{i=1}^{len}{131^{n - i}s_i}\) 之类的。容易发现，在固定位置上的哈希系数是固定的。

所以可以用线段树，维护两个值：一个是区间哈希系数总和，一个是区间哈希总和。推平的时候用系数乘上推平值即可。

进一步思考发现，这种做法的关键是抛弃了原来的哈希可以快速获得子串哈希的性质。既然如此，我们可以有更好的哈希系数：随即产生一个 \(a\) 序列，让 \(h=\sum_{i=1}^{len}{a_is_i}\) 就好。随机化哈希应该更不容易被卡。

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

template <class T>
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) {if (ch == 45) f ^= 1; ch = getchar(); }
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 5e5 + 5;
int n, len, m;
mt19937_64 rd(time(NULL));
unsigned long long h[maxn];
int tmp[maxn];

struct node; typedef node* pos;
struct node { unsigned long long val, hval; int l, r, tag; pos ls, rs; node() { ls = rs = this; }};
node buf[maxn << 1], *buf_pos = buf;
pos root[maxn];
pos new_node(int l, int r) { pos p = ++buf_pos; p -> ls = p -> rs = buf; p -> l = l, p -> r = r; return p; }
void push_up(pos p) { p -> val = p -> ls -> val + p -> rs -> val; p -> hval = p -> ls -> hval + p -> rs -> hval; }
void update_one(pos p, int x) { p -> tag = x; p -> val = p -> hval * x; }
void push_down(pos p) { if (p -> tag) update_one(p -> ls, p -> tag), update_one(p -> rs, p -> tag), p -> tag = 0; }
void build(pos p) {
    if (p -> l == p -> r) p -> hval = h[p -> l], p -> val = tmp[p -> l] * h[p -> l];
    else {
        int mid = (p -> l + p -> r) >> 1;
        p -> ls = new_node(p -> l, mid), build(p -> ls);
        p -> rs = new_node(mid + 1, p -> r), build(p -> rs);
        push_up(p);
    }
}
void update(pos p, int l, int r, int x) {
    if (l <= p -> l && p -> r <= r) return update_one(p, x);
    push_down(p);
    if (l <= p -> ls -> r) update(p -> ls, l, r, x);
    if (p -> rs -> l <= r) update(p -> rs, l, r, x);
    push_up(p);
}

map<unsigned long long, int> mp;

int main() {
    freopen("string.in", "r", stdin), freopen("string.out", "w", stdout);
    read(n); read(len); read(m);
    for (int i = 1; i <= len; i++) h[i] = rd();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= len; j++) {
            tmp[j] = getchar();
            while (!isalpha(tmp[j])) tmp[j] = getchar();
        }
        root[i] = new_node(1, len);
        build(root[i]);
        mp[root[i] -> val]++;
    }
    while (m--) {
        int id, l, r, x;
        read(id); read(l); read(r); x = getchar(); while (!isalpha(x)) x = getchar();
        if (!(--mp[root[id] -> val])) mp.erase(root[id] -> val);
        update(root[id], l, r, x);
        mp[root[id] -> val]++;
        printf("%lu\n", mp.size());
    }
    return 0;
}

qlx

你突然对我说七里香的名字很美我此刻却只想吻你倔强的嘴

类似于最长公共子序列，定义 \(f_{i,j}\) 表示以 \(s_i\) 结尾的 \(s\) 的子串匹配到 \(t_j\) 为止所需要的最短长度。为了方便转移，可以把最短长度改成最大左端点，即 \(f_{i,j}\) 是使得 \(s_l \sim s_i\) 包含子序列 \(t_1 \sim t_j\) 的最大 \(l\)。

这样转移就很简单：

\(s_i = t_j\)：\(f_{i,j} \leftarrow f_{i-1,j-1}\)
\(s_i \ne t_j\)：\(f_{i,j} \leftarrow f_{i-1,j}\)

优化就更显然了：能实现第一个转移的 \(j\) 只有一个，所以记录每一个 \(t_j\) 值对应的 \(j\) 是多少。剩下的部分继承前一个 \(i\) 就好。

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

template <class T>
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) {if (ch == 45) f ^= 1; ch = getchar(); }
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 1e6 + 5, maxm = 1e6 + 5;
int dp[maxm], n, m, _;
pair<int, int> ans;
int s[maxn], t[maxm], in_t[maxm];

int main() {
    freopen("qlx.in", "r", stdin), freopen("qlx.out", "w", stdout);
    read(_);
    while (_--) {
        read(n); read(m);
        for (int i = 1; i <= n; i++) read(s[i]);
        memset(in_t, 0, sizeof in_t);
        for (int i = 1; i <= m; i++) read(t[i]), in_t[t[i]] = i;
        ans = make_pair(0x3f3f3f3f, -1); memset(dp, 0xcf, sizeof dp);
        for (int i = 1; i <= n; i++) {
            int j = (s[i] <= 1e6) ? in_t[s[i]] : 0;
            if (j) {
                if (j == 1) dp[j] = max(dp[j], i);
                else dp[j] = max(dp[j], dp[j - 1]);
            }
            ans = min(ans, make_pair(i - dp[m] + 1, i));
        }
        if (ans.first > n) printf("-1\n");
        else printf("%d %d\n", ans.second - ans.first + 1, ans.second);
    }
    return 0;
}