9.15 杂题选讲

难度还算良心吧。

当然每次都是 CDW 虐场……

---

T1

这题是我讲的，题解在这

T2

看到 [ZJOI2019] 就知道是谁的了吧。先咕了。

T3

全场最简单的题，而且才 1900，所以没有另开一篇，直接贴代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=300030;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
int n,m,k,a[maxn];
ll s[maxn],v[maxn],val[10],ans;
int main(){
    n=read();m=read();k=read();
    FOR(i,1,n){
        a[i]=read();
        s[i]=s[i-1]+a[i];
        v[i]=s[i]-1ll*k*(i/m);
    }
    MEM(val,0x3f);
    val[0]=0;
    FOR(i,1,n){
        FOR(j,0,m-1) ans=max(ans,ll(v[i]-val[j]-1ll*k*((i%m-j+m-1)/m)));
        val[i%m]=min(val[i%m],v[i]);
    }
    cout<<ans<<endl;
}

T4

不得不说 ZSD 还是很好的讲题人。

链接在这

T5

这 CXG 怎么讲 DP 不带解释转移方程的啊……

还有高精，那么在路上了。