2024/10 做题笔记

给你 $n$ 个数（$\le 3\times 10^4$），划分成连续的 $m$ 个段，使得每段数字之和构成长度为 $m$ 的数列的方差最小。

要输出方差乘上 $m^2$ 的结果。

首先，感觉方差这个东西不太好维护，所以说可以推一下式子。这里就直接放结果了。

$$s^2 = \frac{1}{m} \sum a_i^2 – \left(\frac{1}{m} \sum a_i\right)^2$$

发现式子的减号右边跟划分方案根本没有关系，因此我们的目标就是求 $\sum a_i^2$ 即平方和的最值。

我们记 $f(i, j)$ 为前 $i$ 段分到第 $j$ 个数的最小值。有下面这个转移：

$$
f(i, j) = \min_{k=1}^j { f(i – 1, k) + sum(k + 1, j)^2 }
$$

平方和使用前缀和维护，这样我们就有了 $O(n^2)$ 的做法了。然后怎么优化呢？

于是咱就去学了一下斜率优化。

变换一下上面的式子，先把第一维压缩掉，把前缀和式子写进去，然后把跟 $k$ 无关的挪到等号左边去：

$$
\begin{aligned}
f(i) &= \min_{k=1}^i \lbrace g(k) + (pre(i) – pre(k))^2 \rbrace \\
f(i) &= \min_{k=1}^i \lbrace g(k) + pre(i)^2 + pre(k)^2 – 2\cdot pre(i)\cdot pre(k) \rbrace \\
f(i) – pre(i)^2 &= \min_{k=1}^i \lbrace g(k) + pre(k)^2 – 2\cdot pre(i)\cdot pre(k) \rbrace
\end{aligned}
$$

设式子左边为 $b_i$、$y_k = g(k) + pre(k)^2$、$x_k = pre(k)$、$t_i = 2\cdot pre(i)$，则有：

$$
b_i = \min_{k\lt i} { y_k – t_ix_k }
$$

$k$ 在最优决策下，有

$$
b_i = y_k – t_i x_k
$$

如果我们将 $(x_k, y_k)$ 视作一些点，如果我们需要最小化截距 $b_i$，已知 $t_i$，画个图是这样的：

（点 D、H 不作为决策点，为辅助点）

如果将红色线条逐个上移，那么我们会发现 C 在任何时候都不会被扫到，因此可以忽略。而且对于任意斜率也是如此。对于这个情景而言，F 为最优点，而且这个点可以保证 $t_i$ 在 $EF$ 的斜率和 $AF$ 的斜率之间。又由于对于每一轮决策 $t_i$ 单调递增，因此忽略最下面的两个点也无妨。

这启示着我们使用一种数据结构去维护这些点，就是单调队列，保证里面斜率单调递增/递减即可。这东西可以维护一个凸包。然后分讨一下这些点的决策到底是哪个方向就行了。

#define cmp <
using namespace std;

const int MAXN = 3005;

int last[MAXN], f[MAXN], qaq[MAXN], pre[MAXN];
int n, m;

template<class T>
inline T square(T x) { return x * x; }

int head, tail;
int que[MAXN];

inline void clear() { tail = 0, head = 1; }
inline int getx(int j) { return pre[j]; }
inline int gety(int j) { return last[j] + square(pre[j]); }

inline double slope(int fr, int bk) { return 1. * (gety(bk) - gety(fr)) / (getx(bk) - getx(fr)); }

inline void push(int k)
{
    while (head < tail && slope(que[tail], k) cmp slope(que[tail - 1], que[tail]))
        tail--;
    que[++tail] = k;
}
inline void pop(double k)
{
    while (head < tail && slope(que[head], que[head + 1]) cmp k)
        head++;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(last, 0x3f, sizeof last);
    last[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> qaq[i];
        pre[i] = qaq[i] + pre[i - 1];
    }

    for (int i = 1; i <= m; i++) {
        clear();
        push(i - 1);
        for (int j = i; j <= n; j++) {
            pop(2 * pre[j]);
            int k = que[head];
            f[j] = last[k] + square(pre[j] - pre[k]);
            push(j);
        }
        memcpy(last, f, sizeof(int) * (n + 1));
    }
    cout << f[n] * m - square(pre[n]) << '\n';
}

「ARC117C」Tricolor Pyramid

题意不去叙述了。

如果把每个颜色对应 $0\sim 2$ 的数字，记最底下那一层是 ${a_n}$，玩一下会发现，第一层会有一个杨辉三角的规律。然后就是对 $3$ 取模。

这个时候需要 Lucas 定理辅助一下，因为 $3$ 这个模数太小了。

const int MODN = 3;

int C(int n, int m) {
    if (n < m) return 0;
    int res = 1;
    for (int i = n - m + 1; i <= n; i++) res *= i;
    for (int i = 1; i <= m; i++) res /= i;
    return res % 3;
}


int lucas(int n, int m)
{
    if (m == 0) return 1;
    if (n < m) return 0;
    return lucas(n / 3, m / 3) * C(n % 3, m % 3) % 3;
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        char ch;
        cin >> ch;
        ans = ans + lucas(n - 1, i - 1) * (ch == 'B' ? 0 :
                                           ch == 'W' ? 1 : 2);
        ans %= MODN;
    }
    if (n % 2 == 0) {
//      cout << "mod\n";
        ans = (3 - ans) % 3;
    }
    ans = (ans % MODN + MODN) % MODN;
    cout << (
        ans == 0 ? 'B' :
        ans == 1 ? 'W' : 'R'
    );
}

「AHOI2005」矿藏编码

哎哎题意就不放了。就是深搜然后计算 $4$ 的很多次方。理论上要高精度，实际上 u128 就行了。

use std::io::{self, Read};

fn work(x: i32, ans: &mut u128, input: &mut impl Iterator<Item = u8>) {
    if let Some(tmp) = input.next() {
        if tmp == b'2' {
            for _ in 0..4 {
                work(x - 1, ans, input);
            }
        } else if tmp == b'0' {
            *ans += 4_u128.pow(x as u32);
        }
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();

    let mut input = input.split_whitespace();
    let k: i32 = input.next().unwrap().parse().unwrap();

    let mut char_iter = input.next().unwrap().bytes();
    let mut ans = 0;

    work(k, &mut ans, &mut char_iter);

    println!("{}", ans);
}

「NOIP1998 提高组」进制位

题意略。

首先显然可以证明进制数就是表格的列数 – 1。然后你会发现这道题的 $n$ 很小，所以可以 $O(n!)$ 枚举然后 $O(n^2)$ check。但是写起来很恶心。

char ltr[10];
string mp[10][10];
map<char, int> idxof;
map<char, int> wei;
char rewei[10];
int n;

inline void print_wei() {
    for (int i = 1; i <= n; i++) {
        cout << ltr[i] << "=" << wei[ltr[i]] << ' ';
    }
}

inline string add(string a, string b) {
    for (auto &ch : a) ch = wei[ch];
    for (auto &ch : b) ch = wei[ch];
    string c = "qq";
    c[0] = a[0] + b[0];
    c[1] = c[0] / n; c[0] %= n; c[1] += a[1] + b[1];
    if (c[1] == 0) c.pop_back();
    for (auto &ch : c) ch = rewei[ch];
    reverse(c.begin(), c.end());
    return c;
}

inline bool check() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (add(string() + ltr[i], string() + ltr[j]) != mp[i][j]) return false;
        }
    }
    return true;
}


void dfs(int u) {
    if (u == n + 1) {
        if (check()) {
            for (int i = 1; i <= n; i++) {
                cout << ltr[i] << "=" << wei[ltr[i]] << ' ';
            }
            cout << '\n' << n << '\n';
            throw 1;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!rewei[i]) {
            rewei[i] = ltr[u];
            wei[ltr[u]] = i;
            dfs(u + 1);
            rewei[i] = 0;
            wei[ltr[u]] = -1;
        }
    }
}

int main()
{
    cin >> n; n--;
    string ch; cin >> ch;
    for (int i = 1; i <= n; i++) {
        cin >> ltr[i];
        idxof[ltr[i]] = i - 1;
    }
    for (int i = 1; i <= n; i++) {
        char r;
        cin >> r;
        r = idxof[r] + 1;
        for (int j = 1; j <= n; j++) {
            cin >> mp[r][j];
        }
    }
    try {
        dfs(1);
    } catch (int) {
        return 0;
    };
    cout << "ERROR!\n";
}

「HAOI2017」方案数

https://www.luogu.com.cn/record/181138333

「ABC207E」Mod i

https://www.luogu.com.cn/record/181255389

洛谷 P6327 区间加区间 sin 和

维护两个操作，区间加、区间求 sin 和。

对于 sin 值有，

$$
\sin(a + b) = \sin a\cos b + \cos a\sin b
$$

这样就可以线段树维护了。

inline void pushdown(int p)
{
    if (tr[p].lz) {
        updlz(p << 1, tr[p].lz);
        updlz(p << 1 | 1, tr[p].lz);
        tr[p].lz = 0;
    }
}

inline void updlz(int p, long long val)
{
    double sina = tr[p].sine, cosa = tr[p].cosine;
    double sinx = sin(val), cosx = cos(val);
    tr[p].sine = sina * cosx + cosa * sinx;
    tr[p].cosine = cosa * cosx - sina * sinx;
    tr[p].lz += val;
}

「CQOI2007」涂色

假设你有一条长度为 $5$ 的木板，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：$\texttt{RGBGR}$。

每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 $\texttt{RRRRR}$，第二次涂成 $\texttt{RGGGR}$，第三次涂成 $\texttt{RGBGR}$，达到目标。

用尽量少的涂色次数达到目标。

数据范围 $n\le 50$。

这道题看起来像是个区间 DP，这数据范围小得有点夸张了。对于每一个区间有两种情况：

如果区间两端颜色相同，如果每次区间转移只添加一侧的端点，那么可以证明这个时候不需要多涂色。
否则枚举断点，然后求断点两边涂色次数的和的最小值。

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> s;
    int n = s.length();
    s = " " + s;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) f[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if (s[l] == s[r]) {
                f[l][r] = min(f[l + 1][r], f[l][r - 1]);
            } else {
                for (int m = l; m < r; m++) {
                    f[l][r] = min(f[l][r], f[l][m] + f[m + 1][r]);
                }
            }
        }
    }
    cout << f[1][n] << '\n';
}

「MX-X5-T0 / GFOI Round 1」Hypnotize

哎源批收收味。

找一串数字中是否存在两个数字相差 $k$。数据范围 100。

两个方法：

暴力做 $O(n^2)$。枚举 $i, j$ 然后依次做差判断。
值域做 $O(n\log n)$。开个 set 记一下 $a_i$ 然后挨个看有没有 $a_i + k$ 有没有在 set 里。

int main()
{
    int n, k;
    set<int> s;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        s.insert(t);
    }
    for (auto x : s) {
        if (s.count(x + k)) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
}

关路灯

https://www.luogu.com.cn/record/182325092

「ABC328E」Modulo MST

其实这个之前做过，但是因为后来被拉到题单里面了没写记录然后就只写一个记录算了。

求一个最小生成树，但是权值在模 $K$ 意义下最小。

看起来很吓人对不对！但这是 ABC，然后一看数据范围 $N \le 8, M \le \frac{N(N-1)}{2}$，然后就可以开始暴力了。

Submission

「ABC174E」Logs

https://www.luogu.com.cn/record/182517337

「ABC244E」King Bombee

https://www.luogu.com.cn/record/182574143

「ABC129E」Sum Equals Xor

https://www.luogu.com.cn/record/182740646

「ABC133E」Virus Tree 2

https://www.luogu.com.cn/record/182783033

「ABC137E」Coins Respawn

https://www.luogu.com.cn/record/182796843

「POI2015」Trzy wieże (TRZ)

（证明待补充有人看到了踢我一脚我去补）

可以证明答案的端点必定在前三个或者后三个里面。

template<int delta, class Cmp>
int bf(int l, int r, Cmp cmp)
{
    int cnt[3] = { 0, 0, 0 };
    int ans = 0;
    for (int i = l; cmp(i, r); i += delta) {
        if (s[i] == 'B') cnt[0]++;
        else if (s[i] == 'C') cnt[1]++;
        else cnt[2]++;
        if (
            (cnt[0] == 0 || cnt[1] == 0 || cnt[0] != cnt[1]) &&
            (cnt[1] == 0 || cnt[2] == 0 || cnt[1] != cnt[2]) &&
            (cnt[0] == 0 || cnt[2] == 0 || cnt[0] != cnt[2]))
        {
            ans = max(ans, abs(i - l) + 1);
        }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> s;
    cout << max({
        bf<1>(0, n, less<int>{}),
        bf<1>(1, n, less<int>{}),
        bf<1>(2, n, less<int>{}),
        bf<-1>(n - 1, 0, greater_equal<int>{}),
        bf<-1>(n - 2, 0, greater_equal<int>{}),
        bf<-1>(n - 3, 0, greater_equal<int>{}),
    });
}

洛谷 P1638 逛画展

博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。

游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 $a,b$，数据保证一定有解。

等下为什么最近在补这么简单的题目。

本题可以双指针。给画师记个数然后双指针扫。扫到满足条件的就 ok。

for (int i = 1; i <= n; i++) cin >> id[i];
int r = 1;
cnt[id[1]]++; knd = 1;
for (int l = 1; l <= n; l++) {
    while (r < n && knd < k) {
        r++;
        if (cnt[id[r]] == 0) knd++;
        cnt[id[r]]++;
    }
    if (knd == k) {
        if (r - l < ansr - ansl) {
            ansr = r, ansl = l;
        }
    }
    cnt[id[l]]--;
    if (cnt[id[l]] == 0) knd--;
}
cout << ansl << ' ' << ansr << '\n';

「CSP-S 2023」结构体

~~按照题意模拟即可。~~

实现细节比较多。直接看题目最下面的形式化定义，然后按照形式化定义写会好很多，要不然我理解了半天样例 2 都看不懂。

可以发现，对于每一个数据类型（即结构体），只要知道了其内存对齐和大小，那么在该类型被嵌套的情况下，可以推出父类型的对齐和大小。

对于一个结构体而言，我们可以存储每一个成员相对于该结构体的基地址的偏移（offset），这样在随机地址访问的时候可以二分到这个地方，而且你会发现算地址的时候很好算（可以递归计算），且形式化定义也是从偏移出发的。

对于每一个对象，你不需要真正把空间开满，只需要记住该对象在全局作用域的偏移（起始地址）和类型。这样只需要对偏移动手脚了。

要记住在操作 4（即随机地址访问）的时候对于全局作用域的对象进行判空。

因为数据量不大所以直接 string 乱飞值拷贝随便整反正时间复杂度没问题！

Submission

「CSP-S 2021」回文

https://loj.ac/s/2185225

「CSP-S 2021」廊桥分配

机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。

L 市新建了一座机场，一共有 $n$ 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻，请你负责将 $n$ 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。

保证同一时刻只有一架飞机起降。

现在只看一个区。假如我们把所有的廊桥全部分给一个区，如果我们贪心地、每次分配编号最小的可用廊桥，那么会发现下面的性质：

因为是先来后到的原则，对于廊桥分配的数量，如果廊桥数量限制为 $l$，则等价于所有编号 $\gt l$ 的廊桥无法被分配到飞机。

可以预处理出两个区在最大编号为 $1\sim n$ 的时候最多可以分配到廊桥的飞机数量。

Submission

「NOI Online 2021 入门组」切蛋糕

玩一下会发现这东西是分类讨论。

对于 2 个 0：答案是 0。
对于 1 个 0：如果是对半分，则答案是 1；否则答案是 2。
对于全都不是 0：
- 如果存在 $a + b = c$，相当于对半分之后再分一刀，答案是 $2$。
- 如果存在 $a = b$，你会发现切两刀之后，因为对顶角相等，所以可以保证存在一种分法使得 $a = b$。这个情况就等价于 1 个 0 时的后面的情况。
- 无论想怎么分，都不会超过 3 刀。

while (t--) {
    cin >> ar[0] >> ar[1] >> ar[2];
    sort(ar.begin(), ar.end());
    if (ar[1] == 0) {
        cout << "0\n";
    } else if (ar[0] == 0) {
        if (ar[1] == ar[2]) cout << "1\n";
        else cout << "2\n"; 
    } else {
        if (ar[0] == ar[1] || ar[1] == ar[2]) {
            cout << "2\n";
        } else if (ar[0] + ar[1] == ar[2]) {
            cout << "2\n";
        } else {
            cout << "3\n";
        }
    }
}

！「NOI Online 2022 提高组」丹钓战

https://www.luogu.com.cn/record/184571401

「NOIP2002 提高组」字串变换

这题比较神秘。暴力广搜就能通过测试数据。但是他说这是个错题。

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> a >> b;
    int n = 0;
    while (cin >> rules[n].first >> rules[n].second) n++;
    q.push(a);
    dist[a] = 0;
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int d = dist[p];
        if (d > 10) break;
        if (dist.count(b)) {
            cout << dist[b] << '\n';
            return 0;
        }
        for (int i = 0; i < n; i++) {
            auto lpos = p.find(rules[i].first);
            while (lpos != string::npos) {
                string x = p;
                x.replace(lpos, rules[i].first.size(), rules[i].second);
//              cout << p << ' ' << x << '\n';
                if (!dist.count(x)) {
                    dist[x] = d + 1;
                    q.push(x);
                }
                lpos = p.find(rules[i].first, lpos + 1);
            }
        }
    }
    if (dist.count(b)) {
        cout << dist[b] << '\n';
    } else {
        cout << "NO ANSWER!\n";
    }
}

「ABC131E」Friendships

构造一个有 $n$ 个节点的简单图使得恰好仅有 $k$ 对节点 $(u, v)\space (u < v)$ 之间的最短距离为 $2$。

先猜一下，如果这张图是菊花的话，那么满足条件的点对最多。看起来像是一个比较显然的结论。那么可以发现，$\frac{1}{2}(n-1)(n-2)$ 是 $k$ 满足条件的上界。如果我们连接 $u\to v$，那么这两点的最短路径变为 1。因此我们可以从菊花图的基础上构建一个图，如果 $(u, v)$ 太多了就连起来让这些点对恰好减少 1 个。

int main()
{
    cin >> n >> k;
    int x = (n - 1) * (n - 2) / 2;
    if (k > (n - 1) * (n - 2) / 2) {
        cout << "-1\n";
        return 0;
    }
    cout << n - 1 + x - k << '\n';
    int cnt = 1;
    for (int i = 2; i <= n; i++) cout << 1 << ' ' << i << '\n';
    for (int i = 2; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (cnt > x - k) break;
            cnt++; cout << i << ' ' << j << '\n';
        }
    }
}

「ABC155E」Payment

有 $10^{100} + 1$ 种不同面值的十进制货币，每种面值分别为 $10^{i-1}$。你现在需要买一个 $N$ 元的东西（$N \le 10^{1,000,000}$），而且你和店员有无限多货币，求付钱以及找零所花费的货币个数的最小值。

一眼 dp。设式子 $f(i, j_{0/1})$ 表示第 $i$ 种货币（相当于从最低位枚举）可以分别直接支付（$j = 0$）或者通过找零（$j = 1$）可消耗的最少的货币数量。

有下面的式子：

$$
\left\{
\begin{aligned}
f(i, 0) &= \min(f(i – 1, 0), f(i – 1, 1) + 1) + a_i & \text{可以直接支付} \\
& & \text{或再付 1 张然后凑找零} \\
f(i, 1) &= \min(f(i – 1, 0), f(i – 1, 1) – 1) + 10 – a_i & \text{直接付或找零} \\
& & \text{多一张减掉} \\
\end{aligned}
\right.
$$

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> s;
    reverse(s.begin(), s.end());
    int n = s.size();
    f[0][0] = s[0] - '0';
    f[0][1] = 10 - (s[0] - '0');
    for (int i = 1; i < n; i++) {
        f[i][0] = min(f[i - 1][0], f[i - 1][1] + 1) + s[i] - '0';
        f[i][1] = min(f[i - 1][0], f[i - 1][1] - 1) + 10 - (s[i] - '0');
    }
    ll ans = min(f[n - 1][0], f[n - 1][1] + 1);
    cout << ans << '\n';
}

或者这个题还有一个贪心策略，大概就是凑 $5$ 是最优的。在这里就略了。

「ABC159E」Dividing Chocolate

~~切切切切切你说得对但是我没有切力。~~

给你一个最大 $10\times 1000$ 的 0/1 网格图，可以横着或者竖着切几刀，要求判断最少切几刀才可以使所有块里面 1 的个数不超过 $k$。

注意到有一维非常小，可以 $2^n$ 枚举。然后另一维贪心处理。

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    int ans = 1145141919;
    for (int stat = 0; stat < (1 << (n - 1)); stat++) {
        // slice after i
        int r = __builtin_popcount(stat);

        memset(cnt, 0, sizeof cnt);

        for (int j = 1; j <= m; j++) {
            int rd = 0;
            for (int i = 0; i < n; i++) {
                cnt[1][rd] += arr[i][j] - '0';
                if (stat & (1 << i)) {
                    rd++;
                }
            }
            for (int i = 0; i <= rd; i++) if (cnt[0][i] + cnt[1][i] > k) {
                r++;
                memcpy(cnt[0], cnt[1], sizeof cnt[0]);
                memset(cnt[1], 0, sizeof cnt[0]);
                break;
            }
            for (int i = 0; i <= rd; i++) {
                cnt[0][i] += cnt[1][i];
                if (cnt[0][i] > k) r = 0x3f3f3f3f;
            }
            memset(cnt[1], 0, sizeof cnt[0]);
        }
        ans = min(ans, r);
    }
    cout << ans << '\n';
}

「ROI 2019 Day1」Московские числа 拍照

题意：给你一个无色序列，你现在需要给序列区间染色以构造出给定的序列，要求给出构造方案，每种颜色只能使用一次。

由于每种颜色只能使用一次，因此可以先处理出每个节点出现的最左和最右的端点。显然这两个点之间必须被涂色。因此可以试着用线段树维护涂色，将所有左右端点排序后依次染色，如果涂出来的序列恰好是给定的序列则 ok。

struct {
    struct { int l, r, lz, val; } tr[5000006];
    void build(int l, int r, int p = 1) {
        tr[p] = {l, r, 0, 0};
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1);
    }
    inline void updlz(int p, int val) { tr[p].lz = tr[p].val = val; }
    inline void pushd(int p) { if (tr[p].lz) updlz(p << 1, tr[p].lz), updlz(p << 1 | 1, tr[p].lz), tr[p].lz = 0; }
    void upd(int l, int r, int x, int p = 1) {
        if (l > tr[p].r || tr[p].l > r) return;
        if (l <= tr[p].l && tr[p].r <= r) return updlz(p, x);
        pushd(p);
        upd(l, r, x, p << 1), upd(l, r, x, p << 1 | 1);
    }
    int qry(int x, int p = 1) {
        if (tr[p].l == tr[p].r) return tr[p].val;
        int mid = (tr[p].l + tr[p].r) >> 1;
        pushd(p);
        if (x <= mid) return qry(x, p << 1);
        return qry(x, p << 1 | 1);
    }
} seg;

int m, n;
int ll[300005], rr[300005], d[300005];
vector<array<int, 3>> rg;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        cin >> d[i];
        if (!ll[d[i]]) ll[d[i]] = i;
        rr[d[i]] = i;
    }
    seg.build(1, m);
    for (int i = 1; i <= n; i++) if (ll[i] && rr[i]) rg.push_back({ ll[i], rr[i], i });
    sort(rg.begin(), rg.end());
    for (auto x : rg) {
        seg.upd(x[0], x[1], x[2]);
    }
    for (int i = 1; i <= m; i++) {
        if (seg.qry(i) != d[i]) {
            cout << "-1\n";
            return 0;
        }
    }
    cout << rg.size() << '\n';
    for (auto x : rg) {
        cout << x[2] << ' ' << x[0] << ' ' << x[1] << '\n';
    }
}

「USACO 2012 December (Gold)」First!

aka [USACO12DEC] First! G

USACO | Luogu

给你一堆字符串 $s_i$，让你判断「是否有一种重新排列字母表的方式使得第 $i$ 个字符串的字典序最小」。

看到字典序这个东西应该想到字典树。如果我们把所有字符串都放在字典树上的话，那么可以发现，如果我们希望一个串字典序最小，那么在这个串在每一层都应该放在第一个。每一层的约束都不多，所以可以在遍历每一层的时候处理出每一个字母的拓扑关系，然后跑拓扑排序就可以啦。

但是！要注意字典序比较是包含长度的，如果一个字符串存在前缀，那么它永远不可能排到第一个的！

string team[30005];

struct Node {
    Node* child[26];
    int end = 0;
    Node() { memset(child, 0, sizeof child); }
};

Node* root = new Node;

void insert(const string& s)
{
    Node* cur = root;
    for (auto ch : s) {
        if (!cur->child[ch - 'a']) cur->child[ch - 'a'] = new Node;
        cur = cur->child[ch - 'a'];
    }
    cur->end++;
}
bool buildup(const string& s)
{
    Node* cur = root;
    for (auto ch : s) {
        int x = ch - 'a';
        for (int i = 0; i < 26; i++) {
            if (i != x && cur->child[i]) addedge(i, x);
        }
        if (cur->end) return false;
        cur = cur->child[ch - 'a'];
    }
    return true;
}
bool topo()
{
    queue<int> q;
    vector<int> res;
    for (int i = 0; i < 26; i++) if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int top = q.front(); q.pop();
        res.push_back(top);
        for (int e = head[top]; e; e = ed[e].nxt) {
            int v = ed[e].v;
            if (!--deg[v]) q.push(v);
        }
    }
    if (res.size() != 26) return false;
    return true;
}

int flag[30005], cnt;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> team[i];
        insert(team[i]);
    }
    for (int i = 1; i <= n; i++) {
        edcnt = 0;
        memset(head, 0, sizeof head);
        memset(deg, 0, sizeof deg);
        if (buildup(team[i]) && topo()) {
            flag[i] = true; cnt++;
        }
    }
    cout << cnt << '\n';
    for (int i = 1; i <= n; i++) {
        if (flag[i]) cout << team[i] << '\n';
    }
}

「COTS 2019」Vezuv 排名

其实这个题和上面那个题是一样的，只不过需要算出方案而已。

@@ -12,7 +12,7 @@
 int n, m;


-string team[30005];
+string team[25005];

 struct Node {
    Node* child[26];
@@ -57,7 +57,7 @@
    }
    return true;
 }
-bool topo()
+void topo()
 {
    queue<int> q;
    vector<int> res;
@@ -80,12 +80,13 @@
        }
    }

-   if (res.size() != 26) return false;
-   return true;
+   if (res.size() != 26) cout << "nemoguce\n";
+   else {
+       for (auto x : res) cout << char(x + 'a');
+       cout << '\n';
+   }
 }

-int flag[30005], cnt;
-
 int main()
 {
    ios::sync_with_stdio(false);
@@ -99,12 +100,10 @@
        edcnt = 0;
        memset(head, 0, sizeof head);
        memset(deg, 0, sizeof deg);
-       if (buildup(team[i]) && topo()) {
-           flag[i] = true; cnt++;
+       if (buildup(team[i])) {
+           topo();
+       } else {
+           cout << "nemoguce\n";
        }
    }
-   cout << cnt << '\n';
-   for (int i = 1; i <= n; i++) {
-       if (flag[i]) cout << team[i] << '\n';
-   }
 }

「ROIR 2024 Day2」Бактерии 细菌 / 细菌实验