code M资格赛补题

A：

音乐研究

时间限制：1秒

空间限制：32768K

美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。

具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 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的最小值

输入例子:

输出例子:

暴力跑就行，刚开始没看清题目写了非连续的浪费了好多时间：
红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
",ans);
37     return 0;
38 }

B：

锦标赛

时间限制：1秒

空间限制：32768K

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

比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。

现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？

输入描述:

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

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

小美是第一个参赛者。

输出描述:

小美最多参赛的轮次。

输入例子:

4
4 1 2 3

输出例子:

很明显算个 $ 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
",p);
27     return 0;    
28 }

优惠券

时间限制：1秒

空间限制：32768K

美团点评上有很多餐馆优惠券，用户可以在美团点评App上购买。每张优惠券有一个唯一的正整数编号。当用户在相应餐馆就餐时，可以在餐馆使用优惠券进行消费。优惠券的购买和使用按照时间顺序逐行记录在日志文件中，运营人员会定期抽查日志文件看业务是否正确。业务正确的定义为：一个优惠券必须先被购买，然后才能被使用。

某次抽查时，发现有硬盘故障，历史日志中有部分行损坏，这些行的存在是已知的，但是行的内容读不出来。假设损坏的行可以是任意的优惠券的购买或者使用。

现在问这次抽查中业务是否正确。若有错，输出最早出现错误的那一行，即求出最大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
",mininf);
71     }
72     return 0;
73      
74 }

送外卖

时间限制：1秒

空间限制：32768K

n 个小区排成一列，编号为从 0 到 n-1 。一开始，美团外卖员在第0号小区，目标为位于第 n-1 个小区的配送站。
给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ，在每个小区 i 里你有两种选择：
1) 选择a：向前 a[i] 个小区。
2) 选择b：向前 b[i] 个小区。

把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中，字典序最小的字符串。如果做出某个选择时，你跳出了这n个小区的范围，则这个选择不合法。
• 当没有合法的选择序列时，输出 “No solution!”。
• 当字典序最小的字符串无限长时，输出 “Infinity!”。
• 否则，输出这个选择字符串。

字典序定义如下：串s和串t，如果串 s 字典序比串 t 小，则
• 存在整数 i ≥ -1，使得∀j，0 ≤ j ≤ i，满足s[j] = t[j] 且 s[i+1] < t[i+1]。
• 其中，空字符 < ‘a’ < ‘b’。

输入描述:

输入有 3 行。

第一行输入一个整数 n (1 ≤ n ≤ 10^5)。

第二行输入 n 个整数，分别表示 a[i] 。

第三行输入 n 个整数，分别表示 b[i] 。

−n ≤ a[i], b[i] ≤ n

输出描述:

输出一行字符串表示答案。

输入例子:

7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0

输出例子:

abbbb

为什么会无限长呢？最朴素的例子：从1号点选择a方案可到3号点，3号点选择a方案可到2号点，b方案可到n-1号点，那你肯定选择aaaaaaa……（无穷）b这样字典序最小，而不是ab或者aaab等等这样的方案，因为这样的方案字典序不是最小的。

那么解法显而易见：

这道题从n-1号点反向dfs下，找出所有能到达n-1的点，标记下。然后看看0号点能到达n-1号点吗，不能就 no solution。

然后从0号点出发也做一遍dfs，这个dfs是先选a方案在选b方案的，并且标记经过的点。若在dfs中遇到标记点，并且该标记点可达n-1号点（前面的dfs已经找出这些点了），那么中便是无限长的方案。否则就退出继续dfs直到找到一个可到达n-1号点的方案。该方案就是有限长最终方案。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define clr(x) memset(x,0,sizeof(x))
 5 #define clr_1(x) memset(x,-1,sizeof(x))
 6 using namespace std;
 7 int a[100010],b[100010];
 8 char s[100010];
 9 int head[100010],size,inf[100010],inf2[100010],n;
10 struct edg
11 {
12     int next,to;
13 }edge[200010];
14 void addedge(int u,int v)
15 {
16     edge[++size].to=v;
17     edge[size].next=head[u];
18     head[u]=size;
19     return ;
20 }
21 void dfs1(int u)
22 {
23     inf[u]=1;
24     int p;
25     for(int i=head[u];i!=-1;i=edge[i].next)
26     {
27         p=edge[i].to;
28         if(inf[p]==0)
29             dfs1(p);
30     }
31     return ;
32 }
33 int dfs2(int u,int dep)
34 {
35     if(u==n-1)
36     {
37         s[dep]='';
38         printf("%s
",s);
39         return 0;
40     }
41     if(inf2[u]==1)
42     {
43         if(inf[u]==1)
44         {
45             printf("Infinity!
");
46             return -1;
47         }
48         else
49             return 1;
50     }
51     inf2[u]=1;
52     int k=1;
53     if(u+a[u]<=n-1 && u+a[u]>=0)
54     {
55         s[dep]='a';
56         k=dfs2(u+a[u],dep+1);
57     }
58     if(k>0 && u+b[u]<=n-1 && u+b[u]>=0)
59     {
60         s[dep]='b';
61         k=dfs2(u+b[u],dep+1);
62     }
63     return k;
64 }
65 int main()
66 {
67     size=0;
68     scanf("%d",&n);
69     clr_1(head);
70     clr(inf);
71     for(int i=0;i<n;i++)
72     {
73         scanf("%d",&a[i]);
74         if(i+a[i]<=n-1)
75             addedge(i+a[i],i);
76     }
77     for(int i=0;i<n;i++)
78     {
79         scanf("%d",&b[i]);
80         if(i+b[i]<=n-1)
81             addedge(i+b[i],i);
82     }
83     dfs1(n-1);
84     if(inf[0]==0)
85         printf("No solution!
");
86     else
87     {
88         clr(inf2);
89         clr(s);
90         dfs2(0,0);
91     }
92     return 0;
93 
94 }

E：

数码

时间限制：1秒

空间限制：32768K

给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。

输入描述:

一行，两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9)。

输出描述:

输出9行。

第 i 行，输出数码 i 出现的次数。

输入例子:

1 4

输出例子:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #define clr(x) memset(x,0,sizeof(x))
 6 #define LL long long
 7 using namespace std;
 8 LL n,m,l,r;
 9 LL min(LL a,LL b)
10 {
11     return a<b?a:b;
12 }
13 LL max(LL a,LL b)
14 {
15     return a>b?a:b;
16 }
17 LL sum(LL n,LL m)
18 {
19     LL sqrtn=(LL)sqrtl(n);
20     LL ans=0;
21     LL k=n/(sqrtn+1),beg=n/(k+1);
22     for(LL i=1;i<=min(beg,m);i++)
23         ans+=n/i;
24     if(beg>=m)
25     {
26 //        printf("%d %d %d
",n,m,ans);
27         return ans;
28     }
29     for(LL i=k;i>=n/m;i--)
30     {
31         ans+=i*(min(m,n/i)-n/(i+1));
32     }
33     return ans;
34 }
35 LL deal(int p,LL n)
36 {
37     LL q;
38     LL ans=0,ten=1;
39     for(int i=1;i<=10;i++)
40     if((LL)p*ten-1<n)
41     {
42         ans+=sum(n,min((LL)(p+1)*ten-1,n))-sum(n,(LL)p*ten-1);
43         ten*=10;
44     }
45     return ans;
46 }
47 int main()
48 {
49     scanf("%lld%lld",&l,&r);
50     for(int i=1;i<=9;i++)
51     {
52         LL ans=deal(i,r)-deal(i,l-1);
53         printf("%lld
",ans);
54     }
55     return 0;
56 }