专栏文章

2025夏图论&数据结构小测4考试总结

ccaizimo
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miot3xa2
此快照首次捕获于
2025/12/03 00:42
3 个月前
此快照最后确认于
2025/12/03 00:42
3 个月前
查看原文

考试情况

题目分数总分
【模板】单调栈100分190分
[USACO19DEC] Milk Pumping G20分
套利0分
汽车拉力比赛70分
忠诚0分
查单词没做

题目总结

【模板】单调栈

正确思路

单调栈的模板，只要每次维护栈内单调性，如果栈顶和新进栈的元素不再单调，那就记录并弹出。
时间复杂度：O(n) 时间复杂度：O(n)

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=3e6+10;
ll a[N],r[N];
stack<ll> st;
int main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(!st.empty()&&a[st.top()]<a[i]){
			r[st.top()]=i;
			st.pop();
		}
		st.push(i);
	}
	for(int i=1;i<=n;i++){
		cout<<r[i]<<' ';
	}
	return 0;
}

[USACO19DEC] Milk Pumping G

错误原因

在最后取max时错误地将ans定义成了double，因为题目说的是输出一个整数，所以导致丢分。

正确思路

题意：给定n个点，m条无向边，第i条边有边权c[i]表示费用，f[i]表示流量，一条路径的流量是路径上流量的最小值，求一条路径，使路径上流量/路径费用最大。
分析： 我们可以枚举流量，然后跑以费用为边权的最短路，并且经过的边流量不能<i，最后将所有答案取最大值即刻。
时间复杂度：O(1000∗n∗logn) 时间复杂度：O(1000*n*logn)

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int y,w;
	double f;
	bool operator < (const node & tmp) const
	{
		return w>tmp.w;
	}
};
int n,m,vis[N],dis[N];
vector<node> g[N];
void dijkstra(int s,int flow){
	priority_queue<node> q;
	for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f,vis[i]=0;
	dis[s]=0;
	q.push({s,dis[s]});
	while(!q.empty()){
		int x=q.top().y;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i].y,w=g[x][i].w,f=g[x][i].f;
			if(f>=flow&&dis[x]+w<dis[y]){
				dis[y]=dis[x]+w;
				q.push({y,dis[y]});
			}
		}
	}
	return ;
}
int main(){
//	freopen("B.in","r",stdin);
//	freopen("B.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,f,w; cin>>x>>y>>w>>f;
		g[x].push_back({y,w,f});
		g[y].push_back({x,w,f});
	}
	int ans=INT_MIN;
	for(int i=1;i<=1000;i++){
		dijkstra(1,i);
		ans=max(ans,1000000*i/dis[n]);
	}
	cout<<ans;
	return 0;
}

套利

错误原因

在跑dijkstra时，把求最大值求成了最小值，并且再多组数据下，建的图没有清空。

正确思路

本体质让我们判断是否能够套利，所以我们只要用spfa判断是否有环即可。
时间复杂度：O(多组数据∗n∗m) 时间复杂度：O(多组数据*n*m)(实际可能达不到这么多)

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int y;
	double w;
};
int n,m;
double dis[N];
int vis[N],cnt[N];
map<string,int> mp;
vector<node> g[N];
bool spfa(int s){
	for(int i=1;i<=n;i++){
		dis[i]=vis[i]=cnt[i]=0;
	}
	queue<int> q;
	dis[s]=1;
	q.push(s);
	vis[s]=1;
	cnt[s]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i].y;
			double w=g[x][i].w;
			if(dis[x]*w>dis[y]){
				dis[y]=dis[x]*w;
				cnt[y]=cnt[x]+1;
				if(cnt[y]>n-1) return 1;
				if(vis[y]==0){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	return 0;
}
int main(){
//	freopen("C.in","r",stdin);
//	freopen("C.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
	while(1){
		cin>>n;
		if(!n) break;
		for(int i=1;i<=n;i++){
			g[i].clear();
			string s; cin>>s;
			mp[s]=i;
		}
		cin>>m;
		for(int i=1;i<=m;i++){
			string s,t; double x; cin>>s>>x>>t;
			g[mp[s]].push_back({mp[t],x});
		}
		bool f=0;
		for(int i=1;i<=n;i++){
			if(spfa(i)){
				cout<<"Case "<<t<<": Yes\n";
				f=1; break;
			}
		}
		if(!f) cout<<"Case "<<t<<": No\n";
		t++;
	}
	return 0;
}

汽车拉力比赛

错误原因

在判断边界时没有处理好，把i<m写成了i<=m，导致判断错误

正确思路

本题我们可以枚举D，然后判断在本次的D以内，是否所有的路标都联通，如果联通，就说明他是第一个可以联通的，直接输出，但是我们会发现D最多是1e9枚举很明显会超时，这是我们会发现，D值越大，越容易联通，具有单调性，我们可以考虑二分优化，如果本次mid可行，那么就往小继续试，最后输出r。
时间复杂度O(m∗n∗logD) 时间复杂度O(m*n*logD)

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int n,m,a[510][510],vis[N],fa[N],tot;
int get_id(int i,int j){
	return (i-1)*n+j;
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y){
	x=find(x); y=find(y);
	if(x!=y) fa[x]=y;
	return ;
}
bool check(int mid){
	for(int i=1;i<=n*m;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(j+1<=n&&abs(a[i][j]-a[i][j+1])<=mid) unionn(get_id(i,j),get_id(i,j+1));
			if(i+1<=m&&abs(a[i][j]-a[i+1][j])<=mid) unionn(get_id(i,j),get_id(i+1,j));
		}
	}
	for(int i=2;i<=tot;i++){
		if(find(vis[i])!=find(vis[i-1])) return 0;
//		else cout<<mid<<' '<<i<<' '<<i-1<<' '<<find(vis[i])<<' '<<find(vis[i-1])<<endl;
	}
	return 1;
}
int main(){
//	freopen("D.in","r",stdin);
//	freopen("D.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>m>>n;
	int maxn=-1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			maxn=max(maxn,a[i][j]);
		}
	}
	tot=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			int x; cin>>x;
			if(x) vis[++tot]=get_id(i,j);
		}
	}
	int l=-1,r=maxn+1;
	while(l+1<r){
		int mid=(r+l)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<r;
	return 0;
}

忠诚

错误原因

数组开大了

正确思路

ST表模板题。
时间复杂度：O(n∗logn) 时间复杂度：O(n*logn)

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e5+10;
int n,m,dp[N][20],lg[N],a[N];
void ST_RMQ(){
	for(int i=1;i<=n;i++) dp[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
		}
	}
	return ;
}
int main(){
//	freopen("E.in","r",stdin);
//	freopen("E.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dp,0x3f,sizeof dp);
	cin>>n>>m;
	lg[0]=-1;
	for(int i=1;i<=n;i++){
		cin>>a[i]; lg[i]=lg[i/2]+1;
	}
	ST_RMQ();
	for(int i=1;i<=m;i++){
		int x,y; cin>>x>>y;
		int len=y-x+1;
		int j=lg[len];
		cout<<min(dp[x][j],dp[y-(1<<j)+1][j])<<' ';
	}
	return 0;
}

查单词

正确思路

只要将st表改一下，max函数改为string类型，并且dp也改为string类型就可以了，其他是板子，但要注意，本题大小写不敏感，但是输出时要输出原字符串，所以大写转小写要复制一遍在判断。
时间复杂度：O(n∗logn) 时间复杂度：O(n*logn)

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e5+10;
int n,m,lg[N];
string a[N],dp[N][20];
string MAX(string a,string b){
	string s=a,t=b;
	for(int j=0;j<s.size();j++){
		if(s[j]>='A'&&s[j]<='Z') s[j]+=32;
	}
	for(int j=0;j<t.size();j++){
		if(t[j]>='A'&&t[j]<='Z') t[j]+=32;
	}
	if(s>t){
		return a;
	}
	return b;
}
void ST_RMQ(){
	for(int i=1;i<=n;i++) dp[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			dp[i][j]=MAX(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
		}
	}
	return ;
}
int main(){
//	freopen("F.in","r",stdin);
//	freopen("F.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	lg[0]=-1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lg[i]=lg[i/2]+1;
	}
	ST_RMQ();
	while(m--){
		int x,y; cin>>x>>y;
		int len=y-x+1;
		int j=lg[len];
		cout<<MAX(dp[x][j],dp[y-(1<<j)+1][j])<<endl;
	}
	return 0;
}

总结

这次没考好，还是在细节上有问题，代码框架没有问题，但是在细节的检查上还要多加练习。

评论

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

正在加载评论...