3.31考试题解及总结

Noip难度的题目还翻车，真的是菜出了天际。自己最近思维出现问题.静不下心来

T1

很明显的套路题，转化为差分数组.我们可以花费\(1\)的代价来对一个一个位置\(+1\)另一个位置\(-1\).最后统计一下大于\(k\)的之和与小于\(-k\)的差值之和取个\(max\)就好了

#include<cstdio>
#include<iostream>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long 
using namespace std;
const int N = 3e5 + 3;
LL ans;
LL n,k;
LL sum[N],a[N];
inline LL read(){
    LL v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar(); 
    }
    return v * c;
}
int main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    n = read(),k = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= n + 1;++i) sum[i] = a[i] - a[i - 1];
    LL sum1 = 0,sum2 = 0;
    for(int i = 1;i <= n + 1;++i){
        if(sum[i] > k) sum1 += sum[i] - k;
        else if(sum[i] < -k) sum2 += (-k - sum[i]);
    }
    printf("%lld\n",max(sum1,sum2));
    return 0;   
}   

T2

SB DP题目,结果考场上写了一个SB贪心,喜提20

这道题开到\(500000\)，但暴力枚举质因子就可以过掉了.时间复杂度\(O(n\sqrt{n})\)

然后由于垃圾lemon默认不开栈又喜提50,开栈之后A掉。

总结：考试浮躁静不下心来做题，不认真思考。以后考试不到收卷不开小差，认真思考题目

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 5e5 + 3;
int f[N];
int n,T;
inline int dp(int x){
    if(f[x] != -1) return f[x];
    f[x] = 2e9;
    for(int i = 2;i * i <= x;++i)
    if(x % i == 0)
    f[x] = min(f[x],min(dp(x - i) + 1,dp(x - (x / i)) + 1));
    f[x] = min(f[x],dp(x - 1) + 1);
    return f[x];
}
int main(){
    scanf("%d%d",&T,&n);
    memset(f,-1,sizeof(f));
    f[1] = 0;
    while(T--){
        int x;scanf("%d",&x);
        if(x < 1){printf("Impossible\n");continue;}
        printf("%d\n",dp(x));   
    }
    return 0;
}    

T3

先咕一咕,学完分治NTT再回来补

3.31考试总结

原文：https://www.cnblogs.com/wyxdrqc/p/10632528.html