专栏文章

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

mmengnn
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minsdrm8
此快照首次捕获于
2025/12/02 07:34
3 个月前
此快照最后确认于
2025/12/02 07:34
3 个月前
查看原文
本帖由 mengnn 编写，若有疏漏感谢指出。
本帖 2125.13.31 完工。

A. Rock-Strings-Decipher 题解

题面及思路

简单的模拟和判断，从头到尾把字符串看一遍就好，就不过多赘述，直接粘的 #2 T1 的解释。
注意：str=s[i]+str 等代码复杂度是 O(n)O(n) 的，建议直接使用 reverse() 函数。

时间复杂度

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

AC Code:

CPP
#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≤q≤1051\le q\le10^5 但我们依然可以考虑暴力取分。
因为要维护定位删点增点序列，所以我们可以考虑简单数据结构——链表。它可以把 O(n)O(n) 的区间操作转换为 O(1)O(1) 的单点操作。
对于 11 操作，我们仅需确定 xx 字符串的位置，将 yy 字符串加入到 xx 后面即可，这里还很板：
CPP
if (op==1){
    nxt[++sz]=nxt[mp[x]];
    vtx[sz]=y;
    nxt[mp[x]]=sz;
    mp[y]=sz;
}
观察到有一个 mp 数组，其意为某字符串的链表内编号。
对于 22 操作，因为需要区间删点，但我们却无法确定 xx 和 yy 在链表中的先后顺序。所以我们可以转换一下思路，从 xx 和 yy 同时向后移动指针，直到其中一方搜索到对方，我们就更新答案，实现代码：
CPP
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() 函数，这里非常简单，就不过多赘述：
CPP
inline int f(string &s){
	long long cnt=0;
	for (char c:s) cnt=(cnt*26+c-'a')%P;
	return (int)(cnt%P);
}
全部完成后你就会发现，你这样“O(q2)O(q^2)”的代码就直接 AC 了？！
注意：如果你链表模拟的 map 定义为 map<string,string>，那就会莫名奇妙出很多错，时间复杂度甚至不如暴力，建议写为 map<string,int>。

时间复杂度

简单观察容易发现，事实上，你链表的每个点只会被插入和删除最多一次，于是总共的次数便是 qq 量级的的。
于是，本“暴力”代码的真实时间复杂度是 O(qlog⁡2q)O(q\log_2 q) 的（因为 map<string,int> 存储会带一个 log⁡\log）。

AC Code:

CPP
#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 便可通过此题。
不是，这题都快被削成模拟题了。

时间复杂度

设一共有 kk 个石头，每个石头都会进行一次 O(nm)O(nm) 的模拟。
于是，最终时间复杂度为 O(knm)O(knm) 绝对没有超出时间限制。

AC Code:

CPP
#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 题解

题面及思路

时间复杂度

因为输入元素个数为 nn，所以输入和遍历数组复杂度绝对就是 O(n)O(n) 的。
又因为用到了离散化和树状数组，所以它们各会取一个 O(log⁡2n)O(\log_2n)。
总时间复杂度来到了 O(n+nlog⁡22n)O(n+n\log_2^2n)，最终复杂度 O(nlog⁡22n)O(n\log_2^2n) 看起来不太能通过，但树状数组的和离散化二分的 log⁡2n\log_2n 常数都很小，足以通过此题。

AC Code:

CPP
#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:

CPP
#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:

CPP
#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。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...