牛客编程巅峰赛S2第2场 记录&总结
热心的牛牛
https://ac.nowcoder.com/acm/contest/9223/A
牛客编程巅峰赛S2第2场
-> 青铜&白银&黄金
https://ac.nowcoder.com/acm/contest/9223
钻石&王者
https://ac.nowcoder.com/acm/contest/9224
2020-11-20 20:00:00 至 2020-11-20 21:00:00
时长: 1小时
AC 2/3
Rank 261/768
罚时 00:53:22
A (534/2635) 00:05:31
B (361/1170) (-5)
C (274/669) 00:47:51
A 热心的牛牛
牛牛是个非常热心的人，所以他有很多的朋友。这一天牛牛跟他的个朋友一起出去玩，在出门前牛牛的妈妈给了牛牛
块糖果，牛牛决定把这些糖果的一部分分享给他的朋友们。由于牛牛非常热心，所以他希望他的每一个朋友分到的糖果数量都比牛牛要多（严格意义的多，不能相等）。牛牛想知道他最多能吃到多少糖果？
A.1 比赛时AC
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回牛牛能吃到的最多糖果数
* @param n long长整型
* @param k long长整型
* @return long长整型
*/
long long Maximumcandies(long long n, long long k) {
// write code here
long long e=k/(n+1),m=k%(n+1);
if(m==n)return e;
return e-1;
}
};A.2 讲解1 二分法
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回牛牛能吃到的最多糖果数
* @param n long长整型
* @param k long长整型
* @return long长整型
*/
long long Maximumcandies(long long n, long long k) {
// write code here
long long left=0,right=k,ans=0;
while(left<=right){
long long mid=(left+right)/2;
if(check(n,k,mid)){
ans=mid;
left=mid+1;
}
else{
right=mid-1;
}
}
return ans;
}
bool check(long long n,long long k,long long mid){
return (__int128_t)(mid+1)*n+mid<=k;
}
};1e18
A.3 讲解2 解不等式
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回牛牛能吃到的最多糖果数
* @param n long长整型
* @param k long长整型
* @return long长整型
*/
long long Maximumcandies(long long n, long long k) {
// write code here
return (k-n)/(n+1);
}
};B 牛牛切木棒
牛牛有一根长度为的木棒，现在牛牛想将木棒分成一些段（每段木棒长度必须为整数），使得分隔后的木棍中，任意三段都不能构成三角形，牛牛想知道木棒最多被分成几段呢？
B.1 比赛时一直错误
class Solution {
public:
/**
*
* @param a long长整型 木棒的长度
* @return int整型
*/
int stick(long long a) {
// write code here
int count=2;
long long last=1,n=1,sum=2;
while(sum<=a){
n+=last;
sum+=n;
last=n;
count++;
}
//if(sum==a)return count;
return --count;
}
};知道是斐波那契数列，但是写错了。。
只有一个last 导致后面是翻倍。。
1 1 2 4 8 16.。。
B.2 讲解
class Solution {
public:
/**
*
* @param a long长整型 木棒的长度
* @return int整型
*/
int stick(long long a) {
// write code here
long long arr[61];
arr[0]=1;arr[1]=1;
for(int i=2;i<=60;i++){
arr[i]=arr[i-1]+arr[i-2];
}
long long sum=0;
for(int i=0;i<=60;i++){
sum+=arr[i];
if(sum>a){
return i;
}
}
}
};B.3 按照讲解思路写的
class Solution {
public:
/**
*
* @param a long长整型 木棒的长度
* @return int整型
*/
long long f[100]={1,1},sum=2;
int stick(long long a) {
// write code here
for(long long i=2;i<100;i++){
f[i]=f[i-1]+f[i-2];
sum+=f[i];
if(sum>=a)return i;
}
return 0;
}
};B.4 把比赛时代码修改
class Solution {
public:
/**
*
* @param a long长整型 木棒的长度
* @return int整型
*/
int stick(long long a) {
// write code here
int count=2;
long long ll=1,last=1,n,sum=2;
while(sum<a){
n=ll+last;
sum+=n;
ll=last;
last=n;
count++;
}
return count-1;
}
};一个上次last 一个上上次 ll
C Tree II
C.1 比赛时AC
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param k int整型 表示完全k叉树的叉数k
* @param a int整型vector 表示这棵完全k叉树的Bfs遍历序列的结点编号
* @return long长整型
*/
long long tree2(int k, vector<int>& a) {
// write code here
long long sum=0;
int i;
for(i;i<a.size();i++){
//if(i*k+1>=a.size())break;
if((i+1)*k>=a.size())break;
long long tmp=0;
for(int j=0;j<k;j++){
tmp+=a[i]^a[i*k+1+j];
}
sum+=tmp;
}
long long tmp=0;
for(int j=i*k+1;j<a.size();j++){
tmp+=a[i]^a[j];
}
sum+=tmp;
return sum;
}
};叉树，
的子节点为
最后一个子节点不完全的单独算。
C.2 讲解1
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param k int整型 表示完全k叉树的叉数k
* @param a int整型vector 表示这棵完全k叉树的Bfs遍历序列的结点编号
* @return long长整型
*/
long long tree2(int k, vector<int>& a) {
// write code here
int curPos=1;
int n=a.size();
long long ans=0;
queue<int> eq;
eq.push(a[0]);
while(!eq.empty()){
if(curPos==n)break;
int now=eq.front();
eq.pop();
for(int i=1;i<=k;i++){
if(curPos<n){
ans+=now^a[curPos];
eq.push(a[curPos]);
curPos++;
}
}
}
return ans;
}
};BFS中 根节点最先进队
- 找到当前节点
- 连接所有儿子
C.3 更优雅一点
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param k int整型 表示完全k叉树的叉数k
* @param a int整型vector 表示这棵完全k叉树的Bfs遍历序列的结点编号
* @return long长整型
*/
long long tree2(int k, vector<int>& a) {
// write code here
long long ans=0;
int n=a.size();
int curPos=1;
for(int i=0;i<n;i++){
if(curPos==n)break;
for(int j=0;j<k;j++){
if(curPos<n){
ans+=a[i]^a[curPos];
curPos++;
}
}
}
return ans;
}
};- 出队
- 找下一个点儿子
D 数据分析
作为一个优秀的程序员，牛牛喜欢钻研各种技术。最近，牛牛就在研究数据分析有关技术。
牛妹给了牛牛一批商品销量数据，想让牛牛帮忙分析。作为经典的指标，一段时间内的最高销量是一个很好的研究起点，牛牛就打算研究某个长度的子数组中的最高销量中的最小值。
举例子来说，考虑销量序列 [1,3,5,2,4,6]，我们考虑长度为 3 的子数组，从左到右分别为[1,3,5],[3,5,2],[5,2,4]和[2,4,6]，最高销量分别为[5,5,5,6] ，最高销量中的最小值为 5。
然而，牛妹觉得这个仍然不是很直观，她提出了一个更进一步的问题：能不能找出 中每个长度的子数组中最高销量的最小值？举例子来说，对于 [1,3,5,2,4,6]，我们已经求出来了 k=3 时候的最小值为 5，牛妹还想要其他长度的最小值。
虽然牛牛对数据很敏感，但是解决这个问题对他来说还是有点困难了，希望你能完善函数，帮他解决这个问题。牛牛将把这 N 个销量数据给你，你需要返回一个长度恰好为 N 的序列，第一个元素为长度为 1 的答案，第二个元素为长度为 2 的答案，以此类推。
D.1 讲解
class Solution {
public:
/**
* 找到所有长度子数组中最大值的最小值
* @param numbers int整型vector 牛牛给出的数据
* @return int整型vector
*/
vector<int> getMinimums(vector<int>& numbers) {
// write code here
int n=numbers.size();
vector<int> right(n,n),left(n,-1);
stack<int> st;
for(int i=0;i<n;i++){
while(!st.empty()&&numbers[st.top()]<numbers[i]){
right[st.top()]=i;
st.pop();
}
if(!st.empty()){
left[i]=st.top();
}
st.push(i);
}
vector<int> ans(n,0x3f3f3f3f);
for(int i=0;i<n;i++){
int len=right[i]-left[i]-1;
ans[len-1]=min(ans[len-1],numbers[i]);
}
for(int i=n-2;i>=0;i--){
ans[i]=min(ans[i],ans[i+1]);
}
return ans;
}
};单调栈
类似
查看26道真题和解析
