【M Contect-Div.3】#4 题解

mengnn · 2025-09-26 16:21:58 · 题解

本帖由 mengnn 编写，若有疏漏感谢指出。

本帖 2125.13.31 完工。

A. Rock-Strings-Decipher 题解

题面及思路

简单的模拟和判断，从头到尾把字符串看一遍就好，就不过多赘述，直接粘的 #2 T1 的解释。

注意：str=s[i]+str 等代码复杂度是 O(n) 的，建议直接使用 reverse() 函数。

时间复杂度

简单的线形级复杂度，若设输入总字符数为 n，字符串平均长度为 |s|，则复杂度为 O(n|s|)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,a[N];
string s[N];
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>s[i];
    for (int i=1,x;i<=n;i++) cin>>x,a[abs(x)]=i*(abs(x)/x);
    for (int i=1;i<=n;i++){
        if (a[i]<0) reverse(s[-a[i]].begin(),s[-a[i]].end());
        cout<<s[abs(a[i])]<<' ';
    }
    return 0;
}

代码来自 @mengnn。

B. Rock-Strings-Real 题解

题面及思路

这个题代码很简单，虽然 1\le q\le10^5 但我们依然可以考虑暴力取分。

因为要维护定位删点增点序列，所以我们可以考虑简单数据结构——链表。它可以把 O(n) 的区间操作转换为 O(1) 的单点操作。

对于 1 操作，我们仅需确定 x 字符串的位置，将 y 字符串加入到 x 后面即可，这里还很板：

if (op==1){
    nxt[++sz]=nxt[mp[x]];
    vtx[sz]=y;
    nxt[mp[x]]=sz;
    mp[y]=sz;
}

观察到有一个 mp 数组，其意为某字符串的链表内编号。

对于 2 操作，因为需要区间删点，但我们却无法确定 x 和 y 在链表中的先后顺序。所以我们可以转换一下思路，从 x 和 y 同时向后移动指针，直到其中一方搜索到对方，我们就更新答案，实现代码：

string ans1="",ans2="";
for (int i=mp[x],j=mp[y];i||j;ans1+=(vtx[i]!=y?vtx[i]:""),ans2+=(vtx[j]!=x?vtx[j]:"")){
    if (vtx[i]==y){
        ans^=f(ans1);
        nxt[mp[x]]=mp[y];
        break;
    }
    if (vtx[j]==x){
        ans^=f(ans2);
        nxt[mp[y]]=mp[x];
        break;
    }
    if (i) i=nxt[i];
    if (j) j=nxt[j];
}

最后我们只需完成最终“进制转换”的 f() 函数，这里非常简单，就不过多赘述：

inline int f(string &s){
    long long cnt=0;
    for (char c:s) cnt=(cnt*26+c-'a')%P;
    return (int)(cnt%P);
}

全部完成后你就会发现，你这样“O(q^2)”的代码就直接 AC 了？！

注意：如果你链表模拟的 map 定义为 map<string,string>，那就会莫名奇妙出很多错，时间复杂度甚至不如暴力，建议写为 map<string,int>。

时间复杂度

简单观察容易发现，事实上，你链表的每个点只会被插入和删除最多一次，于是总共的次数便是 q 量级的的。

于是，本“暴力”代码的真实时间复杂度是 O(q\log_2 q) 的（因为 map<string,int> 存储会带一个 \log）。

AC Code:

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int P=1e9+7;
int q,nxt[N],sz=1;
map<string,int> mp;
string s,vtx[N];
inline int f(string &s){
    long long cnt=0;
    for (char c:s) cnt=(cnt*26+c-'a')%P;
    return (int)(cnt%P);
}
int main(){
    cin>>q>>s;
    mp[s]=1;vtx[1]=s;
    int ans=0;
    while (q--){
        int op;
        string x,y;
        cin>>op>>x>>y;
        if (op==1){
            nxt[++sz]=nxt[mp[x]];
            vtx[sz]=y;
            nxt[mp[x]]=sz;
            mp[y]=sz;
        }else{
            string ans1="",ans2="";
            for (int i=mp[x],j=mp[y];i||j;ans1+=(vtx[i]!=y?vtx[i]:""),ans2+=(vtx[j]!=x?vtx[j]:"")){
                if (vtx[i]==y){
                    ans^=f(ans1);
                    nxt[mp[x]]=mp[y];
                    break;
                }
                if (vtx[j]==x){
                    ans^=f(ans2);
                    nxt[mp[y]]=mp[x];
                    break;
                }
                if (i) i=nxt[i];
                if (j) j=nxt[j];
            }
        }
    }cout<<ans;
    return 0;
}

代码来自 @mengnn。

C. Rock-String-Search 题解

题面及思路

这题还是很恶心的。

观察题面，简单的二维平面最短路径问题，但实际用 bfs 操做会有很多难点，于是...

因为石头的数量很少，所以我们可以爆搜！

对于每个石头都求最短路径，走到哪个取哪个直接暴力性质的 DFS+BFS 便可通过此题。

不是，这题都快被削成模拟题了。

时间复杂度

设一共有 k 个石头，每个石头都会进行一次 O(nm) 的模拟。

于是，最终时间复杂度为 O(knm) 绝对没有超出时间限制。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
struct node{
    int x,y;
    int st,cnt;
};
int n,m,ans=-1;
int mp[N][N],sum=0;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool vis[N][N];
inline void bfs(int sx,int sy,int st,int cnt){
    if (cnt==sum){
        ans=st;
        return ;
    }
    queue<node> q;
    q.push({sx,sy,st});
    vis[sx][sy]=true;
    while (!q.empty()){
        node t=q.front();q.pop();
        for (int i=0;i<4;i++){
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if (x&&y&&x<=n&&y<=m&&mp[x][y]!=2&&!vis[x][y]){
                if (mp[x][y]){
                    while (!q.empty()) q.pop();
                    mp[x][y]=0;
                    for (int i=1;i<=n;i++)
                        for (int j=1;j<=m;j++)
                            vis[i][j]=false;
                    bfs(x,y,t.st+1,cnt+1);
                    return ;
                }
                q.push({x,y,t.st+1});
                vis[x][y]=true;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            cin>>mp[i][j];
            sum+=(mp[i][j]==1);
        }
    if (mp[1][1]==2){
        puts("-1");
        return 0;
    }
    int k=mp[1][1];
    if (k==1) mp[1][1]=0;
    bfs(1,1,0,(k==1));
    cout<<ans;
    return 0;
}

代码来自 @mengnn。

D. Rock-String-Key 题解

题面及思路

时间复杂度

因为输入元素个数为 n，所以输入和遍历数组复杂度绝对就是 O(n) 的。

又因为用到了离散化和树状数组，所以它们各会取一个 O(\log_2n)。

总时间复杂度来到了 O(n+n\log_2^2n)，最终复杂度 O(n\log_2^2n) 看起来不太能通过，但树状数组的和离散化二分的 \log_2n 常数都很小，足以通过此题。

AC Code:

#include<bits/stdc++.h>
using namespace std;
int T;long long a,b;
int main(){
    cin>>T;
    while (T--){
        cin>>a>>b;
        while (__gcd(a,b)!=1) a=__gcd(a,b),b/=a;
        if (b==1) puts("-1");
        else cout<<b<<'\n';
    }
    return 0;
}

代码来自 @mengnn。

E. Rock-String-Run 题解

题面及思路

时间复杂度

AC Code:

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void rd(T &x){
    x=0;T f=1;
    char ch=getchar();
    while (!isdigit(ch)){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch-'0');
        ch=getchar();
    }
    x*=f;
}
inline __int128 af(__int128 x,__int128 y){
    if (x>y) return x-y;
    else return y-x;
}
int main(){
    for (__int128 x=1,y=1;x&&y;rd(x),rd(y),puts(x&&y?(~af(x,y)&1?"We did it,we are best.":"Oh,no rock is lost."):""));
    return 0;
}

代码来自 @mengnn。

F. Rock-String-Shop 题解

题面及思路

时间复杂度

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
const long long mod=1e9+7;
int n,k,a,b;
long long dp[N][N],s[N];
int main(){
    cin>>n>>a>>b>>k;
    if (abs(a-b)<2){
        putchar('0');
        return 0;
    }
    dp[0][a]=1;
    for (int i=1;i<=k;i++){
        for (int j=1;j<b;j++)
            if (dp[i-1][j]){
                int l=max(2*j-b+1,1);
                int r=b-1;
                dp[i][l]=(dp[i][l]+dp[i-1][j])%mod;
                dp[i][j]=(dp[i][j]-dp[i-1][j])%mod;
                dp[i][j+1]=(dp[i][j+1]+dp[i-1][j])%mod;
                dp[i][r+1]=(dp[i][r+1]-dp[i-1][j])%mod;
            }
        for (int j=b+1;j<=n;j++)
            if (dp[i-1][j]){
                int l=b+1;
                int r=min(2*j-b-1,n);
                dp[i][l]=(dp[i][l]+dp[i-1][j])%mod;
                dp[i][j]=(dp[i][j]-dp[i-1][j])%mod;
                dp[i][j+1]=(dp[i][j+1]+dp[i-1][j])%mod;
                dp[i][r+1]=(dp[i][r+1]-dp[i-1][j])%mod;
            }
        for (int j=1;j<=n;j++)
            dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
    }
    long long ans=0;
    for (int i=1;i<=n;i++)
        ans=(ans+(dp[k][i]%mod+mod)%mod)%mod;
    cout<<ans<<'\n';
    return 0;
}

代码来自 @mengnn。