昨天也是理完发赶回来打的这场比赛，可惜头发剪毁了，但是打的还不错，算是因祸得福（？

这是我第一次在八千多人参赛的情况下获得137名的成绩，虽然不是特别好，但是对我来说很开心了

A题

很简单的思想，移项得到差分数组，维护并更新答案就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
using ll=long long;
const int N=1e5+20;
ll a[N],d[N];
int main()
{
  // 请在此输入您的代码
  ll n;cin>>n;
  for(ll i=1;i<=n;i++){
    cin>>a[i];
    d[i]=a[i]-a[i-1];
   
  }
  ll ans=0;
  for(int i=2;i<=n-1;i++){
     if((a[i+1]<=d[i]))ans++;
  }
  cout<<ans;
  return 0;
}

B题

这道题很简单，一个贪心的思想，尽量在最高位放大的数字，最多只能放9，多余的放在次高位，以此类推

需要注意的是，给的m是有可能大于你最多能表示的数字的，因为要求是f（x）<=M，所以要在9*n和m里取min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include<string.h>
#include<cmath>
using namespace std;
using i64=long long;
int main()
{
  // 请在此输入您的代码
  i64 n,m;
  cin>>n>>m;
  string s="";
  m=min(m,n*9);
  while(m>=10){
    s+=to_string(9);
    m-=9;
  }
  s+=to_string(m);
  while(s.size()<n){
    s+="0";
  }
  cout<<s;
  return 0;
}

C题

一道升级的最大字段和，那我们可以预处理一下，一个线性筛求出所有质数，再以所有质数为子数组的长度取答案，取的时候可以利用一个前缀和做到O（1）的查询。需要注意的是在预处理质数的时候N最好开大一点，因为线性筛的特性有时会导致一些合数没有被筛掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=2e5+10;
using i64=long long;
vector<int>prime;
bool vis[N];
i64 a[N],pre[N];
int main()
{
  memset(vis,1,sizeof vis);
  // 请在此输入您的代码
  i64 n;cin>>n;
  for(int i=2;i<=n;i++){
    if(vis[i])prime.push_back(i);
    for(int j=0;j<prime.size()&&i*prime[j]<=N;j++){
      vis[i*prime[j]]=0;
      if(i%prime[j]==0)break;
    }
  }
  for(int i=1;i<=n;i++){
    cin>>a[i];
    pre[i]=pre[i-1]+a[i];
  }
  i64 ans=-0x3f3f3f3f;
  for(auto &e:prime){
    if(e>n)break;
    for(i64 i=1;(i+e-1)<=n;i++){
      ans=max(ans,pre[i+e-1]-pre[i-1]);
    }
  }
  cout<<ans;
  return 0;
}