CF2164（Global Round 30）全解

· · 个人记录

试着搓一套新的难度玩。

Grok 居然能自己爬整场题并翻译了，好评。不过开长考翻译质量较差，建议开快速再让它重译一遍，顺便处理各种 markdown 锅。

本文中的题意纯手翻，没用 Grok，因为它复制 markdown 时公式没用美元符号。

更新日志：

A. Sequence Game

题意

给定长度为 n 的序列 a，每次操作选择一个 1\le i< n，并将 a_i 与 a_{i+1} 删去，替换成 [a_i,a_{i+1}] 内任一整数（具体多少你自己定）。

求 n-1 次操作后剩下的那个数是否可能为 x。

数据范围：多测，T\le 500，n\le 100，a_i\le 10^9。

做法

显然可以通过不断操作与最值相邻的值来最大化最后一次操作的取值范围。

所以最终 x\in[\min\{a_i\},\max\{a_i\}] 则符合条件，求数组最大值和最小值即可。

:::success[代码]

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define lf double
#define ld long double
using namespace std;
ll T,n,a,mx,mn;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>a;
        n--;
        mx=a;
        mn=a;
        while(n--){
            cin>>a;
            mx=max(mx,a);
            mn=min(mn,a);
        }
        cin>>a;
        if(a<=mx&&a>=mn){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
    return 0;
}

:::

B. Even Modulo Pair

题意

给定长度为 n 的严格单调递增序列 a，求是否存在一对 (x,y)，使得：

如果存在，给出任意一对。

数据范围：多测，\sum n\le 10^5，a_i\le 10^9。

做法

需要注意力。真注意不到。

若无解，

发现 V 只有 10^9，去重后取前 40 个（若不足则取全部）暴力枚举即可。

:::success[代码]

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define lf double
#define ld long double
using namespace std;
ll T,n,a[200010];
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        n=min(n,40ll);
        bool flg=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[j]%a[i]%2==0){
                    cout<<a[i]<<' '<<a[j]<<endl;
                    flg=1;
                    break;
                }
            }
            if(flg){
                break;
            }
        }
        if(!flg){
            cout<<-1<<endl;
        }
    }
    return 0;
}

:::

C. Dungeon

题意

有 n 把剑，m 个怪，剑有攻击力 a_i，怪有防御力 b_j。剑 i 能杀死怪 j 当且仅当 a_i\ge b_j。

怪分两类：

一个怪只能打一次，求最多能打死多少怪。

数据范围：多测，\sum n,\sum m\le 2\times10^5，a_i,b_i,c_i\le 10^9。

做法

显然要先打能爆装备的怪。而为了尽量使剑增强，每个这种怪都应该用尽量烂的剑去打。为了防止有怪不强化就打不死的情况打的时候按 b_i 排个序。这可以用 multiset 维护，不会写也可以上树。

然后对于不爆装备的就枚举每个怪找最菜的剑打就行，顺序随意因为反正我每次用的是最菜的剑，打谁都一样。

:::success[代码] 关于 set 和 multiset 的基本操作：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define lf double
#define ld long double
using namespace std;
struct node{
    ll b,c;
};
bool operator <(node x,node y){
    return x.b==y.b?x.c>y.c:x.b<y.b;
}
ll T,n,m,u,b[200010],p1,p0,ans;
multiset<ll> s;
node c[200010];
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        s.clear();p0=p1=ans=0;
        for(int i=0;i<n;i++){
            cin>>u;
            s.insert(u);
        }
        for(int i=0;i<m;i++){
            cin>>b[i];
        }
        for(int i=0;i<m;i++){
            cin>>u;
            if(u){
                c[p1].b=b[i];
                c[p1++].c=u;
            }
            else{
                b[p0++]=b[i];
            }
        }
        sort(b,b+p0);
        sort(c,c+p1);
        for(int i=0;i<p1;i++){
            set<ll>::iterator p=s.lower_bound(c[i].b);
            if(p==s.end()){
                break;
            }
            ans++;
            ll tmp=(*p);
            s.erase(p);
            s.insert(max(tmp,c[i].c));
        }
        for(int i=0;i<p0;i++){
            set<ll>::iterator p=s.lower_bound(b[i]);
            if(p==s.end()){
                break;
            }
            ans++;
            s.erase(p);
        }
        cout<<ans<<endl;
    }
    return 0;
}

:::

D. Copy String

题意

给定字符串 s,t，令 s_0=s，你可以进行若干次操作，第 i 次操作得到 s_i，其中 s_{i,j} 可以从 s_{i-1,j} 和 s_{i-1,j-1} 中选一个（j=1 时显然不能选后者）。

试问能否用不超过 k_{\max} 次操作使得最后一次操作得到的 s_k=t，如果可以，求出最小的 k 并给出一组构造方案。

数据范围：多测，\sum nk_{\max}\le 10^6。

做法

容易想到一种直接匹配的方法：枚举 s_i 并维护指针 p 使其与 t 中各项匹配并记录每个 i 匹配到的 p（记作 r_i），这个过程中如果枚举到某个 i 时 p<i 则匹配失败（依照题意字符只能往右移动），匹配成功后若 \max\{r_i-i\}>k_{\max} 仍视为匹配失败，否则操作次数即为 \max\{r_i-i\}，依题意模拟即可。

但是这个东西跑样例 #5 会输出 -1。

10 3
vzvylxxmsy
vvvvvllxxx

原因是 t[0,4] 全部匹配给了 s_0。

所以上述方法求出来的方案不是最优的。

于是考虑当当前 r_i-i=k_{\max} 时强行结束 s_i 的匹配。

然后会发现我把 k_{\max} 开大点它又炸了。

然后发现他是放 nk_{\max} 过的，所以直接从小到大枚举操作次数，然后用上上面强行结束匹配的思路，匹配完输出答案之前再确定一遍是否能够到达最终状态（有时只判 p<i 判不掉一些情况）即可。复杂度 O(nk_{\max})。

:::success[代码]

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<cassert>
#define ll long long
#define lf double
#define ld long double
using namespace std;
ll T,n,k,l[1000010],r[1000010],lst[30];
string s,t;
bool work(ll now){
    ll p=0;
    bool flg=0;
    memset(lst,-1,sizeof(lst));
    for(int i=0;i<n;i++){
        if(p<i){
            flg=1;
            break;
        }
        l[i]=p;
        while(p<n&&t[p]==s[i]){
            if(p-1-i==now)break;
            p++;
        }
        r[i]=p-1;
    }
    if(flg){
        return false;
    }
    string tmp=s;
    for(int i=1;i<=now;i++){
        for(int j=0;j<n;j++){
            if(j+i<=r[j]){
                tmp[j+i]=s[j];
            }
        }
    }
    if(tmp!=t){
        return false;
    }
    cout<<now<<endl;
    tmp=s;
    for(int i=1;i<=now;i++){
        for(int j=0;j<n;j++){
            if(j+i<=r[j]){
                tmp[j+i]=s[j];
            }
        }
        cout<<tmp<<endl;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>k>>s>>t;
        bool flg=0;
        for(int i=0;i<=k;i++){
            if(work(i)){
                flg=1;
                break;
            }
        }
        if(!flg){
            cout<<-1<<endl;
        }
    }
    return 0;
}

:::

E. Journey

题意

给定 n 个点 m 条边的无向连通图，边有边权。你初始在 1 号点，每次可以选下面中的一种操作：

  1. 选择一条与当前位置相连的边，走到边的另一端并标记该边，代价为该边边权。
  2. 选择一条以当前位置为起点的路径（点和边都可以重复走），走到路径的另一端，代价为路径上编号最大的边的边权。

求标记所有边并回到 1 的最小代价。

数据范围：多测，\sum n,\sum m\le 10^6，1\le w_i\le 10^9。不保证图是简单图。

做法

官解评论区里有一个赛时自己发明出重构树的选手写的题解中算法过程比较清楚，对重构树不熟的同学可以参考。

当图有欧拉回路的时候显然可以只走一操作。

对于没有欧拉回路的情况，我们需要为度数为奇的点间进行连边使得每个点度数都变成偶数。新加入的边 (u,v) 的权值显然是通过二操作从 u 到达 v 的最小代价。

而从 u 到达 v 的代价是与路径上点的编号的瓶颈值相关的。所以对于简单路径，这其实也可以视为一种图上多次询问路径最小瓶颈的问题，使用 Kruskal 重构树（此时显然要以编号的顺序添加边）即可解决。

但二操作中允许绕路。所以除了简单路径上的必经边之外，也许可以通过绕路到一些下标更大但权值更小的边来减小代价。

这种情况下，由于每次添加的边都是下标尽量小的，所以重构树上 \text{LCA}(u,v) 到根节点路径上的各个点其实都可以是从 u 至 v 二操作的代价。所以在建出重构树之后我们可以从根节点进行一次 DFS 求出每个点到根节点路径上的最小值。

而从根往叶子走的过程中这个值显然是单调不升的，所以我们应该找尽可能深的、子树内含有两个或以上原图中奇度数点的重构树上的点并在这个时刻进行连边。

这样最终的复杂度就是 O(n\log n) 或者 O(n\alpha(n))，视并查集实现而定。

F. Chain Prefix Rank

鉴于笔者也没学过这种高科技，本题解简述广义串并联图的基础，所以不用担心看不懂。

题意

给定一棵 n 个点的树和一个长度为 n 的数组 a，求有多少长度为 n 的排列 p，满足对于每个 u 恰有 a_u 个祖先 v 使得 p_v<p_u。答案对 998244353 取模。

数据范围：

做法

看了无数篇 blog，所以没法列举出处了，因为我也不知道我在默写哪篇。如果你发现我大篇幅默了某篇你可以来找我。

这里讲官解做法。

我们引入广义串并联图的概念。

广义串并联图基础

定义

如果一个无向图中不存在四个点，使得这四个点间两两有路径相连，且路径间互不相交，则这个图被称为广义串并联图。树和仙人掌是常见的广义串并联图。

构造

性质与判定

口诀：删一缩二并重边。

即广义串并联图可以经过若干次下面三种操作变成一个点：

上述性质也可以用于判定。

上述性质中，由于这些操作通常容易合并信息，我们在操作的过程中可以在点上和边上维护信息以方便地进行统计。

更一般地，对于点数和边数相差较小的图，对其也进行上面的操作直至无法操作，可以将其剩余的点数和边数缩到可以暴力的范围，这种方法叫广义串并联图方法。设 m-n=k，则最终得到的图有 n\le 2k,m\le 3k。

本题

首先 a_i 实质上就是 i 在其到根路径上的 rank。

所以为了找到排列我们可以考虑从根向下不断地在当前路径上插入点。我们建一张表示这个关系的图，为了确保每个点都能插入，我们在 1 的上方建立点 n+1，在 n+1 的上方建立点 0，则此时初始的图就是一个 0\to n+1 的边。插入点 1 时，增加 0\to 1 和 1\to n+1 的边，以此类推。

这样得到的图视为无向图后显然是一个广义串并联图（因为插入的点可以“缩二度点”后“合并重边”来删掉），题目要求其拓扑序个数。很多题解里这里直接给的总式子，我简单展开一下。我们在边上维护信息，下设 f_{x,y} 为边 (x,y) 中包含的方案数，sz_{x,y} 为边 (x,y) 中包含的点数。

上述过程暴力实现是 n^2 的，平衡树维护一下前驱后继可以 1\log。

G. Pointless Machine

题意

交互题。给定 n，交互库有一棵 n 个点的树，每次询问时可以给出由所有点组成的排列，交互库会返回该排列各前缀导出子图的边数。交互库一次性回答所有询问。你需要通过不超过 31 次询问得到这棵树。

数据范围：多测，\sum n\le 5\times10^4。

做法

字母疑似和现有题解的做法一样，但我使用它们是因为 jiangly 讲这题的时候使用了。

首先 1\sim n 问一遍，n\sim 1 问一遍，得到各点度数。

看上去询问次数的限制在提示我们按位考虑。考虑对于每个二进制位求出每个点向各编号点的连边数，将点分成这一位为 0 的和为 1 的两个序列 s_0,s_1，然后分别询问 s_0+s_1 和 s_1+s_0（保持序列内顺序不变，这样才能相减），对结果进行差分，这样对于每一位我就知道了每个点连向该位上为 0/1 的边的数量。然后由于我们已经知道各点度数了所以可以不断剥叶子（叶子只连一个点显然连的谁就确定了）。于是就做完了。

由于 1\sim n 可以视为一组 s_0,s_1，故操作次数 2\lceil\log n\rceil+1，上界为 33，难以通过。

本题的一个坑点就在于，此时很容易去想如何实现 2(\lceil\log n\rceil-1)+1。如果你这么想基本上就完蛋了。

jls 的做题经验告诉我们，形如 a\lceil\log_a n\rceil 的式子在 a=e 时取到最小值，所以通常取 2 就足矣，但个别题就是要卡你去取 3。

一算，3^{10}=59049，完美卡满。也就是按三进制位考虑，分成 s_0,s_1,s_2 三组并分别询问 s_0+s_1+s_2,s_1+s_2+s_0,s_2+s_0+s_1 即可按类似的方式得到结果。这就是杭二学生出题的素质？

H. PalindromePalindrome

注意：本题解并不讲解如何证明最终复杂度是 1\log，相反，这里试图 hack 题解中关于复杂度的证明。不过反正开了 5 秒 2log 也照过不误管他呢

题意

定义一个字符串的幽默度为其中出现至少两次的最长的回文串的长度。

给定长度为 n 的字符串 s 及 q 次询问，每次询问 s 的一段子串的幽默度。

数据范围：n,q\le5\times10^5。

做法

官解翻译出锅催更暂无果，差评更了，虽然还是有锅。将部分正确的官解和各个资料拼着看得到了下述内容。

考虑回文子串两次出现位置的关系。显然可以简单地分为相交和不相交。

两次出现范围相交

好在新版官解的这部分改对了。

设两次出现的区间分别是 [l_1,r_1] 和 [l_2,r_2]，则有 l_1<l_2\le r_1<r_2，又因为 [l_1,r_1] 和 [l_2,r_2] 是回文的，所以 [l_1,r_2] 也必然是回文的。所以这里我们只需要对每个回文的 [l_1,r_2] 找到其最大的边界即可。考虑设 S[l,l'] 为以 l 开头的最长前缀，S[r',r] 为以 r 结尾的最长后缀，则只有下面三种情况是做贡献的：

  1. 回文中心在 S[l,l'] 和 S[r',r] 的回文中心（取边界）之间的所有回文子串。

第一条可以马拉车预处理，后两条可以上 PAM 找祖先，查询的时候直接上线段树即可。

两次出现范围不相交

对于这种情况，考虑以 r 结尾的所有回文后缀。令 B=\overline{AC}，其中 A,C 为回文串，记 B^k=\overline{\begin{matrix}\underbrace{BBB\dots B}\\k\ \text{个}\ B\end{matrix}}，则上述所有后缀均可以表示成 B^kA(k\in\mathbb{N}) 的形式。所以，对于两个后缀 S_1,S_2，若 \dfrac{|S_2|}{2}<|S_1|<|S_2|，则 S_1 在 S_2 中必然会相交地出现至少两次，这会被第一种情况计算。所以实际有效的串的个数只有 O(n\log n) 级别。

我们在构建 PAM 时预处理出每个串的长度不超过其一半的最长回文后缀，每次跳这个后缀就可以只遍历我们需要的串了。查询还是上线段树即可。

总复杂度 O((n+q)\log^2 n)。

下面的内容要感谢机房一位 Ag 爷愿意听我这个一等线上的小蒟蒻提问并和我探讨此题。

官解试图采用 runs 说明实际有效的串为 O(n) 个，但我们可以构造形如 S_i=\text{lowbit}(i) 的字符串：

\mathtt{abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba}\dots

这根本不适用 runs，因为它就没有出现两次的周期。而且它应该有 n\log n 个需要考虑的字串。