竞赛讨论区 > 【题解】2026年北京印刷学院校赛题解
头像
比那名居的桃子
发布于 05-21 16:13 北京
+ 关注

【题解】2026年北京印刷学院校赛题解

（B题数据已加强并重测）

A 小红的相切直线

难度：

知识点：计数、几何观察

思路：

对于一条竖直直线 ，它与第 个圆相切，当且仅当 或者 。
对于一条水平直线 ，它与第 个圆相切，当且仅当 或者 。

于是问题就变成统计这些候选坐标中，哪个值出现次数最多。把所有 分别丢进数组排序后做计数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,i,ans=0;
        cin>>n;
        vector<int>a,b;
        a.reserve(n*2);
        b.reserve(n*2);
        for(i=1;i<=n;i++){
            int x,y,r;
            cin>>x>>y>>r;
            a.push_back(x-r);
            a.push_back(x+r);
            b.push_back(y-r);
            b.push_back(y+r);
        }
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        int c=0,last=4e18;
        for(auto x:a){
            if(x!=last)c=0,last=x;
            c++;
            ans=max(ans,c);
        }
        c=0,last=4e18;
        for(auto x:b){
            if(x!=last)c=0,last=x;
            c++;
            ans=max(ans,c);
        }
        cout<<ans<<"\n";
    }
}

B 小红的 gcd

难度：

知识点：数论、、容斥原理

思路：

设 ，题目要求的是：

注意到任意两个 的差值与原数组对应元素差值相同，因此令

则有

进一步可推出，合法的 恰好满足：

于是题目变成统计区间 中有多少个整数与 互质。把 做质因数分解，然后对这些质因子做容斥即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>p;
int cnt(int n,int g){
    if(g==0)return n>=1;
    p.clear();
    for(int i=2;i*i<=g;i++){
        if(g%i==0){
            p.push_back(i);
            while(g%i==0)g/=i;
        }
    }
    if(g>1)p.push_back(g);
    int m=p.size(),res=n;
    for(int s=1;s<(1<<m);s++){
        int t=1,c=0;
        for(int i=0;i<m;i++){
            if(s>>i&1){
                t*=p[i];
                c++;
            }
        }
        if(c&1)res-=n/t;
        else res+=n/t;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,i,g=0,m=4e18;
    cin>>n;
    vector<int>a(n);
    for(i=0;i<n;i++){
        cin>>a[i];
        m=min(m,a[i]);
    }
    for(i=1;i<n;i++)g=__gcd(g,abs(a[i]-a[0]));
    cout<<cnt(m-1,g)<<"\n";
}

C 小红的格式化

难度：

知识点：字符串

思路：

顺着字符串扫一遍即可。若当前位置是开头，或者前一个字符是空格，就把当前位置变成大写字母；否则保持原样。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    string s;
    getline(cin>>ws,s);
    for(int i=0;i<(int)s.size();i++){
        if(i==0||s[i-1]==' ')s[i]=s[i]-'a'+'A';
    }
    cout<<s<<"\n";
}

D 小红的物品兑换

难度：

知识点：图论、强连通分量、缩点、DAG 上的 DP

思路：

把每种物品看成一个点。若存在兑换关系 ，就连一条 的边，边权记为 ，表示一个 最多可以变成 个 。

如果某个强连通分量内存在一条边权大于 的边，那么由于分量内点互相可达，可以不断绕圈放大数量，这个分量内以及它能到达的所有分量答案都应为 。

把图缩点之后得到一张 DAG。对不会变成 的部分，只需要在 DAG 上做最长路 DP：

  • 设 表示到达缩点 时最多能拥有多少个当前分量里的物品
  • 从 号物品所在缩点开始转移

这样就能得到所有有限答案。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>>g[202020],rg[202020],dag[202020],rdag[202020];
int dfn[202020],low[202020],stk[202020],ins[202020],bel[202020],sz[202020],dp[202020];
int vis[202020],ord[202020],inf[202020],reach[202020],in[202020];
int tt,top,sc;
void tarjan(int x){
    dfn[x]=low[x]=++tt;
    stk[++top]=x;
    ins[x]=1;
    for(auto [y,w]:g[x]){
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(ins[y])low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        sc++;
        while(1){
            int y=stk[top--];
            ins[y]=0;
            bel[y]=sc;
            sz[sc]++;
            if(y==x)break;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        g[i].clear();
        rg[i].clear();
        dfn[i]=low[i]=bel[i]=0;
    }
    vector<array<int,3>>e;
    for(i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({z,y});
        rg[z].push_back({x,y});
        e.push_back({x,y,z});
    }
    tarjan(1);
    for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(i=1;i<=sc;i++){
        dag[i].clear();
        rdag[i].clear();
        vis[i]=inf[i]=reach[i]=in[i]=0;
        dp[i]=0;
    }
    vector<int>bad(sc+1);
    for(auto [x,y,z]:e){
        int a=bel[x],b=bel[z];
        if(a==b){
            if(y>1)bad[a]=1;
        }else{
            dag[a].push_back({b,y});
            rdag[b].push_back({a,y});
            in[b]++;
        }
    }
    queue<int>q;
    int s=bel[1];
    q.push(s);
    vis[s]=1;
    while(q.size()){
        int x=q.front();q.pop();
        for(auto [y,w]:dag[x]){
            if(!vis[y]){
                vis[y]=1;
                q.push(y);
            }
        }
    }
    for(i=1;i<=sc;i++){
        if(vis[i]&&bad[i]){
            q.push(i);
            inf[i]=1;
        }
    }
    while(q.size()){
        int x=q.front();q.pop();
        for(auto [y,w]:dag[x]){
            if(!inf[y]){
                inf[y]=1;
                q.push(y);
            }
        }
    }
    queue<int>tq;
    for(i=1;i<=sc;i++)if(!in[i])tq.push(i);
    int m2=0;
    while(tq.size()){
        int x=tq.front();tq.pop();
        ord[m2++]=x;
        for(auto [y,w]:dag[x]){
            if(--in[y]==0)tq.push(y);
        }
    }
    dp[s]=1;
    reach[s]=1;
    for(i=0;i<m2;i++){
        int x=ord[i];
        if(!reach[x]||inf[x])continue;
        for(auto [y,w]:dag[x]){
            if(inf[y])continue;
            reach[y]=1;
            dp[y]=max(dp[y],dp[x]*w);
        }
    }
    for(i=1;i<=n;i++){
        int x=bel[i];
        if(inf[x])cout<<-1;
        else if(reach[x])cout<<dp[x];
        else cout<<0;
        cout<<(i==n?'\n':' ');
    }
}

E 小红的舞会

难度：

知识点：树形 DP

思路：

设 表示节点 不参加舞会时，以 为根的子树最大快乐值； 表示节点 参加舞会时的最大快乐值。

转移分两种情况：

  • 若 会跳舞，那么当 不参加时，它的儿子都不能参加
  • 若 不会跳舞，那么当 不参加时，它的儿子可以参加也可以不参加，直接取最大值

而当 参加时，所有儿子都可以自由选择是否参加，因此统一加上 。

按树的后序顺序做一遍 DP 即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>g[202020];
int a[202020],f[202020][2],fa[202020],ord[202020];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,i;
        string s;
        cin>>n;
        for(i=1;i<=n;i++){
            cin>>a[i];
            g[i].clear();
        }
        cin>>s;
        for(i=1;i<n;i++){
            int x,y;
            cin>>x>>y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int m=0;
        queue<int>q;
        q.push(1);
        fa[1]=0;
        while(q.size()){
            int x=q.front();q.pop();
            ord[m++]=x;
            for(auto y:g[x]){
                if(y==fa[x])continue;
                fa[y]=x;
                q.push(y);
            }
        }
        for(i=n-1;i>=0;i--){
            int x=ord[i];
            f[x][1]=a[x];
            f[x][0]=0;
            for(auto y:g[x]){
                if(y==fa[x])continue;
                f[x][1]+=max(f[y][0],f[y][1]);
                if(s[x-1]=='1')f[x][0]+=f[y][0];
                else f[x][0]+=max(f[y][0],f[y][1]);
            }
        }
        cout<<max(f[1][0],f[1][1])<<"\n";
    }
}

F 小红选数

难度：

知识点：贪心、位运算

思路：

一个整数在二进制表示下末尾有多少个 ，等价于它含有多少个因子 。
因此若选出若干个数，它们乘积在二进制末尾的 的个数，就是这些数的因子 个数之和。

于是每个数的贡献只与 有关。对所有数按照 从大到小排序，取前 个输出即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int v2(int x){
    int s=0;
    while((x&1)==0)x>>=1,s++;
    return s;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,k,i;
        cin>>n>>k;
        vector<pair<int,int>>a(n);
        for(i=0;i<n;i++){
            cin>>a[i].second;
            a[i].first=v2(a[i].second);
        }
        sort(a.begin(),a.end(),greater<pair<int,int>>());
        for(i=0;i<k;i++){
            if(i)cout<<" ";
            cout<<a[i].second;
        }
        cout<<"\n";
    }
}

G 小红的概率

难度：

知识点：图论、构造计数、概率取模

思路：

把每个位置 看成一条边，连接候选值 和 。最终每条边必须选一个端点，而且所有 到 必须恰好各出现一次。

先处理强制情况：

  • 若 ，那么这一位固定取 ，同时这一位仍然对应两种等概率选择方式，因此答案额外乘
  • 若只有一个端点合法，那么这一位也被迫取那个合法值

把这些强制条件消化以后，剩下的图只由合法点构成。此时一个连通块只有两种可能：

  • 是一棵树，此时方案数为
  • 是一个简单环，此时方案数为

其余形态都不可能满足“每个数恰好出现一次”。

最后把所有连通块方案数乘起来，再乘上 即可。由于题目要求模 ，这里用快速幂求逆元。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1000000007;
vector<int>g[202020];
int need[202020],vis[202020];
int qp(int x,int y){
    int s=1;
    while(y){
        if(y&1)s=s*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return s;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,i,ans=1;
        cin>>n;
        vector<int>a(n+1),b(n+1),fix(n+1),deg(n+1),in(n+1),e1,e2;
        for(i=1;i<=n;i++)cin>>a[i];
        for(i=1;i<=n;i++)cin>>b[i];
        for(i=1;i<=n;i++){
            g[i].clear();
            need[i]=1;
            vis[i]=0;
        }
        int ok=1,m=0;
        auto good=[&](int x){return 1<=x&&x<=n;};
        for(i=1;i<=n;i++){
            int x=a[i],y=b[i];
            if(x==y){
                if(!good(x)){ok=0;break;}
                fix[x]++;
                ans=ans*2%mod;
                continue;
            }
            if(!good(x))x=0;
            if(!good(y))y=0;
            if(!x&&!y){ok=0;break;}
            if(!x||!y){
                fix[x+y]++;
                continue;
            }
            e1.push_back(x);
            e2.push_back(y);
            m++;
            deg[x]++;
            deg[y]++;
        }
        if(!ok){
            cout<<0<<"\n";
            continue;
        }
        for(i=1;i<=n;i++){
            if(fix[i]>1)ok=0;
            need[i]-=fix[i];
            if(need[i]<0)ok=0;
        }
        if(!ok){
            cout<<0<<"\n";
            continue;
        }
        int s=0;
        for(i=1;i<=n;i++)s+=need[i];
        if(s!=m){
            cout<<0<<"\n";
            continue;
        }
        for(i=0;i<m;i++){
            int x=e1[i],y=e2[i];
            if(!need[x]&&!need[y])ok=0;
            g[x].push_back(y);
            g[y].push_back(x);
            in[x]=in[y]=1;
        }
        if(!ok){
            cout<<0<<"\n";
            continue;
        }
        for(i=1;i<=n;i++){
            if(need[i]&&!in[i])ok=0;
        }
        if(!ok){
            cout<<0<<"\n";
            continue;
        }
        for(i=1;i<=n;i++){
            if(!in[i]||vis[i])continue;
            queue<int>q;
            q.push(i);
            vis[i]=1;
            int v=0,e=0,c=0;
            while(q.size()){
                int x=q.front();q.pop();
                v++;
                c+=need[x];
                e+=g[x].size();
                for(auto y:g[x]){
                    if(!vis[y]){
                        vis[y]=1;
                        q.push(y);
                    }
                }
            }
            e/=2;
            if(c!=e){
                ok=0;
                break;
            }
            if(e==v)ans=ans*2%mod;
            else if(e!=v-1){
                ok=0;
                break;
            }
        }
        if(!ok)cout<<0<<"\n";
        else cout<<ans*qp(qp(2,n),mod-2)%mod<<"\n";
    }
}

H 小红的平滑构造

难度：

知识点：构造、均匀分配

思路：

数组首项固定为 ，末项固定为 ，总共要跨越的距离为 。中间一共有 段，因此为了让最大相邻差最小，显然应该尽量平均分配到每一段上。

令

则前 段长度取 ，剩下的段长度取 。这样得到的构造最大相邻差最小。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,k,i,cur=1,d,q,r;
        cin>>n>>k;
        d=k-1;
        q=d/(n-1);
        r=d%(n-1);
        cout<<1;
        for(i=1;i<n;i++){
            cur+=q+(i<=r);
            cout<<" "<<cur;
        }
        cout<<"\n";
    }
}
2026最新求职资料大礼包领取
真题
历年笔试真题附答案
触宝科技2017秋季校招笔试客户端前端（第三批）
哔哩哔哩2023校园招聘移动端方向笔试卷
中国银行校招笔试真题-模拟卷1
全部 >
面经
面试常考问题整理
22届-国企上岸经验分享
管理类双非硕的23秋招记录＆反思
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
【百强外企】博世智行学院实习生招募
拼多多27届实习&26届校招内推内推码快速通道
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”