Acwing第50场周赛报告

得分情况

（由于时间原因，只能腾出中午来做题，所以只写了前四道）

T1：100

T2：100

T3：100

T4：0

错题分析

T3：DP

时间复杂度：O（n^3）
要三重循环所有维度的变量

T4：数学

时间复杂度：O（n）
(s[r] - s[0, r - 1]) % k = 0, 当这个条件成立答案就加一。

代码

T1

#include<iostream>
using namespace std;

int main(){
    long long sum=1；
    long long tot=0;
    int n,x;
    cin >> n;
    for(int i = 2;i <= n;i++)
        cin >> x,sum+=i,tot+=x;
    cout << sum-tot<<endl;
    return 0;
}

T2

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int INF = 1e9;
int a[N];

int main(){
    int n,m;
    int res = 0;
    cin >> n;
    int a =INF;
    int b = -INF;
    for(int i = 0; i < n; i ++){
        int l,r;
        cin >> l >> r;
        a = min(a,r); 
        b = max(b,l);
    }
    cin >> m;
    for(int i = 0; i < m ; i++){
        int l,r;
        cin >> l >> r;
        res = max(res,l-a);
        res = max(res,b-r);
    }
    cout <<res<<endl;
}

T3

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long a[205],f[205][205];
    memset(f,-0x3f,sizeof(f));
    int n,k,x;
    cin >>n>>k>>x;
    for(int i = 1;i<=n;i++) cin >> a[i];
    f[0][0]=0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=x;j++){
            for(int t = max(0,i-k);t<i;t++){
                f[i][j]=max(f[i][j],f[t][j-1]+a[i]);
            }
        }
    }
    long long ans=-1;
    for(int i = n-k+1;i<=n;i++) ans=max(ans,f[i][x]);
    cout <<ans<<endl;

    return 0;
}