首页 > 代码库 > code M资格赛 补题
code M资格赛 补题
A：
音乐研究
时间限制：1秒
空间限制：32768K
美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。
具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 difference 最小。两段等长音频的 difference 定义为：
difference = SUM(a[i] - b[i])2 (1 ≤ i ≤ n),其中SUM()表示求和
其中 n 表示序列长度，a[i], b[i]分别表示两段音频的音高。现在袋鼠先生想要知道，difference的最小值是多少？数据保证第一段音频的长度小于等于第二段音频的长度。
A
具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 difference 最小。两段等长音频的 difference 定义为：
difference = SUM(a[i] - b[i])2 (1 ≤ i ≤ n),其中SUM()表示求和
其中 n 表示序列长度，a[i], b[i]分别表示两段音频的音高。现在袋鼠先生想要知道，difference的最小值是多少？数据保证第一段音频的长度小于等于第二段音频的长度。
输入描述:
第一行一个整数n(1 ≤ n ≤ 1000)，表示第一段音频的长度。 第二行n个整数表示第一段音频的音高（0 ≤ 音高 ≤ 1000）。 第三行一个整数m(1 ≤ n ≤ m ≤ 1000)，表示第二段音频的长度。 第四行m个整数表示第二段音频的音高（0 ≤ 音高 ≤ 1000）。
输出描述:
输出difference的最小值
输入例子:
2 1 2 4 3 1 2 4
输出例子:
0
暴力跑就行，刚开始没看清题目写了非连续的浪费了好多时间：
红q添加了10w的数据量的解法，就是开方以后处理，并且加上FFT乘法把 $ \sum_{j=1}^{j<=n} a_i b_{i+j} $ 快速处理出来。
暴力版：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define clr(x) memset(x,0,sizeof(x)) 6 #define clrmax(x) memset(x,0x3f,sizeof(x)) 7 #define LL long long 8 using namespace std; 9 LL dp[1010][1010]; 10 LL mindp[1010]; 11 int high1[1010],high2[1010]; 12 int main() 13 { 14 int n,m; 15 clrmax(mindp); 16 mindp[0]=0; 17 clr(dp); 18 scanf("%d",&n); 19 for(int i=1;i<=n;i++) 20 scanf("%d",&high1[i]); 21 scanf("%d",&m); 22 for(int i=1;i<=m;i++) 23 scanf("%d",&high2[i]); 24 LL sum; 25 LL ans=1e18; 26 for(int j=1;j<=m-n+1;j++) 27 { 28 sum=0; 29 for(int i=j;i<j+n;i++) 30 { 31 sum+=1LL*(high1[i-j+1]-high2[i])*(high1[i-j+1]-high2[i]); 32 } 33 if(sum<ans) 34 ans=sum; 35 } 36 printf("%lld\n",ans); 37 return 0; 38 }
B：
锦标赛
时间限制：1秒
空间限制：32768K
组委会正在为美团点评CodeM大赛的决赛设计新赛制。
比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。
现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？
B
比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。
现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？
输入描述:
第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。
接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。
小美是第一个参赛者。
输出描述:
小美最多参赛的轮次。
输入例子:
4 4 1 2 3
输出例子:
2
很明显算个 $ log_2 m $是多少，其中m是分数小于等于他的选手个数（包括她自己），就是答案。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define clr(x) memset(x,0,sizeof(x)) 6 using namespace std; 7 int main() 8 { 9 int n,lower=1,mei,p; 10 scanf("%d",&n); 11 scanf("%d",&p); 12 mei=p; 13 for(int i=2;i<=n;i++) 14 { 15 scanf("%d",&p); 16 if(p<=mei) 17 lower++; 18 } 19 p=0; 20 while(lower) 21 { 22 lower/=2; 23 p++; 24 } 25 p--; 26 printf("%d\n",p); 27 return 0; 28 }
C:
优惠券
时间限制：1秒
空间限制：32768K
美团点评上有很多餐馆优惠券，用户可以在美团点评App上购买。每张优惠券有一个唯一的正整数编号。当用户在相应餐馆就餐时，可以在餐馆使用优惠券进行消费。优惠券的购买和使用按照时间顺序逐行记录在日志文件中，运营人员会定期抽查日志文件看业务是否正确。业务正确的定义为：一个优惠券必须先被购买，然后才能被使用。
某次抽查时，发现有硬盘故障，历史日志中有部分行损坏，这些行的存在是已知的，但是行的内容读不出来。假设损坏的行可以是任意的优惠券的购买或者使用。
现在问这次抽查中业务是否正确。若有错，输出最早出现错误的那一行，即求出最大s，使得记录1到s-1满足要求；若没有错误，输出-1。
C
某次抽查时，发现有硬盘故障，历史日志中有部分行损坏，这些行的存在是已知的，但是行的内容读不出来。假设损坏的行可以是任意的优惠券的购买或者使用。
现在问这次抽查中业务是否正确。若有错，输出最早出现错误的那一行，即求出最大s，使得记录1到s-1满足要求；若没有错误，输出-1。
输入描述:
m 分别表示 m (1 ≤ m ≤ 5 * 10^5) 条记录。
下面有m行，格式为：
I x （I为Input的缩写，表示购买优惠券x）；
O x（O为Output的缩写，表示使用优惠券x）；
? （表示这条记录不知道）。
这里x为正整数，且x ≤ 10^5 。
输出描述:
-1 或 x(1 ≤ x ≤ m) 其中x为使得1到x-1这些记录合法的最大行号。
输入例子:
0 1 O 1 2 ？ O 1 3 I 1 ？ O 1 2 I 2 O 1
输出例子:
-1 1 -1 -1 2
做的时候石乐志哦，没有想用set，然后手打平衡树失败。赛后补了set版。
对于未知记录，我们把它的位置插入set中，以便之后查找删除。
对于每条有效记录，使用或者获得了券x，我们先查询券X的上条记录状态，如果是与之相反的状态就变为当前状态，反之从上条记录的位置往后查询，找到第一个未知记录变为X的与现在状态相符的状态，并把这条状态的位置从set里删除。若没有找到未知状态，那么这条记录就是错误记录，这里就是最早出现错误的地方。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 #define clr(x) memset(x,0,sizeof(x)) 7 using namespace std; 8 int inf[100010],last[100010]; 9 set<int> tree; 10 set<int>::iterator it; 11 int main() 12 { 13 char c; 14 int m,p,k; 15 int mininf,flag; 16 while(scanf("%d",&m)!=EOF) 17 { 18 clr(inf); 19 clr(last); 20 tree.clear(); 21 flag=0; 22 mininf=-1; 23 for(int i=1;i<=m;i++) 24 { 25 scanf(" %c",&c); 26 if(c==‘?‘) 27 { 28 if(flag) continue; 29 tree.insert(i); 30 continue; 31 } 32 scanf("%d",&p); 33 if(flag) continue; 34 if(c==‘I‘) 35 { 36 if(inf[p]==0) 37 { 38 inf[p]=1; 39 40 } 41 else if((it=tree.lower_bound(last[p]))!=tree.end()) 42 { 43 tree.erase(it); 44 } 45 else 46 { 47 flag=1; 48 mininf=i; 49 } 50 } 51 if(c==‘O‘) 52 { 53 if(inf[p]==1) 54 { 55 inf[p]=0; 56 57 } 58 else if((it=tree.lower_bound(last[p]))!=tree.end()) 59 { 60 tree.erase(it); 61 } 62 else 63 { 64 flag=1; 65 mininf=i; 66 } 67 } 68 last[p]=i; 69 } 70 printf("%d\n",mininf); 71 } 72 return 0; 73 74 }
code M资格赛 补题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。