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

caizimo · 2025-07-21 16:29:34 · 个人记录

考试情况

题目总结

【模板】单调栈

正确思路

单调栈的模板，只要每次维护栈内单调性，如果栈顶和新进栈的元素不再单调，那就记录并弹出。

AC Code

#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，最后将所有答案取最大值即刻。

AC Code

#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判断是否有环即可。

AC Code

#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表模板题。

AC Code

#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类型就可以了，其他是板子，但要注意，本题大小写不敏感，但是输出时要输出原字符串，所以大写转小写要复制一遍在判断。

AC Code

#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;
}

总结

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