2026 ICPC EC Online Contest I 比赛小结 + 补题

· · 算法·理论

题目链接

前言

虽然是临时替补一场，好歹也是 ICPC 初见吧，所以写份博客 + 补题

AC：A，C，F，L，M；

Rank：849th，校排 4th / 5th

个人可以接受的结果吧，校内上面三队本来水平就更高，该做的也都做了。

唯一可惜的是最后 D 没想到我们做法的剪枝，就很简单的一行啊！

希望未来会更好。

个人题解

F - 50 Years of Excellence

题意

给出连续 n 年的题目评分，每年恰好有 m 道题，第 i 年第 j 道题的整数评分为 a_{i,j}。

一年的总分定义为这一年所有题目评分的和。

我们称一年为优秀的，当且仅当这一年的总分严格小于前一年的总分。

特别地，第一年之前一年的总分定义为 0，第一年也按此规则判断。

求有多少个优秀的年份。

思路

第一个签到，手速慢了。。

考虑到 n,m 都很小，直接暴力计算每一年的总分，与维护的上一年的总分进行比较，计算答案即可。

复杂度 O(nm)。

代码

inline void solve() {
    ll n, m; cin >> n >> m;
    ll pre = 0, ans = 0;
    for (int i = 1; i <= n;++i) {
        ll res = 0;
        for (int j = 1; j <= m;++j) {
            ll e; cin >> e;
            res += e;
        }
        if (res < pre) ans++;
        pre = res;
    }
    cout << ans;
}

M - Check In

题意

给出包含 n 支参赛队伍的名单，队名两两不同。再按顺序给出 m 次签到查询，每次查询给出一个队名。名单中的队名和查询中的队名均只由大小写英文字母组成。

对于每次查询，按以下规则输出结果：

思路

第二个签到，一个 set 维护有效用户名，另一个 set 动态维护已出现的用户名，对于每个询问分支判断即可。

代码

inline void solve() {
    int n, m; cin >> n >> m;
    unordered_set<string> st;
    for (int i = 1; i <= n;++i) {
        string s; cin >> s;
        st.insert(s);
    }
    unordered_set<string> vis;
    for (int i = 1; i <= m;++i) {
        string t; cin >> t;
        if (!st.count(t)) cout << "WRONG\n";
        else {
            if (!vis.count(t)) cout << "OK\n";
            else cout << "REPEAT\n";
            vis.insert(t);
        }
    }
}

C - Permutation Inversions

题意

有一个未知的长度为 n 的排列 p（由 1 到 n 组成），给出关于它的 m 条限制。

每条限制给出一个区间 [l_i,r_i]，以及这个区间内所有下标的一个排列 q_{i,1},q_{i,2},\ldots,q_{i,r_i-l_i+1}，表示：

p_{q_{i,1}} < p_{q_{i,2}} < \cdots < p_{q_{i,r_i-l_i+1}}

构造一个满足所有限制，且逆序对数量最少的排列 p。逆序对指满足 1 ≤ x < y ≤ n 且 p_x > p_y 的下标对 (x,y)。

若无解，输出 -1；若存在多个最优排列，输出任意一个即可。

思路

注意到是根据给出的原排列的位置的大小约束确定原排列，很经典的图论建模 + 拓扑排序问题。

先考虑什么时候无解，显然一对约束关系矛盾时无解。如果用一条有向边表示一对位置的偏序关系，显然在图上体现为一个环。

我们可以拓扑排序得到一个可行的解，也就是原排列每个位置的排名，如果无解那么拓扑也可以判断。

再考虑第二个约束：逆序对数量最少。

这意味着我们安排没有确定偏序关系的位置时，越靠前的位置的排名要更靠前。

那我们用小根堆代替拓扑排序的队列即可，这样保证了更小的位置在更早的时候被弹出。

最后我们从 1 开始，按排序后顺序填进每一个位置即可。

不过还有一个细节上的问题，直接根据输入存边会有重边导致拓扑出问题，用一个 set 去重边即可。

设 L = \sum(r_i - l_i)，则复杂度 O(n\log n + L \log L)

代码

const int N = 1e6 + 10;
vector<int> grid[N];
int deg[N];
inline void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n;++i) {
        grid[i].clear();
        deg[i] = 0;
    }
    set<pair<int, int>> st;
    for (int i = 1; i <= m;++i) {
        int l, r; cin >> l >> r;
        int pre; cin >> pre;
        for (int j = l + 1; j <= r;++j) {
            int e; cin >> e;
            st.insert({ pre,e });
            pre = e;
        }
    }
    for (auto& [u, v] : st) grid[u].push_back(v), deg[v]++;
    // 建图
    priority_queue<int, vector<int>, greater<int>> q;
    vector<int> res, ans(n + 1, 0);
    for (int i = 1; i <= n;++i) {
        if (deg[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int cur = q.top();
        q.pop();
        res.push_back(cur);
        for (auto e : grid[cur]) {
            if (--deg[e] == 0) q.push(e);
        }
    }
    // 拓扑
    if (res.size() != n) cout << "-1\n"; // 有环
    else {
        int cur = 1;
        for (auto e : res) {
            ans[e] = cur++;
        }
        for (int i = 1; i <= n;++i) cout << ans[i] << ' ';
        cout << "\n";
    }
}

L - Longest Common Prefix

题意

给出 n 个非空字符串 s_1,s_2,\ldots,s_n，均由小写英文字母组成。

对于 1 ≤ j ≤ i ≤ n，定义 f_{i,j} 为：从前 i 个字符串中恰好选出 j 个，它们的最长公共前缀长度的最大值。特别地，单个字符串的最长公共前缀就是它本身。

对于每个 i=1,2,\ldots,n，求：

\sum_{j=1}^{i}(f_{i,j} \oplus j)

其中 \oplus 表示按位异或。共输出 n 行，第 i 行为对应的答案。

思路

一开始以为是什么神必题，因为看榜的时候过题数处于一个不温不火的状态。

调 A 调的实在没招了仔细看了一下才发现是路边一条，直接踹死了。

我们考虑维护多个串的 LCP 的数据结构，显然只有 Trie 了。（不知道 SAM 能不能做不过还好我不太会）

在 Trie 上，我们会维护每个节点 p 被经过次数 cnt[p] 来解决一些查询问题。

考虑自根开始遍历一段公共前缀 T 至节点 p，cnt[p] 就是截至目前前缀为 T 的串的个数。

再考虑插入一个新串 S 对答案的影响，如果经过节点 p 后，cnt[p] 从 k-1 变成了 k，那么现在就可以选出 k 个串，使它们的 LCP 长度至少为节点 p 的深度，也就是当前处理到的长度。

由于 Trie 的内容就是前 i 个串，f 的第一维就被滚掉了。

我们用 f[j] 维护当前恰好选出 j 个串时，LCP 长度的最大值。

插入到 S 的下标 i 时，在节点 p，令 k = cnt[p]，有：

f[k] = \max(f[k], i + 1)

这样就更新了所有发生变化的 f[j]，因为只有新串经过的节点的 cnt 值会变化，才会对答案产生影响。

最后考虑怎么维护答案：用 sum 维护当前所有 f[j] \oplus j 的和，每次修改 f[k] 时，先减去旧的 f[k] \oplus k，更新后再加上新的 f[k] \oplus k。

还有一个细节，插入第 i 个串时，求和范围会从 [1,i-1] 扩大到 [1,i]。此时 f[i] 还没有被更新过，初值为 0，所以先给 sum 加上 0 \oplus i = i，再正常插入就行。

设所有字符串的长度之和为 S，每个字符只需要走一次 Trie，时间复杂度 O(S)。

代码

const int N = 5e5 + 10;
struct Trie {
    int t[N][65];
    ll cnt[N], f[N];
    ll idx, sum = 0;
    int toint(char x) {
        if (x >= 'A' && x <= 'Z') return x - 'A';
        else if (x >= 'a' && x <= 'z') return x - 'a' + 26;
        else return x - '0' + 52;
    }
    void insert(const string str) {
        int p = 0, len = str.size();
        for (ll i = 0; i < len; i++) {
            int c = toint(str[i]);
            if (!t[p][c]) t[p][c] = ++idx;
            p = t[p][c];
            cnt[p]++;
            sum -= (f[cnt[p]] ^ cnt[p]);
            f[cnt[p]] = max(f[cnt[p]], i + 1);
            sum += (f[cnt[p]] ^ cnt[p]);
        }
    }
} trie;
inline void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n;++i) {
        string s; cin >> s;
        trie.sum += 1ll * i;
        trie.insert(s);
        cout << trie.sum << "\n";
    }
}

A - Recall

题意

有一个初始为空的栈，支持三种操作：

现给出 n 条按原顺序记录的操作，只包含 + x、T x 和 F x，所有出栈操作均被省略。

需要在记录中补入若干出栈操作，使得任意时刻栈内元素两两不同，且所有查询结果与记录一致。

保证有解，构造任意一种合法的操作序列。只需输出由 +、? 和 - 组成的字符串，分别表示入栈、查询和出栈，无需输出操作中的 x。

思路

卡了好多人的难调题。。

考虑当前状态下任意一个合法的后续方案 S。

因为 x 的下一次操作不是 T，所以只有三种情况：

  1. 下一次是 F x：执行询问时 x 必须已经不在栈中；
  2. 下一次是 + x：再次加入 x 以前，旧的 x 必须已经出栈；
  3. 后面不再出现 x：为了最终清空栈，x 仍然必须出栈。

因此，在方案 S 中，x 迟早必须在上述时刻之前被弹出。

基于此，赛时队友贡献了一个做法：对于一个数 x 的先后两次操作 {op1,\ op2}，我们只看：

由于这题的“保证给出的操作序列有解”需要自己判断，再加上猪脑过载，我们觉得只关注这样的一组操作之内的贪心是正确的。

过了 30min 终于构造出了一组反例：

7
+ 1
+ 2
T 1
T 2
+ 4
F 1
T 4

按照我们的思路，会在第六次操作前弹空整个栈，导致最后一次查询结果不对。

然而只要在第四次操作之后就把栈清空，最后一次查询显然就是正确的。

所以，实际上正确的贪心是：

感性的理解：既然栈先进后出，且这个数后面需要出栈，那么不如趁早让它出去，防止对后续加入的数产生影响。

证明：

设 S 第一次弹出 x 的时刻为 t。现在把这次弹栈操作从时刻 t 提前到当前时刻：

于是，从任意合法方案都能交换得到一个“现在立即弹出 x”的合法方案。

因此，这一步贪心是安全的。

实现：预处理每一次操作的下一次操作，再在维护栈中数的下一次操作的同时模拟一下即可。

考虑最后弹空栈的情况，每个数出入栈一次，复杂度 O(n)。

代码

struct node {
    char nxt = '#', op;
    int x;
};
inline void solve() {
    int n; cin >> n;
    vector<node> ops(n + 1);
    map<int, int> pre;

    for (int i = 1; i <= n;++i) {
        char op; int x;
        cin >> op >> x;
        ops[i].op = op; ops[i].x = x;
        if (pre.count(x)) ops[pre[x]].nxt = op;
        pre[x] = i;
    }
    pre.clear();
    stack<int> st; set<int> vis;
    string ans;
    for (int i = 1; i <= n;++i) {
        pre[ops[i].x] = i;
        if (ops[i].op == '+') {
            ans.push_back('+');
            vis.insert(ops[i].x);
            st.push(i);
        } else {
            ans.push_back('?');
        }
        while (!st.empty() && ops[pre[ops[st.top()].x]].nxt != 'T') {
            vis.erase(ops[st.top()].x);
            st.pop();
            ans.push_back('-');
        }
    }
    cout << ans << "\n";
}

D - Sequence

题意

对于一个长度为 n 的 01 序列 s，定义：

p_i=\sum_{j=1}^{i}[s_i \ne s_j]

即 p_i 表示前 i 个元素中与 s_i 不同的元素个数。其中 [\text{条件}] 在条件成立时为 1，否则为 0。

现给出 n 和 p_1,p_2,\ldots,p_n 打乱顺序后得到的多重集合 \{p'_1,p'_2,\ldots,p'_n\}，也就是只知道每个值出现的次数，不知道它对应的位置。

求有多少个不同的 01 序列 s 能产生这个多重集合，答案对 998244353 取模。保证至少存在一个满足条件的序列。

思路

队友赛时最后一小时提供了一个暴搜做法，但剪枝不全 T 了。

感觉这个做法加上剪枝比较直观，所以在此基础上补了。

首先我们需要注意到给出的是 p 的多重集，这意味着顺序是不确定的，不能直接上手递推。

随后考虑到原串是一个 01 串，也就是说 p 的值实际上只会是前面的 0 的个数或者 1 的个数。

我们可以想到模拟填 0/1，并在此基础上维护 p，继续搜索可以在当前位置填入合法 p 值的分支

可以以此为状态写一个暴搜：

设当前填到了第 pos 个位置，前面 01 中更多的数的个数为 mx，更少的数的个数为 mn，有：

这样很直观，但是会 T，需要考虑剪枝。

考虑每次填完一个数对 mx 和 mn 的影响，可以注意到每次的结果都会有 mn' \ge mn；

那么每个分枝都需要保证剩余的集合中不会有 < mn 的待选数；

这样加一条剪枝就过了，但是为什么？

实际上，当 mx \neq mn 且集合中 mx，mn 均存在时：

所以：

因此，任意时候这份暴搜只有一个分支，复杂度是 O(n) 的。

不过递归写法看起来很直观，不也挺好的吗。

代码

int n;
multiset<int> f;
ll dfs(int pos, int mx, int mn) {
    if (pos == n + 1) return 1;
    if (*f.begin() < mn) return 0;
    if (mx < mn)swap(mx, mn);
    ll ans = 0;
    auto it1 = f.find(mx);
    auto it2 = f.find(mn);
    if (mx == mn && it1 != f.end()) {
        f.erase(it1);
        ans += 2ll * dfs(pos + 1, mx + 1, mn);
        f.insert(mx);
        ans %= mod;
    } else {
        if (it1 != f.end()) {
            f.erase(it1);
            ans += dfs(pos + 1, mx, mn + 1);
            f.insert(mx);
        }
        if (it2 != f.end()) {
            f.erase(it2);
            ans += dfs(pos + 1, mx + 1, mn);
            f.insert(mn);
        }
    }
    return ans % mod;
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n;++i) {
        int e; cin >> e; f.insert(e);
    }
    cout << dfs(1, 0, 0);
}

N - Red Sequence

题意

给出一个长度为 n 的序列，每个位置放有 1 到 3 枚棋子，颜色为红、黄、蓝中的若干种，同一位置不会有两枚相同颜色的棋子。

第 i 个位置用三个数 r_i,y_i,b_i 描述，分别表示该位置是否有红、黄、蓝色棋子，1 表示有，0 表示没有。

需要将整个序列划分为若干个连续段。若一个段内红色棋子的数量不少于黄色棋子的数量，且不少于蓝色棋子的数量，则称这一段为红色段。即对于区间 [l,r]，需要满足：

\sum_{i=l}^{r}r_i \ge \max\left(\sum_{i=l}^{r}y_i,\sum_{i=l}^{r}b_i\right)

求划分后所有红色段的长度之和的最大值。段的长度指它包含的位置数，即 r-l+1。

思路

CDQ 分治 + DP

首先贪心显然是不对的，因为本质是一个从合法单点开始的区间拓展问题，无法确定往左还是往右更优。

考虑 DP，设 dp[i] 为 [1,i] 的最长长度，那要么不选当前点，要么接上上一段合法红色段，则有：

dp[i] = \max(dp[i-1],\ dp[j] + i - j)

但是考虑到约束，不是任意连接的，需要满足：

整理一下：

可以发现是个三维偏序问题，考虑 CDQ 分治；

先预处理一下三个前缀和，然后以三维偏序存点的模式存储一下每个下标的信息；

这里由于前缀和之差值的域是 [-10^6, \ 10^6]，需要加上 10^6 才能用最大值树状数组维护；

第三维因为是下标已经有序，只存剩下两维，直接跑 CDQ 板子就行了。

注意优化 dp 时，先处理左半部分，再计算左边向右边的贡献，再计算右半部分；

同时，由于递推式 dp[i] = \max(dp[i-1],\ dp[j] + i - j)；

对于右半部分的每个下标 j，需要先更新 dp[j] = \max(dp[j], dp[j - 1])。

复杂度 O(n \log ^ 2 n)，卡的有点死，不知道场上能不能过，QOJ 可以过。

代码

struct node {
    ll b, c, id;
};
struct BIT {
    int n;
    ll c[N];
    int lowbit(int x) { return x & -x; }
    void init(int _n) {
        n = _n;
        for (int i = 0; i <= n; i++) {
            c[i] = -inf32;
        }
    }
    void update(int x, ll k) {
        while (x <= n) {
            c[x] = max(c[x], k);
            x += lowbit(x);
        }
    }
    void clear(int x) {
        while (x <= n) {
            c[x] = -inf32;
            x += lowbit(x);
        }
    }
    ll query(int x) {
        ll res = -inf32;
        while (x > 0) {
            res = max(res, c[x]);
            x -= lowbit(x);
        }
        return res;
    }
} bit;
ll dp[N];
void CDQ(int l, int r, const vector<node>& ori) {
    if (l == r)return;
    int mid = (l + r) >> 1;
    CDQ(l, mid, ori);
    vector<node> L(ori.begin() + l, ori.begin() + 1 + mid);
    vector<node> R(ori.begin() + mid + 1, ori.begin() + 1 + r);
    sort(L.begin(), L.end(), [&](const node& A, const node& B) {
        if (A.b != B.b)return A.b < B.b;
        return A.c < B.c;
        });
    sort(R.begin(), R.end(), [&](const node& A, const node& B) {
        if (A.b != B.b)return A.b < B.b;
        return A.c < B.c;
        });
    int i = 0;
    for (int j = 0; j < R.size();++j) {
        //dp[R[j].id] = max(dp[R[j].id], dp[dp[R[j].id] - 1]);
        while (i < L.size() && L[i].b <= R[j].b) {
            bit.update(L[i].c, dp[L[i].id] - L[i].id);
            i++;
        }
        dp[R[j].id] = max(dp[R[j].id], bit.query(R[j].c) + R[j].id);
    }
    for (int j = 0; j < i;++j) bit.clear(L[j].c);
    for (int j = mid + 1; j <= r;++j) dp[j] = max(dp[j], dp[j - 1]);
    CDQ(mid + 1, r, ori);
    return;
}
inline void solve() {
    int n; cin >> n;
    vector<ll> psR(n + 1, 0), psY(n + 1, 0), psB(n + 1, 0);
    for (int i = 1; i <= n;++i) {
        int a, b, c;
        cin >> a >> b >> c;
        dp[i] = -inf32;
        psR[i] = psR[i - 1] + a;
        psY[i] = psY[i - 1] + b;
        psB[i] = psB[i - 1] + c;
    }
    vector<node> a(n + 1);

    ll div = 1e6;
    bit.init(2 * div + 1);
    a[0].b = div; a[0].c = div;a[0].id = 0;
    for (int i = 1; i <= n;++i) {
        a[i].b = psR[i] - psY[i] + div;
        a[i].c = psR[i] - psB[i] + div;
        a[i].id = i;
    }
    dp[0] = 0;
    CDQ(0, n, a);
    cout << dp[n];
}