已被标记为猫猫虫_usedchang

题解牛客2025秋季算法编程训练联赛2-基础组&提升组

题解

/ 注册

牛客2025秋季算法编程训练联赛2-基础组&提升组

101 浏览 0 回复 2025-10-24

已被标记为猫猫虫_usedchang

+关注

牛客2025秋季算法编程训练联赛2-提升组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

https://ac.nowcoder.com/acm/contest/119774/

A.做游戏

原题链接解题思路

尽可能多的使牛牛获胜，那么出石头，剪刀，布三种都取获胜的最大可能，对于石头：牛牛出的石头数量与牛可乐出的剪刀数量，剪刀和布亦然 note:注意c++开 long long

code

void solve(){
    ll a,b,c;
    ll x,y,z;
    cin>>a>>b>>c;
    cin>>x>>y>>z;
    cout<<min(a,y)+min(b,z)+min(c,x)<<endl;
}

B.排数字

解题思路

贪心的数字串中的616全部提出来，然后以61616...的顺序排下去，发现答案是 min((6的数量-1),1的数量)。

code

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    vector<int>mp(10);
    for(char c:s) mp[c-'0']++;
    cout<<max(min(mp[6]-1,mp[1]),0)<<endl;
}

C.判正误

解题思路

快速幂，没啥好说的，对于单一模数冲突概率很大，本题需要采用多模技术，但是题主赛时单模1234567891水过去了

note:快速幂需要处理负数幂不方便，要先把所有数归一化为0~mod-1内的数 ,0^0

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
vector<ll>Mod={998244353,2,3,5,11,13,1234567891LL};
ll q_pow(ll a,ll b,ll mod){
    a=(a%mod+mod)%mod;
    ll s=1;
    while(b){
        if(b&1){
            s=s*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return s;
}
void solve(){
    ll a,b,c,d,e,f,g;
    cin>>a>>b>>c>>d>>e>>f>>g;
    bool F=true;
    for(ll mod:Mod){
        ll s1=q_pow(a,d,mod),s2=q_pow(b,e,mod),s3=q_pow(c,f,mod);
        ll s=((s1+s2)%mod+s3)%mod;
        F&=(s==(g%mod+mod)%mod);
    }
    if(F) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;cin>>T;
    while(T--) solve();
    return 0;
}

D.数三角

解题思路

暴力枚举三个点然后用向量叉积判定是否共线，再根据余弦定理或者向量点积判定是否存在钝角。

code

void solve(){
    int n;cin>>n;
    vector< pair<int,int> >res(n+1);
    for(int i=1;i<=n;i++) cin>>res[i].first>>res[i].second;
    auto dis=[&](ll x,ll y) ->ll { return 1LL*x*x+1LL*y*y;};
    auto judge=[&](pair<int,int>a,pair<int,int>b,pair<int,int>c) ->bool {
        pair<int,int>w={b.first-a.first,b.second-a.second};
        pair<int,int>t={c.first-a.first,c.second-a.second};
        return 1LL*w.first*t.second!=1LL*w.second*t.first;
    };
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(!judge(res[i],res[j],res[k])) continue;//不共线的判定
                ll a=dis(res[i].first-res[j].first,res[i].second-res[j].second);
                ll b=dis(res[i].first-res[k].first,res[i].second-res[k].second);
                ll c=dis(res[k].first-res[j].first,res[k].second-res[j].second);
                ans+=(a+b<c);
                ans+=(b+c<a);
                ans+=(a+c<b);
            }
        }
    }
    cout<<ans<<endl;
}

E.做计数

解题思路

$\sqrt i + \sqrt j=\sqrt k$

$i+j+2\sqrt {i \times j} = k$ 而要满足这个等式存在两个条件：

1. $i \times j \leq n$

2. ${i \times j}$ 是一个完全平方数

那么就转化为了求解小于等于 n 范围内的完全平方数配对数了，暴力枚举作为平方的数和其中一个因子即可，复杂度 $O{(\sqrt n \times \sqrt n)}$

note:本题可以通过筛做到更快

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
vector<int>p;
void Init(int n){
    for(int i=1;i<=n/i;i++){
        p.push_back(i*i);
    }
}
void solve(){
    ll n;cin>>n;
    int ans=0;
    for(auto &x:p){
        for(int i=1;i<=x/i;i++){
            if(x>n) break;
            if(x%i==0){
                ans+=(x/i!=i)*2+(x/i==i);
            }
        }
    }
    cout<<ans<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    Init(4e7+5);
    solve();
    return 0;
}

F.拿物品

解题思路

简单贪心，考虑他们在争夺什么？当拿走第 i 个位置的物品后可以使对手永远无法获得 $b_i$ 的价值，并且自己一定可以获得 $a_i$ ,那么按照 $a_i+b_i$ 排序后顺序贪心取得的就是最大值。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
struct node{
    int x,y,idx;
};
void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    vector<int>b(n+1);
    vector< node >res(n+1);
    for(int i=1;i<=n;i++) cin>>a[i],res[i].x=a[i],res[i].idx=i;
    for(int i=1;i<=n;i++) cin>>b[i],res[i].y=b[i];
    sort(res.begin()+1,res.end(),[&](node w,node t){
        return w.x+w.y>t.x+t.y;
    });
    queue<int>Q;
    for(int i=1;i<=n;i++) Q.push(res[i].idx);
    vector<int>ans1,ans2;
    bool cur=0;
    while(!Q.empty()){
        cur^=1;
        int u=Q.front();
        Q.pop();
        (cur)?(ans1.push_back(u)):(ans2.push_back(u));
    }
    for(auto &x:ans1) cout<<x<<' ';
    cout<<endl;
    for(auto &x:ans2) cout<<x<<' ';
    cout<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

C.算概率

解题思路

简单概率dp，考虑前 i 个位置时答对了 j 个题目概率由考虑前 i-1 个位置答对了 j-1个题目或 j 个题目转移而来 $dp_{i,j}=dp_{i-1,j-1} \times p_i +dp_{i-1,j} \times (1-p_i)$ 暴力 $O(n^2)$ 转移即可注意特判 n=0 的情况 note:感觉应该基础场C>提高场C

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int mod=1e9+7;
ll q_pow(ll a,ll b){
    ll s=1;
    while(b){
        if(b&1){
            s=s*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return s;
}
void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    vector<ll>p(n+1);
    p[0]=1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        vector<ll>nxtp(n+1);
        nxtp[0]=p[0]*(1-a[i]+mod)%mod;
        for(int j=1;j<=i;j++){
            nxtp[j]=(p[j-1]*a[i]%mod+p[j]*(1-a[i]+mod)%mod)%mod;
        }
        p=nxtp;
    }
    for(int i=0;i<=n;i++) cout<<p[i]<<' ';
    cout<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

D.施魔法

解题思路

很容易注意到排序后可以使用区间 dp，前 i 个位置最少消耗魔力由比 i 小的位置转移过来，具体方程为 $dp_i= \min_{j=0,i-j>=k}^{i-1} ({dp_j+a_i-a_{j+1},dp_i})$ ,朴素枚举显然时 $O(n^2)$ 的,仔细注意一下发现把 $dp_j-a_{j+1}$ 这个东西看成整个整体，每次枚举更新他的前缀最值，最后就可以得到一个 $O(n)$ 的正解了

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
    int n,k;cin>>n>>k;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<ll>dp(n+1,INT_MAX);
    dp[0]=0;
    sort(a.begin()+1,a.end());
    ll minl=INT_MAX;
    for(int i=1;i<=n;i++){
        if(i>=k) minl=min(minl,dp[i-k]-a[i-k+1]);
        dp[i]=min(dp[i],minl+a[i]);
    }
    cout<<dp[n]<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

E.建通道

解题思路

位运算优先考虑拆位，发现如果存在某一位点权在序列中至少有一个数与他不同，那么我们可以把，记这一位为 i，那么我们把所有第 i 为1的数字与某个第 i 位为0 的数字相连，再把所有第 i 为 0 的数字与某个第 i 位为 1 的数字相连，发现相连后一定一颗生成树，那么就有一个贪心的思路，从小到大枚举发现第一位序列中有一位数与其不同时，就产生 1<<i*(n-1)的代价，可以证明这样代价一定最小，注意去重，因为如果两个数相同连接他们产生的 lowbit 显然是 0.

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a.begin()+1,a.end());
    a.erase(unique(a.begin()+1,a.end()),a.end());
    n=a.size()-1;
    for(int j=0;j<=31;j++){
        bool bit=(a[1]>>j&1);
        for(int i=2;i<=n;i++){
            if(bit^(a[i]>>j&1)) {
                cout<<(1LL<<j)*(n-1)<<endl;
                return;
            }
        }
    }
    cout<<0<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

F.求函数

解题思路

区间线段信息合并类题目，可以考虑线段树，发现其由一颗单点更新的线段树可以解决，考虑如何由子节点更新父节点发现分别维护 k 与 b 即可由子节点上传信息时

1. $parent.k=lchild.k \times rchild.k$

2. $parent.b=lchild.b \times rchild.k+rchild.b$

最后输出 k与 b之和即可

note:注意输入格式

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define lc (p<<1)
#define rc (p<<1|1)
typedef long long ll;
const int mod=1e9+7;
struct Seg{
    struct S{
        int l,r;
        ll k,b;
    };
    int n;
    vector<S>tre;
    Seg(int n):n(n){
        tre.resize(n<<2);
        build(1,n,1);
    }
    pair<ll,ll> merge(pair<ll,ll>x,pair<ll,ll>y){
        return pair<ll,ll>{x.first*y.first%mod,(y.first*x.second%mod+y.second)%mod};
    }
    void pushup(int p){
        tre[p].k=tre[lc].k*tre[rc].k%mod;
        tre[p].b=(tre[rc].k*tre[lc].b%mod+tre[rc].b)%mod;
    }
    void build(int l,int r,int p){
        tre[p]={l,r,0,0};
        if(l==r) return;
        int mid=l+r>>1;
        build(l,mid,lc);
        build(mid+1,r,rc);
        pushup(p);
    }
    void upd(int idx,pair<ll,ll>k,int p=1){
        if(tre[p].l==tre[p].r){
            tre[p].k=k.first%mod;
            tre[p].b=k.second%mod;
            return;
        }
        int mid=tre[p].l+tre[p].r>>1;
        if(mid>=idx) upd(idx,k,lc);
        if(mid<idx) upd(idx,k,rc);
        pushup(p);
    }
    pair<ll,ll> qry(int l,int r,int p=1){
        if(l<=tre[p].l&&r>=tre[p].r){
            return {tre[p].k,tre[p].b};
        }
        pair<ll,ll>L={1,0};
        pair<ll,ll>R={1,0};
        int mid=tre[p].l+tre[p].r>>1;
        if(mid>=l) L=qry(l,r,lc);
        if(mid<r) R=qry(l,r,rc);
        return merge(L,R);
    }   
};
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int n,m;cin>>n>>m;
    vector< pair<ll,ll> >res(n);
    Seg S(n);
    for(auto &[x,y]:res) cin>>x;
    for(auto &[x,y]:res) cin>>y;
    for(int i=0;i<n;i++) S.upd(i+1,res[i]);
    while(m--){
        int op,idx;
        ll k,b;
        cin>>op;
        if(op==1){
            cin>>idx>>k>>b;
            S.upd(idx,pair<ll,ll>{k,b});
        }
        else {
            cin>>k>>b;
            pair<ll,ll>w=S.qry(k,b);
            cout<<(w.first+w.second)%mod<<endl;
        }
    }
    return 0;
}

新人第一次在牛客写题解，更差的阅读体验:我的博客

C++

举报

收藏

赞

评论加载中...