美团codem资格赛第二题

关键词：

第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。

接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。

小美是第一个参赛者。

小美最多参赛的轮次。

4
4 1 2 3

2


由于是让第一位选手存活最长时间
所以我们可以只关心积分小于等于这位选手的选手
而这些积分小于等于它的选手，每轮结束剩下多少呢？没错是k/2
k是2的幂次，显然我们让内部决胜负，能剩下k/2个比第一位选手分数少的选手
k不是2的幂次，显然我们还是让内部决胜负最佳，因为如果每个人对阵分数高的外部选手，可以让第一位选手提前结束
观察得其答案也为k/2
综合一下，每轮剩下的人数就是k/2(比第一位选手小的
但每次/2是不对的，假如我们考虑 2 1 1 3 4 5 6 7
仅考虑 1 1，按照我们的逻辑，这个1,1可以用两次
但其实如果1,1内部决胜负，2就必须和其他比他大的比
那么第一轮就GG，所以，前提是首先从小于等于它的选手中挑一个和他比，首先保证其存活
然后让剩下的k个人内部决胜负

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 int a[1123456];
 5 int main(){
 6     int n;scanf("%d",&n);
 7     for(int i=1;i<=n;++i){
 8         scanf("%d",a+i);
 9     }
10     int x=a[1],small=0;
11     for(int i=2;i<=n;++i){
12         if(a[i]<=x) small++;
13     }
14     int ans=0;
15     while(n!=1){
16         if(small==0) break;
17         small--;//首先保证自身存活
18         small>>=1;
19         ans++;
20         n>>=1;
21     }
22     printf("%d
",ans);
23     return 0;
24 }

「美团codem资格赛」跳格子

题目描述nnn 个格子排成一列，一开始，你在第一个格子，目标为跳到第 n 个格子。在每个格子 i 里面你可以做出两个选择:选择「a」：向前跳 ai?? 步。选择「b」：向前跳 bi 步。把每步的选择写... 查看详情

codem美团点评编程竞赛资格赛题

最近看到牛课网美团一个编程竞赛，想着做做看，结果一写就是两天。。真是写不动了啊。话不多说，下面开始我的题解。题目大致还是比较考察思维和代码能力（因为自己代码能力较弱，才会觉得比较考察代码能力吧==！），... 查看详情

libreoj6048美团codem资格赛跳格子

　　题目传送门　　题目思想其实很简单，直接搜索就可以了，因为由题意可以直接转化成一幅图，比较不好处理的就是Infinity的情况，不过这题数据较水，所以就算直接暴力不加任何优化的搜索都可以拿九十分，不过如果要想... 查看详情

「题解」「美团codem资格赛」跳格子(代码片段)

目录「题解」「美团CodeM资格赛」跳格子题目描述考场思路思路分析及正解代码「题解」「美团CodeM资格赛」跳格子今天真的考自闭了...(T1)花了(2h)都没有搞定，最后无奈(90pts)。然而(T2)想到很多很奇怪的做法，结果正解在(28min)之... 查看详情

#6085.「美团codem资格赛」优惠券(代码片段)

题目描述用last[x]表示对x进行的上一次操作的位置，vis[x]表示x是否在大楼内。Splay维护‘?‘的位置。若x要进楼：1.若x已在楼内，则去找last[x]到i之间是否有‘?‘，若有，则可以把这个‘?‘当做是上一个x出楼，反之则出现错误。... 查看详情

codem2017美团点评编程大赛资格赛(代码片段)

音乐研究时间限制：C/C++1秒，其他语言2秒空间限制：C/C++32M，其他语言64M美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段... 查看详情

codem资格赛2

...制。比赛有n个人参加（其中n为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有m个人参加，那么参赛者会被分为 m/2组，每组恰好2人，m/2组的人分别厮... 查看详情

codem资格赛1

题目描述美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。具体地说，就是在第二段音频中找到一个长... 查看详情

codem资格赛补题

A：音乐研究时间限制：1秒空间限制：32768K美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。具体地说... 查看详情

组委会正在为美团点评codem大赛的决赛设计新赛制

比赛有n个人参加（其中n为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有m个人参加，那么参赛者会被分为 m/2组，每组恰好2人，m/2组的人分别厮杀。... 查看详情

codem资格赛5

早上起床太晚，最后没时间了。。不是ac代码，下次题目在oj上线的时候再去做一下。。 1#include<iostream>2#include<cstdio>3#include<cstring>4#include<vector>5#include<algorithm>6#include<cmath>7#include& 查看详情

美团笔试-第二题最大汉明距离：

题目描述　　给出n个数，求这n个数中两两最大的汉明距离，两个数的汉明距离定义维两个二进制表示中不同的位数。　　例如11和6的汉明距离为3，因为11转换为二进制后为1011，6转换为二进制后为0110，他们的二进制第1，3，4位... 查看详情

libreoj#6191.「美团codem复赛」配对游戏

二次联通门: LibreOJ#6191.「美团CodeM复赛」配对游戏    /*LibreOJ#6191.「美团CodeM复赛」配对游戏概率dp不是很懂为什么这样做。。。*/#include<cstdio>#include<iostream>constintBUF=12312312;charBuf[BUF],*buf=Bu 查看详情

「美团codem复赛」城市网络

https://loj.ac/problem/6192内存限制：64MiB  时间限制：500ms标准输入输出题目描述有一个树状的城市网络（即 nnn 个城市由 n−1n-1n−1 条道路连接的连通图），首都为 111 号城市，每个城市售卖价值... 查看详情

loj#6164.「美团codem初赛rounda」数列互质

link: https://loj.ac/problem/6164 莫队傻题，直接容斥做。 #include<bits/stdc++.h>#definemaxn100005#definepbpush_backusingnamespacestd;vector<int>g[maxn];structask intl,r,K,num,bl; bool 查看详情

libreojl6210「美团codem决赛」tree(代码片段)

难度：$\\texttt?$链接难度：\\(\\texttt?\\)有一颗\\(n\\)个点的树，每个点有权值\\(x_i\\)，定义一条简单路径的权值为\\(f(a_1\\toa_2\\to...\\toa_k)=\\fracx_a_1\\timesx_a_2\\times...\\timesx_a_kk\\)，求最小的\\(f(a_1\\toa_2\\to...\\toa_k)\\)值。数据范 查看详情

美团笔试-第二题最大汉明距离：

题目描述　　给出n个数，求这n个数中两两最大的汉明距离，两个数的汉明距离定义维两个二进制表示中不同的位数。　　例如11和6的汉明距离为3，因为11转换为二进制后为1011，6转换为二进制后为0110，他们的二进制第1，3，4位... 查看详情

美团codem数列互质-莫队(代码片段)

题目描述给出一个长度为nnn的数列a1,a2,a3,...,ana_1,a_2,a_3,...,a_na?1??,a?2??,a?3??,...,a?n??，以及mmm组询问(li,ri,ki)(l_i,r_i,k_i)(l?i??,r?i??,k?i??)，求区间[li,ri][l_i,r_i][l?i??,r?i??]中有多少数在该区间中的出现次数与kik_ik?i??互质。输入格式第一行 查看详情