2023牛客寒假算法基础集训营5

(0条未读通知) 【题解】2023牛客寒假算法基础集训营5_ICPC/CCPC/NOIP/NOI刷题训练题单_牛客竞赛OJ (nowcoder.com)

A-小沙の好客

 下面是错误代码我刚开始看到这题觉得很简单阿做了才知道会超时所以不能单纯的去做而是加上一些思维。

#include<bits/stdc++.h>
using namespace std;
bool cmp(int x,int y){
    return x>y;
}
int main(){
    int n,q,k,x,i,a[100005],y;
    cin>>n>>q;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n,cmp);
    while(q--){
        y=0;
        cin>>k>>x;
        for(i=0;i<n;i++){
            if(k==0)break;
            if(a[i]<=x){y+=a[i];k--;}
        }
        cout<<y<<endl;
    }
    return 0;
}

//下面给出正确代码

//参考了题解讨论的博主代码

//核心是前缀和以及二分upper_bound( begin,end,num)从数组的begin位置到end-1位置二分查找第一个大于num的数字找到返回该数字的地址不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

关于lower_bound( )和upper_bound( )的常见用法_brandong的博客-CSDN博客_upper_bound

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int n,q,k,x,a[100005],b[100005],i,z,y;
    cin>>n>>q;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    b[0]=0;
    for(i=0;i<n;i++)b[i+1]=b[i]+a[i];
    while(q--){
        cin>>k>>x;
        z=0;
        y=upper_bound(a,a+n,x)-a;
         if(y<k)
             z=b[y];
        else z=b[y]-b[y-k];
        cout<<z<<endl;
    }
    return 0;
}

 

B-小沙の博弈

链接登录—专业IT笔试面试备考平台_牛客网
来源牛客网
 

小沙和小雅在玩"拿石子游戏"他们两个人都十分聪明均会选择最优的方法使得自己获胜。桌子上有 nnn 个石子 他们两个人面前均有排成一行的若干个格子每个格子都可以置放无限多个石子。

小沙和小雅两个人交替进行操作小沙先行每次操作可以从桌子上拿走任意正整数个石子将其置放于自己面前第一个没有石子的格子里。

当桌上的石子数为 000 时游戏结束按照两人格子中石子数目组成序列的字典序判断胜负字典序小的人获胜。

字典序你有两个序列 aaa 和 bbb 两个序列从前往后第一个不相同的字符分别为 aia_iai​ , bib_ibi​ 如果 ai<bia_i < b_iai​<bi​ 那么我们称序列 a<ba < ba<b 。如果两个序列完全相同那么他们的字典序相等。

输入描述:

第一行输入一个整数 nnn 1≤n≤1051 \leq n \leq 10^51≤n≤105。

输出描述:

输出一行字符串。

当小沙获胜时输出字符串"Sajin-win!"(不含引号)。

当小雅获胜时输出字符串"Yaya-win!"(不含引号)。

如果两个都没有获胜那么输出字符串"win-win!"(不含引号)。

示例1

输入

复制2

2

输出

复制win-win!

win-win!

说明

小沙先手拿一个小雅在拿一个石子被用完了他们的序列分别为

1

1

字典序相同所以平局。

示例2

输入

复制3

3

输出

复制Yaya-win!

Yaya-win!

//如果n是偶数那么结果一定是平局题目已经说了他们两个人都十分聪明均会选择最优的方法使得自己获胜其次就是小雅获胜因为奇数情况下小沙一定会比小雅多取以此而题目是小数获胜可以自己尝试多举几个例子。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n%2==0)cout<<"win-win!";
    else cout<<"Yaya-win!";
    return 0;
}

 

H-小沙の店铺

//同样先给出错误代码便于对比。首先来说根据输入描述那么y=1k=2但又与样例说明不符所以应该是y=2k=1广播也说了对此题样例说明做了更正不过我始终没理解样例说明的最后一条为什么最后只涨价了一元。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long x,y,k,n,t,s=0,a=0,b=0;
    cin>>x>>k>>y>>n>>t;
    for(int i=n;i>=1;i--){
        s+=i*x;b++;
        if(s>=t){a=1;break;}
        if(i>k)x+=y;
    }
    if(a)cout<<b;
    else cout<<"-1";
    return 0;
}

//后面发现从根本上就理解错了题目注意是每卖出k件就上涨y元我们解释样例n=5最开始x=10第一个顾客买了5此时收益b=50元然后每卖出2件涨价1元现在卖出5件所以涨价2元并且遗留一件到第二个顾客时他买了4件每件x=12所以又收益48加上之前剩的一件现在卖出去5件同样涨价2元第三个顾客买了3件每件x=14又收益42加上前面剩的一件现在卖出去四件同样涨价2元第四个顾客买了2件每件x=16又收益32此时收益已经等于t了我们不妨继续解释此时卖出去2件所以只涨价1元所以x=17.

b是统计当前总收益d统计顾客数a用来标记z=当前顾客购买量加上上一个顾客剩余量除以k可以把z理解为涨价的倍率c是每次剩余数。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long x,y,k,n,t,a=0,b=0,i,z=0,c=0,d=0;
    cin>>x>>y>>k>>n>>t;
    for(i=n;i>=1;i--){
        b+=i*x;d++;
        if(b>=t){a=1;break;}
        z=(i+c)/k;
        c=i+c-z*k;
        x+=z*y;
    }
    if(a)
    cout<<d;
    else cout<<"-1";
    return 0;
}

K-小沙の抱团 easy

// 要使最后的人数最少这个数其实可以确定是2那么每次淘汰人数就应该较一半多一点。

我的代码错在了两个点第一n=1和n=2的情况之间输出0虽然最开始我是这样写的但在后面我改成了1这点是源于越找越错就是我感觉其他部分代码没问题的情况下产生了这部分代码的质疑第二输出应该在else内如果这点对了估计前面第一点错误也不会继续了如果这点不对则只会通过百分之98的样例因为1和2已经输出0再输出0就无法通过通过代码部分可以进行优化。

//优化代码

//错误代码 

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,x,y=0;
    cin>>n;
    x=n;
    if(n==2||n==1)cout<<"1";
    else {
        while(n!=2){
            if(n%2==0)x=(x+2)/2;
            else x=(x+1)/2;
            n=x;
            y++;
        }
    }cout<<y;
    return 0;
}

//正确代码 

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,x,y=0;
    cin>>n;
    x=n;
    if(n==2||n==1)cout<<"0";
    else {
        while(n!=2){
            if(n%2==0)x=(x+2)/2;
            else x=(x+1)/2;
            n=x;
            y++;
        }
        cout<<y;
    } 
    return 0;
}