您现在的位置是:首页 >技术教程 >牛客小白月赛65网站首页技术教程
牛客小白月赛65
A-牛牛去购物(枚举)
题目描述
牛牛带着 n n n元钱去超市买东西,超市一共只有两款商品,价格为 a a a元的篮球和价格为 b b b元的足球,牛牛想把手里的钱尽可能花光,请问牛牛最少能剩多少钱?
输入描述:
输入一行,三个正整数 n , a , b ( 1 ≤ n , a , b ≤ 1000 ) n,a,b (1 leq n,a,b leq 1000) n,a,b(1≤n,a,b≤1000), n n n表示牛牛现有的钱数, a a a表示一个篮球的单价, b b b 表示一个足球的单价。
输出描述:
输出一行一个整数,代表牛牛最少能剩下的钱数。
题解:
枚举每种情况取剩下的最下钱数即可
#include <iostream>
#define int long long
using namespace std;
inline int min(int a,int b){return a>b?b:a;}
void solve(){
int n,a,b;
cin>>n>>a>>b;
int ans=n;
for(int i=0;i<=n/a;i++){
for(int j=0;j<=n/b;j++){
int x=n-a*i-b*j;
if(x>=0){
ans=min(ans,x);
}
}
}
cout<<ans;
}
signed main(void){
int _=1;
//cin>>_;
while(_--)solve();
return 0;
}
当然也可以简化代码
直接遍历花钱数从买0个篮球遍历到买n/a个篮球即可
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,a,b,big=200000;
cin>>n>>a>>b;
for(int i=0;i<=n;i+=a)
big=min(big,(n-i)%b);
cout<<big;
return 0;
}
B-牛牛写情书(字符串)
题解:
遍历选取出原字符串中所有小写字母,然后再直接找字串即可
如果没找到输出NO
#include <iostream>
#define int long long
using namespace std;
inline int min(int a,int b){return a>b?b:a;}
void solve(){
int n,m;cin>>n>>m;
string k,s;
cin>>s>>k;
string ss;
for(int i=0;i<s.size();i++)
if(s[i]>='a'&&s[i]<='z')
ss+=s[i];
if(ss.find(k)==string::npos)cout<<"NO";
else cout<<"YES";
}
signed main(void){
int _=1;
//cin>>_;
while(_--)solve();
return 0;
}
C-牛牛排队伍(模拟)
示例1
输入
5 4
2 1
1 3
2 5
2 4
输出
0
4
2
题解:
其实就是一个队伍或者是队列。
那么叫走一个就要改变当前队列后一个的前者。
但因为叫走顺序不定,所以我们不仅要记录当前队列每位的前一位是谁,还要记住后一位是谁。
如果单纯用bool数组去记录当前位走没走,后续遍历很耗时间,直接TLE
其实就是双链表
#include <iostream>
#define int long long
using namespace std;
inline int min(int a,int b){return a>b?b:a;}
inline int read(){
int ans=0;
int f=1;char ch;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')f=-1;
do ans=(ans<<3)+(ans<<1)+(ch^48); while((ch=getchar())>='0'&&ch<='9');
return f*ans;
}
const int N = 1e6+10;
int b[N];
int a[N];
void init(int n){
for(int i=1;i<=n;i++){
a[i]=i-1;
b[i]=i+1;
}
}
void solve(){
int n=read(),k=read();
init(n);
while(k--){
int chose=read(),x=read();
if(chose==1){
a[b[x]]=a[x];
b[a[x]]=b[x];
}
else if(chose==2){
printf("%d
",a[x]);
}
}
}
signed main(void){
int _=1;
//cin>>_;
while(_--)solve();
return 0;
}
D-牛牛取石子(博弈)
示例1
输入
2
1 2
3 3
输出
niuniu
niumei
题解:
一开始看这道题,想着直接博弈,打一个巴什游戏的输赢条件即可。
后面想着又没那么简单,有两堆,其实决定胜负的是少石头的那一堆。
就加了一个判断和交换。
后面还是错的
这题的特例就是两堆石头相同的情况
下面是特例考虑:
考虑4和4:先手操作后,得到3和2,后手拿1和2,剩下2和0,先手败。
其实上面的分析默认了一个条件:针对最小堆进行策略操作后不会改变原来两堆的相对大小,而当两堆相等时:模3得1时:还是上面的例子,4和4,令另第一个4为较小值,先手要将其变为3的倍数,选择操作1,变为的3和2改变了一开始的“大小关系”,这时不是第一堆最小了,而是第二堆的2,2模3不为0,这对后手而言是“必胜态”。
模3得2时:例如5和5,令第一个5为较小值,进行操作2,变为3和4,仍是第一堆较小,未改变大小关系,先手赢。
#include <iostream>
#define int long long
using namespace std;
void solve(){
int a,b;cin>>a>>b;
if(a>b)swap(a,b);
if(a%3==0||(a==b&&a%3==1))cout<<"niumei
";
else cout<<"niuniu
";
}
signed main(void){
int _=1;
cin>>_;
while(_--)solve();
return 0;
}
E-牛牛的构造(构造,思维)
题解:
注:以下出现运算全都向下取整
如果考虑最大全排列,如果一个数 x x x放在前面,那么后面就有 x − 1 x-1 x−1个比他小的数,那么该数字能到达 k k k提供 l o g 2 ( i ) log_2(i) log2(i)个值,直接从大到小遍历,如果最大全排列无法满足 k k k就输出-1
如果能满足,例如需要 l o g 2 ( x ) log_2(x) log2(x)个贡献,那么就把 x x x放在 0 到 ( x − 1 ) 0到(x-1) 0到(x−1)的前面,使得式子可以成立, x x x可以做出 l o g 2 ( x ) log_2(x) log2(x),如果贡献值刚好到了 k k k,那么这个数组就是存在的,因为考虑贡献是从最大的开始,那么队列就是从最大的开始放,最后放入数组的时候直接放就可以了,就可以保证小于其值的数字都在后面,当然,我们仅仅需要队列里面的值提供贡献,那么就表明如果没有进队列的值贡献一定为 0 0 0,那么最后就正向遍历没有出现过的即可,这样出来的剩余值,小的在前面大的在后面,通过题目式子运算,一定为负数,不可能有贡献!!!
#include <iostream>
#include <queue>
#include<vector>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6+10;
//int a[N];
vector<int>a;
queue<int >q;
bool b[N];
void init (int n);
void Print(int n){
int flag=1;
for(int i=0;i<a.size();i++){
if(flag)cout<<a[i];
else cout<<' '<<a[i];
flag=0;
}
}
void solve(){
int n,k;
cin>>n>>k;
//init(n);
// if(k>(n-1)*n/2){
// cout<<-1;return ;
// }
for(int i=n;i>=1;i--){
if(k>=log2(i)){
q.push(i);
k-=log2(i);
}
if(k==0)break;
}
if(k>0){cout<<-1;return ;}
while(!q.empty()){
int x=q.front();
b[x]=true;
a.push_back(x);
q.pop();
}
for(int i=1;i<=n;i++){
if(b[i]==false)a.push_back(i);
}
Print(n);
}
void init (int n){
// for(int i=n;i>=1;i++){
// a[i]=i;
// }
a.resize(n+1);
}
signed main(void){
int _=1;
//cin>>_;
while(_--)solve();
return 0;
}