昨天 19:17 陈皮学院算法工程师发布于广东

关注

2026天梯赛题解

L1-1 一行代码

题意：签到（请输出文本）

print("Building the Future, One Line of Code at a Time.")

L1-2 要刷多少题

题意：输出 $15\times n$

n=int(input())
print(n*15)

L1-3 就挺突然的

题意：给定两个年份 $A$ 和年份 $B$ ，先计算 $B-A$ 并输出，再根据其是否 $>250$ 、 $\le 0$ 或在 $1\sim250$ 之间分别输出对应提示语。

void solve(){
    int a,b;cin>>a>>b;
    int d=b-a;
    cout<<d<<endl;
    if(d<=0){
        cout<<"hai sheng ma?";
    }else if(d<=250){
        cout<<"nin tai cong ming le!";
    }else{
        cout<<"jiu ting tu ran de...";
    }
    cout<<endl;
}

L1-4 普及赛排名

题意：给定 $n$ 个数，统计里面 $< 1700$ 的数的个数。

void solve(){
    int n;cin>>n;
    int cnt=0;
    for(int i=0;i<n;++i){
        int a;cin>>a;
        if(a<1700){
            ++cnt;
        }
    }
    cout<<cnt;
}

L1-5 做什么都被骂怎么办

题意：给定 $n$ 条记录，找出只有被骂而没有被夸的人。

思路：用两个标记数组分别记录每个编号是否被骂过、是否被夸过，最后按编号升序输出“被骂过且从未被夸过”的人，没有就输出NONE。

void solve(){
    int n;cin>>n;
    vb a(100001,0),b(100001,0);
    for(int i=0;i<n;++i){
        int x,y;cin>>x>>y;
        if(y==0)a[x]=1;
        else b[x]=1;
    }
    vi v;
    for(int i=1;i<=100000;++i){
        if(a[i]&&!b[i])v.push_back(i);
    }
    if(v.empty()){
        cout<<"NONE";
        return;
    }
    for(int i=0;i<(int)v.size();++i){
        if(i)cout<<" ";
        cout<<v[i];
    }
}

L1-6 钓鱼佬专用挪车电话

题意：给定 $11$ 行分别由 $0\sim9$ 个m构成的字符串，最后输出每行m的个数。

思路：通过getline(cin,s)输入每行字符串，输出s.size()返回的值。

void solve(){
	vi a(11);
    for(int i=0;i<11;++i){
        string s;
        getline(cin,s);
        a[i]=s.size();
    }
    for(int i:a)cout<<i;
}

L1-7 网络流量监测

题意：给定 $n$ 个每小时流量值，输出最大值、最小值和平均值（向下取整），再找出所有流量大于平均值 $2$ 倍的点（没有则输出Normal）。

思路：先一次遍历求出最大值、最小值和平均值（整除向下取整），再二次遍历找出所有流量严格大于平均值 $2$ 倍的小时下标输出，否则输出Normal。

void solve(){
    int n;cin>>n;
    vi a(n+1);
    ll s=0;
    int mx=0,mn=INF;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        s+=a[i];
        mx=max(mx,a[i]);
        mn=min(mn,a[i]);
    }
    ll avg=s/n;
    cout<<mx<<" "<<mn<<" "<<avg<<endl;
    vi v;
    for(int i=1;i<=n;++i){
        if((ll)a[i]>avg*2)v.push_back(i);
    }
    if(v.empty()){
        cout<<"Normal"<<endl;
        return;
    }
    for(int i=0;i<(int)v.size();++i){
        if(i)cout<<" ";
        cout<<v[i];
    }
}

L1-8 智慧文本编辑器

题意：模拟一个支持查找子串前 $3$ 次出现位置、插入字符串、翻转指定区间字符串三种操作的文本编辑器，按输入指令处理字符串并输出对应结果。

思路：答辩模拟。

void solve(){
    int n;cin>>n;
    string t;cin>>t;
    for(int i=0;i<n;++i){
        int x;cin>>x;
        if(x==1){
            string a;cin>>a;
            vi v;
            for(int j=0;j+(int)a.size()-1<(int)t.size();++j){
                int y=1;
                for(int k=0;k<(int)a.size();++k){
                    if(t[j+k]!=a[k]){
                        y=0;
                        break;
                    }
                }
                if(y){
                    v.push_back(j);
                    if((int)v.size()==3)break;
                }
            }
            if(v.empty()){
                cout<<-1<<endl;
            }else{
                for(int j=0;j<(int)v.size();++j){
                    if(j)cout<<" ";
                    cout<<v[j];
                }
                cout<<endl;
            }
        }else if(x==2){
            int p;string a;cin>>p>>a;
            t.insert(p,a);
            cout<<t<<endl;
        }else{
            int l,r;cin>>l>>r;
            reverse(t.begin()+l,t.begin()+r+1);
            cout<<t<<endl;
        }
    }
}

L2-1 姥姥改作业

题意：给定 $n$ 本作业的混乱指数与初始阈值 $T$ ，按混乱指数 $\leq T$ 直接批改、 $>T$ 暂存的规则处理，无待批改作业时将 $T$ 更新为暂存作业混乱指数的平均值并继续处理暂存作业，最终输出作业的批改编号顺序。

思路：按题意用两个栈模拟批改过程，每轮把当前堆里满足 $c_i\le T$ 的作业按顺序输出、把 $c_i>T$ 的作业放到左手堆，当前堆空后用左手堆混乱指数平均值更新 $T$ 并继续直到全部处理完。

void solve(){
    int n;ll t;cin>>n>>t;
    vi c(n+1);
    for(int i=1;i<=n;++i)cin>>c[i];
    vi a,b,v;
    for(int i=n;i>=1;--i)a.push_back(i);
    while(1){
        while(!a.empty()){
            int x=a.back();a.pop_back();
            if((ll)c[x]>t)b.push_back(x);
            else v.push_back(x);
        }
        if(b.empty())break;
        ll s=0;
        for(int i=0;i<(int)b.size();++i)s+=c[b[i]];
        t=s/(ll)b.size();
        a.swap(b);
    }
    for(int i=0;i<(int)v.size();++i){
        if(i)cout<<" ";
        cout<<v[i];
    }
}

L2-2 超参数搜索

题意：给定 $n$ 个参数组合的性能得分，先按升序输出所有得分最高的参数组合编号；再处理 $m$ 次查询，每次查询目标得分 $x$ ，从性能得分 $>x$ 的组合中找到得分最小（得分相同时取编号最小）的组合编号，不存在则输出0。

思路：用结构体存储每个参数组合的性能得分和对应的序号，按得分升序且序号升序排序后，顺序输出所有 $mx$ 的序号；每次查询通过二分查找符合的参数组合。

struct ai{
    int mk,id;
    bool operator<(const ai &y)const{
        if(mk!=y.mk)return mk<y.mk;
        else return id<y.id;
    }
};

void solve(){
	int n;cin>>n;
    vector<ai> a(n);
    for(int i=0;i<n;++i){
        cin>>a[i].mk;
        a[i].id=i+1;
    }
    sort(all(a));
    vi mx;
    for(int i=n-1;i>=0;--i){
        if(a[i].mk==a.back().mk)mx.push_back(a[i].id);
        else break;
    }
    sort(all(mx));
    for(int i=0;i<(int)mx.size();++i){
        if(i)cout<<" ";
        cout<<mx[i];
    }
    cout<<endl;
    int m;cin>>m;
    while(m--){
        int x;cin>>x;
        if(x>a.back().mk)cout<<0;
        else{
            int l=0,r=n;
            while(l<r){
                int mid=(l+r)>>1;
                if(a[mid].mk>x)r=mid;
                else l=mid+1;
            }
            cout<<a[l].id;
        }
        cout<<endl;
    }
}

L2-3 森林藏宝图

题意：给定一棵以 $0$ 为入口（根节点）、共 $n$ 个节点的树，每条边带安全系数权值；对每个藏宝地（叶子节点），计算从 $0$ 到该节点路径上所有边权的最小值；找出这些最小值中的最大值，并按升序输出所有取到该最大值的藏宝地编号。

思路：先从入口 $0$ 遍历整棵树并对每个点维护“到该点路径上的最小安全系数”，再在所有叶子中找这个值的最大者并按升序输出达到该最大值的藏宝地编号。

void solve(){
    int n;cin>>n;
    vector<vpii> g(n);
    vi d(n,0),f(n,0),q;
    for(int i=1;i<n;++i){
        int p,s;cin>>p>>s;
        g[p].push_back({i,s});
        d[p]++;
    }
    f[0]=INF;
    q.push_back(0);
    for(int i=0;i<(int)q.size();++i){
        int u=q[i];
        for(auto [v,w]:g[u]){
            f[v]=min(f[u],w);
            q.push_back(v);
        }
    }
    int mx=0;
    vi v;
    for(int i=1;i<n;++i){
        if(d[i]==0)mx=max(mx,f[i]);
    }
    for(int i=1;i<n;++i){
        if(d[i]==0&&f[i]==mx)v.push_back(i);
    }
    cout<<mx<<endl;
    for(int i=0;i<(int)v.size();++i){
        if(i)cout<<" ";
        cout<<v[i];
    }
    cout<<endl;
}

L2-4 大语言模型的推理

题意：给定 $n$ 个想法和 $m$ 个单向思维跳跃关系（ $id_1$ 引出 $id_2$ 的概率为 $p\%$ ），对每个根思维节点，按“优先选概率最高的子想法，概率相同时选编号最小的，不重复访问”的规则逐步推理，直到无新想法可生成，按顺序输出每条推理路径（节点间用->分隔）。

思路：先把每个想法的出边按概率降序且编号升序排序，然后对每个起点按这个顺序贪心选择第一个未访问后继一路前进并标记访问，直到没有可走边为止输出整条路径。

void solve(){
    int n,m;cin>>n>>m;
    vector<vpii> g(n+1);
    for(int i=0;i<m;++i){
        int x,y,p;cin>>x>>y>>p;
        g[x].push_back({y,p});
    }
    for(int i=1;i<=n;++i){
        sort(all(g[i]),[](pii a,pii b){
            if(a.se!=b.se)return a.se>b.se;
            return a.fi<b.fi;
        });
    }
    int k;cin>>k;
    vi a(k);
    for(int i=0;i<k;++i)cin>>a[i];
    vi vis(n+1,0);
    int t=0;
    for(int i=0;i<k;++i){
        ++t;
        int u=a[i];
        vis[u]=t;
        cout<<u;
        while(1){
            int v=0;
            for(int j=0;j<(int)g[u].size();++j){
                int x=g[u][j].fi;
                if(vis[x]!=t){
                    v=x;
                    break;
                }
            }
            if(!v)break;
            cout<<"->"<<v;
            u=v;
            vis[u]=t;
        }
        cout<<endl;
    }
}

L3-043 门诊预约排队系统

题意：给定 $n$ 位患者的到达时段、预约时段、ID 与年龄，按时段 $1\sim n$ 的顺序，每个时段按「优先叫当前时段预约且已到达的患者；无则优先候诊队列中 $80$ 岁及以上的老人（按预约时段升序）；仍无则按所有候诊患者的预约时段升序」的规则接诊，按实际就诊时段升序输出每位患者的就诊时段与 ID。

思路：按时间顺序模拟门诊流（上述规则），维护当前等待队列并优先处理预约时间已到的 $80$ 岁及以上患者，否则在可接诊时按最早预约者就诊，直到所有患者完成。

void solve(){
    int n;cin>>n;
    vi a(n),b(n),c(n);
    vs s(n);
    int mx=0;
    for(int i=0;i<n;++i){
        cin>>a[i]>>b[i]>>s[i]>>c[i];
        mx=max(mx,b[i]);
    }
    vi u(mx+1,-1);
    for(int i=0;i<n;++i){
        u[b[i]]=i;
    }
    set<int> v,w;
    int k=0,t=1,cnt=0;
    while(cnt<n){
        if(v.empty()&&k<n&&t<a[k])t=a[k];
        while(k<n&&a[k]<=t){
            v.insert(b[k]);
            if(c[k]>=80)w.insert(b[k]);
            ++k;
        }
        int x=0;
        if(v.count(t))x=t;
        else if(!w.empty())x=*w.begin();
        else if(!v.empty())x=*v.begin();
        if(x==0){
            ++t;
            continue;
        }
        int i=u[x];
        cout<<t<<" "<<s[i]<<endl;
        v.erase(x);
        if(c[i]>=80)w.erase(x);
        ++cnt;
        ++t;
    }
}

L3-2 花砖物语

题意：给定 $n$ 个工厂板块，每个板块有编号为 $r_i$ 的红色花砖和编号为 $b_i$ 的蓝色花砖，通过“从工厂板块拿取一块花砖并将剩余那块移至桌面中央”或“从桌面中央拿取所有同颜色同编号的花砖”两种操作，求拿完所有 $2n$ 块花砖所需的最少操作次数。

思路：把每个花色花瓣看成二分图两侧的点，建立红蓝花瓣之间的连边后求最大匹配，答案就是总花瓣数减去最大匹配数。

void solve(){
    int n;cin>>n;
    vvi g(n+1);
    for(int i=0;i<n;++i){
        int r,b;cin>>r>>b;
        g[r].push_back(b);
    }
    vi ml(n+1,0),mr(n+1,0),d(n+1),it(n+1);
    
    auto bfs=[&](){
        queue<int> q;
        bool ok=0;
        for(int i=1;i<=n;++i){
            if(!ml[i]) d[i]=0,q.push(i);
            else d[i]=-1;
        }
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int v:g[u]){
                int w=mr[v];
                if(!w)ok=1;
                else if(d[w]==-1)d[w]=d[u]+1,q.push(w);
            }
        }
        return ok;
    };
    function<bool(int)> dfs=[&](int u){
        for(int &i=it[u];i<(int)g[u].size();++i){
            int v=g[u][i],w=mr[v];
            if(!w||(d[w]==d[u]+1&&dfs(w))){
                ml[u]=v;
                mr[v]=u;
                return 1;
            }
        }
        d[u]=-1;
        return 0;
    };
    
    int cnt=0;
    while(bfs()){
        fill(all(it),0);
        for(int i=1;i<=n;++i){
            if(!ml[i]&&dfs(i))++cnt;
        }
    }
    cout<<n+cnt<<endl;
}

L3-3 序列谜题

题意（题面很短但我还是写了）：给定长度为 $n$ 的整数序列 $a$ ，求满足 $1 \leq b_i \leq n$ （ $1 \leq i \leq n$ ）的整数序列 $b$ 的个数，使得 $a \circ b = b \circ a$ （其中 $a \circ b$ 的第 $i$ 个元素定义为 $a_{b_i}$ ），答案对 $998244353$ 取模。

思路（powered by GPT）：把 $a$ 当成每个点只指向一个点的函数图后，整图会自动分成“一个环加若干入树”的结构，所以做法是先用剥叶子把所有非环点按拓扑顺序处理，并用 DP 预处理出每个树点映到任意目标点的方案数，等树枝贡献都算进来后只剩环与环的匹配，再对每个源环枚举可去的目标环（长度需满足整除关系）以及目标环上的起始对齐位置，把整圈对应点的 DP 值连乘并累加得到该源环贡献，最后把所有源环贡献相乘即为答案。

void solve(){
    int n;cin>>n;
    vi a(n+1),b(n+1,0);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        ++b[a[i]];
    }

    vi c(n+1,1);
    queue<int> q;
    for(int i=1;i<=n;++i){
        if(b[i]==0)q.push(i);
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        c[u]=0;
        int v=a[u];
        --b[v];
        if(b[v]==0)q.push(v);
    }

    vvi g(n+1);
    for(int i=1;i<=n;++i){
        if(!c[i])g[a[i]].push_back(i);
    }

    vi d(n+1,0),e;
    for(int i=1;i<=n;++i){
        if(!c[i])d[i]=(int)g[i].size();
    }
    queue<int> q2;
    for(int i=1;i<=n;++i){
        if(!c[i]&&d[i]==0)q2.push(i);
    }
    while(!q2.empty()){
        int u=q2.front();q2.pop();
        e.push_back(u);
        int v=a[u];
        if(!c[v]){
            --d[v];
            if(d[v]==0)q2.push(v);
        }
    }

    vvi f(n+1,vi(n+1,1));
    vi cur(n+1,1),sum(n+1,0);
    auto w=[&](int u){
        for(int i=1;i<=n;++i)cur[i]=1;
        for(int i=0;i<(int)g[u].size();++i){
            int x=g[u][i];
            for(int j=1;j<=n;++j)sum[j]=0;
            for(int j=1;j<=n;++j){
                int v=a[j];
                sum[v]+=f[x][j];
                if(sum[v]>=MOD2)sum[v]-=MOD2;
            }
            for(int j=1;j<=n;++j){
                cur[j]=1LL*cur[j]*sum[j]%MOD2;
            }
        }
        for(int i=1;i<=n;++i)f[u][i]=cur[i];
    };

    for(int i=0;i<(int)e.size();++i)w(e[i]);
    for(int i=1;i<=n;++i){
        if(c[i])w(i);
    }

    vi vis(n+1,0);
    vvi h;
    for(int i=1;i<=n;++i){
        if(c[i]&&!vis[i]){
            vi t;
            int u=i;
            while(!vis[u]){
                vis[u]=1;
                t.push_back(u);
                u=a[u];
            }
            h.push_back(t);
        }
    }

    ll ans=1;
    for(int i=0;i<(int)h.size();++i){
        vi &x=h[i];
        int l=(int)x.size();
        ll cnt=0;
        for(int j=0;j<(int)h.size();++j){
            vi &y=h[j];
            int r=(int)y.size();
            if(l%r)continue;
            for(int k=0;k<r;++k){
                ll p=1;
                for(int t=0;t<l;++t){
                    p=p*f[x[t]][y[(k+t)%r]]%MOD2;
                    if(p==0)break;
                }
                cnt+=p;
                if(cnt>=MOD2)cnt-=MOD2;
            }
        }
        ans=ans*cnt%MOD2;
    }
    cout<<ans<<endl;
}