2021 沈阳补题记录（9 / 13）

发表于 2022-07-07 更新于 2024-07-21 分类于区域赛本文字数： 14k 阅读时长 ≈ 13 分钟

2021 沈阳补题记录与部分题目题解（待补…）

这场没有打， vp 时候给的感觉就是基础知识 + 思维能力的欠缺。

B. Bitwise Exclusive-OR Sequence

题意

给定 $n$ 个数， $m$ 个限制，每一个限制包含 $3$ 个数 $u, v, w$ ，表示 $a_u \bigoplus a_v = w$ ，求满足所有限制情况下 $\sum\limits_{i=1}^{n} a_i$ 的最小值。
其中 $1 \leq n \leq 10^5, 0 \leq m \leq 2 \cdot 10^5, 1 \leq u, v \leq n, 0 \leq w < 2^{30}$ 。

思路

考虑到异或操作不难想到将二进制每一位拆开来考虑。
对于某一位，期限制可以转换为 $a_u = a_v$ 与 $a_u \neq a_v$ ，考虑可以用一个带权并查集来维护数之间的关系，这里用 $n \cdot 2$ 个并查集来实现，最后取并查集中较大的部分将这一位赋为 $0$ 即可。
总复杂度为 $O(30 \cdot (n + m))$ 。

代码

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

using ll=long long;

constexpr int N=1e5+5;

int n,m;
int u[N*2],v[N*2],w[N*2];
int fa[N*2],sz[2][N*2];
ll ans;

int get(int a){
    if(fa[a]==a) return a;
    return fa[a]=get(fa[a]);
}

void merge(int a,int b){
    int r1=get(a),
        r2=get(b);
    if(r1==r2) return;
    sz[0][r2]+=sz[0][r1];
    sz[1][r2]+=sz[1][r1];
    fa[r1]=r2;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i];
    for(int j=30;j>=0;j--){
        iota(fa+1,fa+1+n*2,1);
        for(int i=1;i<=n;i++){
            sz[0][i]=1,sz[1][i]=0;
            sz[0][i+n]=0,sz[1][i+n]=1;
        }
        for(int i=1;i<=m;i++){
            if((w[i]>>j)&1){
                if(get(u[i])==get(v[i])){
                    cout<<"-1";
                    return true&&false;
                }
                merge(u[i],v[i]+n);
                merge(u[i]+n,v[i]);
            }
            else{
                if(get(u[i])==get(v[i]+n)){
                    cout<<"-1";
                    return true&&false;
                }
                merge(u[i],v[i]);
                merge(u[i]+n,v[i]+n);
            }
        }
        ll sum=0;
        for(int i=1;i<=n*2;i++) if(get(i)==i) sum+=min(sz[0][get(i)],sz[1][get(i)])*(1ll<<j);
        ans+=sum/2;
    }
    cout<<ans;

    return true&&false;
}

E. Edward Gaming, the Champion

题意

找给定小写字符串 $s$ 里有多少个 $edgnb$ 。
其中 $1 \leq |s| \leq 2 \cdot 10^5$ 。

思路

找即可。

代码

略。

F. Encoded Strings I

题意

给定长为 $n$ 包含前 $20$ 个小写字符的串 $s$ 。定义一种字符串 $t$ 的加密方式为：假设字符 $c$ 在 $t$ 中最后一次出现的位置为 $p$ ， $p$ 之后有 $k$ 种小写字符，则将 $c$ 替换为第 $k + 1$ 个小写字符，要求加密串 $s$ 。
其中 $1 \leq n \leq 10^3$ 。

思路

模拟即可。

代码

略。

G. Encoded Strings II

题意

给定长为 $n$ 的只含前 $20$ 个小写字母的字符串 $s$ ，采用 $F$ 题的加密方式，求 $s$ 的所有子序列中，加密后字典序最大的加密子序列。
其中 $1 \leq n \leq 10^3$ 。

思路

观察一下可以得到：

最后结果中所有在 $s$ 中出现过的字母都至少出现过一次，否则将其加入一定可以有方法使子序列中的首字母变大。
最后的结果一定是若干段连续相同的字母组成，否则若存在 $..A..B..last(A)..last(B)..$ 的结构， $A$ 的字典序一定大于 $B$ ，可以交换 $A, B$ 得到 $..A..last(A)..B..last(B)..$ ，结果一定更优。

所以可以预处理出 $g[mask]$ 表示最大的位置使得往后能全部取到集合 $mask$ 包含的字母，前缀和预处理复杂度为 $O(n + 2^m)$ ， $m$ 为 $s$ 中的字符集大小。
取字母可以贪心地往后取，记 $dp[mask]$ 表示取了 $mask$ 包含的字母并且结果字典序最大时子序列结尾的最小位置，转移时将mask按照popcount从小到大分为若干层，层之间转移只取这一段能取到的最多的字母进行转移，输出结果类似输出背包方案从终态倒着走回去即可。
复杂度 $O(m \cdot 2^m)$ ， $m$ 为 $s$ 中的字符集大小。

代码

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

using i64=long long;

const int N=1e3+5;

int n;
char s[N];
int sum[N][20];
int dp[1<<20],g[1<<20],all;
vector<int> pos[20],state[21];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    cin>>s+1;

    for(int i=0;i<(1<<20);i++){
        g[i]=n+1;
        int cnt=__builtin_popcount(i);
        state[cnt].push_back(i);
    }
    for(int i=1;i<=n;i++){
        int w=s[i]-'a';
        g[1<<w]=i;
        sum[i][w]++;
        for(int j=0;j<20;j++) sum[i][j]+=sum[i-1][j];
        pos[w].push_back(i);
        all|=(1<<w);
    }
    for(int j=0;j<20;j++) sum[n+1][j]+=sum[n][j];
    for(int i=0;i<20;i++)
        for(int mask=1;mask<(1<<20);mask++) if((mask>>i)&1) g[mask]=min(g[mask],g[mask^(1<<i)]);
    
    for(int i=0;i<(1<<20);i++) dp[i]=n+1;
    dp[0]=0;
    for(int cnt=1;cnt<=20;cnt++){
        int maxn=0;
        for(auto mask:state[cnt]){
            if((all&mask)!=mask) continue;
            for(int w=0;w<20;w++) if((mask>>w)&1) maxn=max(maxn,sum[g[all^mask]-1][w]-sum[dp[mask^(1<<w)]][w]);
        }
        if(maxn==0) continue;
        for(auto mask:state[cnt])
            for(int w=0;w<20;w++) if(((mask>>w)&1)&&sum[g[all^mask]-1][w]-sum[dp[mask^(1<<w)]][w]==maxn){
                int p=lower_bound(pos[w].begin(),pos[w].end(),g[all^mask])-pos[w].begin();
                dp[mask]=min(dp[mask],pos[w][p-1]);
            }
    }

    string ans="";
    int now=all,cnt=0;
    while(now){
        int maxn=0;
        for(int w=0;w<20;w++) if((now>>w)&1) maxn=max(maxn,sum[dp[now]][w]-sum[dp[now^(1<<w)]][w]);
        for(int w=0;w<20;w++) if(((now>>w)&1)&&sum[dp[now]][w]-sum[dp[now^(1<<w)]][w]==maxn){
            for(int i=0;i<maxn;i++) ans+=(char)('a'+cnt);
            now^=(1<<w);
            cnt++;
            break;
        }
    }
    reverse(ans.begin(),ans.end());

    cout<<ans;

    return true&&false;
}

H. Line Graph Matching

题意

给定一张 $n$ 个点， $m$ 条边的带权无向连通图，定义它的线图为 $\rightarrow$ 原图边变点，点变边之后形成的图，形成的图的点权为原图的边权，线图的一条边的边权为它的两个端点的点权之和。求线图的最大带权匹配的权值。
其中 $1 \leq n \leq 10^5, n - 1 \leq m \leq \min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5)$ 。

思路

不难发现，线图中的一对匹配对应原图中就是取有公共端点的两条边进行匹配。
只考虑树上的情况时，不难发现当边的数量为偶数时，所有的边一定都能被匹配完，从叶子开始贪心地匹配即可；若边的数量为奇数，则一定会剩下恰好一条边没有被匹配，而这条边可以被剩下的条件是除去它后剩下来的两个连通块中包含的边数一定都是偶数，因此枚举每一条边判断即可。
若考虑是图上的情况，可以将原图看成一棵 $dfs$ 树加上若干条返祖边，若边的数量是偶数，类似树上的情况做一个贪心的匹配即可，所有的边一定能被匹配完；若边的数量是奇数，则一定会剩下恰好一条边，这条边的被剩下的条件是这条边不是原图的割边或者将它除去后原图分裂为两个包含偶数条边的连通块，枚举这条边即可。
找割边加判断的总复杂度为 $O(n)$ 。

代码

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

using ll=long long;

constexpr int N=1e5+5;

vector<array<int,4>> e[N];
array<int,3> edge[N*2];
int n,m;
int dfn[N],low[N],del[N*2],dfs_clock;
int cnt[N*2],sz[N];

void dfs(int x,int fa){
    dfn[x]=low[x]=++dfs_clock;
    for(auto [u,v,w,id]:e[x]){
        if(v==fa) continue;
        if(!dfn[v]){
            dfs(v,u);
            sz[u]+=sz[v]+1;
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                del[id]=1;
                cnt[id]=sz[v];
            }
        }
        else{
            sz[v]++;
            low[u]=min(low[u],dfn[v]);
        }
    }
    return;
}

void find_bridge(int n){
    dfs_clock=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(del,0,sizeof(del));
    for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        e[edge[i][0]].push_back({edge[i][0],edge[i][1],edge[i][2],i});
        e[edge[i][1]].push_back({edge[i][1],edge[i][0],edge[i][2],i});
    }
    if(m%2==0){
        ll ans=0;
        for(int i=1;i<=m;i++) ans+=edge[i][2];
        cout<<ans;
    }
    else{
        find_bridge(n);
        ll ans=-0x3f3f3f3f3f3f3f3f;
        for(int i=1;i<=m;i++){
            if(!del[i]) ans=max(ans,-1ll*edge[i][2]);
            else if(del[i]&&cnt[i]%2==0) ans=max(ans,-1ll*edge[i][2]);
        }
        for(int i=1;i<=m;i++) ans+=edge[i][2];
        cout<<ans;
    }

    return true&&false;
}

I. Linear Fractional Transformation

数学

题意

待补

思路

待补

代码

待补

J. Luggage Lock

题意

给定两个长度为 $4$ 的数字串 $a, b$ ，每次操作可以将 $a$ 中连续一段数字同时加 $1$ 或减 $1$ （模 $10$ 意义下），求最少多少次操作可以将 $a$ 变成 $b$ 。
其中包含 $t$ 组数据， $1 \leq t \leq 10^5$ 。

思路

每次操作只涉及一段区间的加减，显然我的操作只和 $a, b$ 每一位上的差值有关。可以 $bfs$ 预处理出 $0000$ 到 $[0001, 9999]$ 的所有距离，输出 $a, b$ 每一位相减构成的数对应的距离即可。

代码

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

constexpr int N=1e5+5;
int _=1;

string s,t;
int dis[N];

int calc(array<int,4> &arr){
    int res=0;
    res=arr[0]*1000+arr[1]*100+arr[2]*10+arr[3];
    return res;
}

void init(){
    memset(dis,0x3f,sizeof(dis));
    queue<array<int,4>> q;
    dis[0]=0;
    q.push({0,0,0,0});
    while(!q.empty()){
        array<int,4> u=q.front();
        q.pop();
        for(int l=0;l<=3;l++)
            for(int r=l;r<=3;r++)
                for(int i=1;i<=9;i++){
                    array<int,4> v=u;
                    for(int j=l;j<=r;j++) v[j]=(v[j]+i)%10;
                    if(dis[calc(v)]>dis[calc(u)]+min(i,10-i)){
                        dis[calc(v)]=dis[calc(u)]+min(i,10-i);
                        q.push(v);
                    }
                }
    }
}

void work(){
    cin>>s>>t;
    array<int,4> arr;
    for(int i=0;i<4;i++) arr[i]=((t[i]-'0')-(s[i]-'0')+10)%10;
    cout<<dis[calc(arr)]<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    init();

    cin>>_;
    while(_--){
        work();
    }

    return true&&false;
}

L. Perfect Matchings

题意

给定一张 $n \cdot 2$ 个点的完全图，从图中去掉恰好 $n \cdot 2 - 1$ 条边，且这 $n \cdot 2 - 1$ 条边恰好构成一棵树，求去边之后的图的完美匹配数。
其中 $1 \leq n \leq 2 \cdot 10^3$ 。

思路

题意不难理解成：计算完全图中不包含任何一条树边的完美匹配数。
“不包含任何一条边”，容易想到容斥，设 $F(S)$ 为指定 $S$ 条树边匹配，剩余点任意匹配的方案数，那么容斥（也可以看成特殊情况下的二项式反演）可以得到最后的答案 $ans = \sum\limits_{S=0}^{n} F(S) \cdot (-1)^{|S|}$ 。
对于 $F(S)$ 的计算，等于选定 $S$ 条互不相交的树边的方案数 $G(S)$ 乘上剩余点任意匹配的方案数 $H(S)$ ， $G(S)$ 可以一次树 DP 处理出来， $H(S)$ 可以 $O(n)$ 地处理出来。最后计算即可。
其中树 DP 的复杂度为 $O(n^2)$ 而不是 $O(n^3)$ ，因为考虑每两个点只会在他们的 $lca$ 处被合并一次。总复杂度为 $O(n^2)$ 。

代码

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

using ll=long long;

constexpr ll mod=998244353;
constexpr int N=2e3+5;

vector<int> e[N*2];
int n;
int sz[N*2];
ll res[N];
ll dp[N*2][N*2][2],g[N*2][2],ans;

void dfs(int x,int fa){
    dp[x][0][0]=1;
    for(auto v:e[x]){
        if(v==fa) continue;
        dfs(v,x);
        for(int i=0;i<=sz[x]+sz[v]+1;i++) g[i][0]=g[i][1]=0;
        for(int i=0;i<=sz[x];i++)
            for(int j=0;j<=sz[v];j++){
                g[i+j][0]+=dp[x][i][0]*(dp[v][j][0]+dp[v][j][1])%mod;
                g[i+j][0]%=mod;
                g[i+j][1]+=dp[x][i][1]*(dp[v][j][0]+dp[v][j][1])%mod;
                g[i+j][1]%=mod;
                g[i+j+1][1]+=dp[x][i][0]*dp[v][j][0]%mod;
                g[i+j+1][1]%=mod;
            }
        sz[x]+=sz[v]+1;
        for(int i=0;i<=sz[x];i++){
            dp[x][i][0]=g[i][0];
            dp[x][i][1]=g[i][1];
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    res[0]=1;
    for(int i=1;i<N;i++) res[i]=res[i-1]*(i*2-1)%mod;

    cin>>n;
    for(int i=1,x,y;i<n*2;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,1);
    for(int i=0;i<=n;i++) dp[1][i][0]=(dp[1][i][0]+dp[1][i][1])%mod;
    for(int i=0;i<=n;i++){
        if(i&1) ans=(ans+mod-dp[1][i][0]*res[n-i]%mod)%mod;
        else ans=(ans+dp[1][i][0]*res[n-i]%mod)%mod;
    }
    cout<<ans;

    return true&&false;
}

M. String Problem

题意

给定小写字符串 $s$ ，对 $s$ 的每个前缀 $prefix_i$ ，求 $prefix_i$ 字典序最大的子串，若有多个求最左的，输出子串的起终点。
其中 $1 \leq |s| \leq 10^6$ 。

思路

解法很多。

$sam$ 的做法。
显然字典序最大的子串对应于一条 $sam$ 上的路径。对每个前缀，我们记录当前前缀中字典序最大的子串所在路径上的点并在这些点上打上标记，并记录终止接点，记为 $now$ 。
那么每次在当前前缀的末尾添加一个字符， $now$ 节点可能会直接选权值最大的边往后走一步，也可能会回退若干步再往后走，这种情况会发生当且仅当新加入的字符在前一前缀构成的路径上连出了比原来边权值更大的边，所以在 $sam$ $extend$ 同时还要记录路径上满足这一条件的深度最小的节点。
需要注意的是在构建 $sam$ 的过程中可能会将一些边重定向到复制出的 $clone$ 节点上，如果最大字串的路径经过这些边，对应节点的标记也要改变，不能理解的话可以先补习 $sam$ 的构建过程。
在构建 $sam$ 的过程中，每添加一个字符 $now$ 节点会往后走一步，总共往后走加上回退的总次数不会超过 $O(n)$ ，因此复杂度为 $O(n)$ 。

$kmp$ 的做法。
其实不难看出每一次的结果一定是当前前缀的某一段后缀（如果不是可以继续延长至末尾直到成为后缀），并且第 $i$ 次的答案一定是第 $i - 1$ 次答案的某一段公共前后前缀加上 $s_i$ 。这里结合 $sam$ 的做法不难理解，在 $sam$ 末尾 $extend$ 一个字符后， $now$ 节点回退若干步会到达第 $i - 1$ 次答案的一段前缀，再往后加上字符 $s_i$ 后得到的是第 $i$ 次的答案，由于答案一定是当前的某一段后缀，所以第 $i$ 次答案去掉 $s_i$ 一定是第 $i - 1$ 次答案的某一个 $border$ 。
那么一个显然的做法就是暴力跳 $kmp$ ，对每一个 $border$ 都试一次，取长度最小的结果作为答案。
显然这是 $O(n^2)$ 的，不好。
考虑 $border$ 的性质 $\rightarrow$ 一个串的所有 $border$ 长度构成 $O(logn)$ 个等差数列，对于每个等差数列中的 $border$ 它们的循环节是相同的，因此对于每个等差数列取长度最小的 $border$ 来更新答案即可。
具体实现可以对当前的答案实时构建一个 $kmp$ 自动机，更新时直接覆盖前面的值即可，和 $sam$ 的做法一样是一个均摊的复杂度。
总复杂度为 $O(n \cdot logn)$ 。

代码

$sam$

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

using ll=long long;

constexpr int N=1e6+5;
constexpr int M=26;

int n;
char s[N];
int minndep,now;
int vis[N*2];
struct SAM{
    int nex[N*2][M];
    int choose[N*2];
    int dep[N*2];
    int fa[N*2];
    int len[N*2];
    int link[N*2];
    int cnt[N*2];
    int lst;
    int tot;
    SAM(){
        memset(link,-1,sizeof(link));
    }
    void cpy(int x,int y){
        for(int i=0;i<M;i++) nex[x][i]=nex[y][i];
        choose[x]=choose[y];
        len[x]=len[y];
        link[x]=link[y];
        cnt[x]=0;
    }
    void extend(char c){
        int w=c-'a';
        int u=++tot;
        len[u]=len[lst]+1;
        int p=lst;
        while(p!=-1&&!nex[p][w]){
            if(vis[p]&&p!=now&&choose[p]<w) minndep=min(minndep,dep[p]);
            nex[p][w]=u;
            p=link[p];
        }
        if(p==-1) link[u]=0;
        else{
            int q=nex[p][w];
            if(len[p]+1==len[q]) link[u]=q;
            else{
                int clone=++tot;
                cpy(clone,q);
                len[clone]=len[p]+1;
                while(p!=-1&&nex[p][w]==q){
                    if(vis[p]&&vis[q]&&dep[p]+1==dep[q]){
                        fa[clone]=fa[q];
                        choose[clone]=choose[q];
                        dep[clone]=dep[q];
                        vis[clone]=1;
                        vis[q]=0;
                        if(q!=now) fa[nex[clone][choose[clone]]]=clone;
                        else now=clone;
                    }
                    nex[p][w]=clone;
                    p=link[p];
                }
                link[q]=link[u]=clone;
            }
        }
        lst=u;
        cnt[u]++;
    }
}t;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>s+1;
    n=strlen(s+1);
    vis[0]=1;
    for(int i=1;i<=n;i++){
        minndep=n+1;
        t.extend(s[i]);
        while(t.dep[now]>minndep){
            vis[now]=0;
            now=t.fa[now];
        }
        while(true){
            int x=-1;
            for(int j=25;j>=0;j--) if(t.nex[now][j]){
                x=j;
                break;
            }
            if(x==-1) break;
            t.choose[now]=x;
            t.fa[t.nex[now][x]]=now;
            now=t.nex[now][x];
            vis[now]=1;
            t.dep[now]=t.dep[t.fa[now]]+1;
        }
        cout<<i-t.dep[now]+1<<" "<<i<<'\n';
    }

    return true&&false;
}

$kmp$

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

constexpr int N=1e6+5;

int n;
char s[N],t[N];
int fail[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>s+1;
    for(int i=1;s[i];i++){
        if(!n){
            t[++n]=s[i];
            fail[1]=0;
        }
        else{
            int len=n;
            int p=n;
            while(p){
                int T=p-fail[p];
                p%=T;
                if(t[p+1]<s[i]) len=p;
                p=fail[p];
            }
            if(t[p+1]<s[i]) len=p;
            t[len+1]=s[i];
            n=len+1;
            if(n==1) fail[n]=0;
            else{
                for(int j=fail[n-1];;j=fail[j]){
                    if(t[j+1]==t[n]){
                        fail[n]=j+1;
                        break;
                    }
                    else if(j==0){
                        fail[n]=0;
                        break;
                    }
                }
            }
        }
        cout<<i-n+1<<" "<<i<<"\n";
    }

    return true&&false;
}