9.20 %你赛

T1 link $\color{#00F000}(3.50)$

我糖丸了，想了 $\text{2h+}$ 假贪心。
这直接导致正解没时间调，交了 $O\left(n^3\right)$ 暴力上去。

看到 $n \leq 5000$ 就应该想到暴力dp。
根据某个题解，问题可转换为将原序列划分成 $m$ 个连续段，每段的和作为新序列的一个元素，要求新序列非降，且 $m$ 尽量大。
对于每个 $1 \leq i \leq n$，设 $dp_{i,0}$ 为最大段数，$dp_{i,1}$ 为满足段数最大时最后一段的最小和。
对于每个 $1 \leq i \leq n$，枚举 $1 \leq j \leq i-1$ 进行转移（具体见代码）。

时间复杂度 $O\left(n^2\right)$。

订正代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,x,y,ans,h,tmp,f[5007],g[5007][5007];
ll a[5007],s[5007],b[5007],dpa[5007][2],dpb[5007][5007];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		dpa[i][1]=117511172511762;
	}
	for(int i=1;i<=n;i++){
		dpa[i][0]=1;
		dpa[i][1]=dpb[i][1]=s[i];
		g[i][1]=0;
		for(int j=i-1;j>=0;j--){
			if(s[i]-s[j]>=dpa[j][1]){
				if(dpa[j][0]>=dpa[i][0]||
                (dpa[j][0]==dpa[i][0]-1&&s[i]-s[j]<dpa[j][1])){
					dpa[i][0]=dpa[j][0]+1;
					dpa[i][1]=s[i]-s[j];
					f[i]=j;
				}
			}
			if(dpa[j][0]<dpa[i][0]-1) break;
		}
	}
	ans=dpa[n][0];
	cout<<ans<<endl;
	x=n;
	y=ans;
	tmp=ans;
	while(x){
		b[y]=s[x]-s[f[x]];
		x=f[x];
		y--;
	}
	for(int i=1;i<=ans;i++) cout<<b[i]<<' ';
	return 0;
}

T2 link $\color{#00F0A0}(4.00)$

注意到当令红色为 $1$，蓝色为 $-1$ 时，答案为前缀和最大值减去前缀和最小值。
这题甚至没修改，所以处理完前缀和后建个ST表就完事了。

时间复杂度 $O\left(n\log(n)+q\right)$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,x,y,w,l,r,s[100007],mx[20][100007],mn[20][100007],g[100007];
char c;
int main(){
	cin>>n>>q;
	g[0]=-1;
	for(int i=1;i<=100005;i++) g[i]=g[i/2]+1;
	for(int i=1;i<=n;i++){
		cin>>c;
		if(c=='C') s[i]=s[i-1]+1;
		else s[i]=s[i-1]-1;
		mx[0][i]=mn[0][i]=s[i];
	}
	for(int i=1;i<20;i++){
		for(int j=0;j+(1<<(i-1))<=n;j++){
			mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
			mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
		}
	}
	while(q--){
		cin>>l>>r;
		w=r-l+2;
		x=max(mx[g[w]][l-1],mx[g[w]][r-(1<<g[w])+1]);
		y=min(mn[g[w]][l-1],mn[g[w]][r-(1<<g[w])+1]);
		cout<<x-y<<endl;
	}
	return 0;
}

T3 link $\color{#CCCCCC}(-)$

赛时骗了 $9$ 分跑路了。

观察题解发现：
在一个点坐标与方向确定的时候，到达的下一个点的坐标与方向一定确定，那我们把每个转弯点拆成四个方向不同的点，分别判断，那么整个图就变成了一堆简单环，那么两个点的距离就很容易得到，判断合法也只要看是不是在一个环里即可。
简单？才怪！
这代码又长又屎，我挂个TJ（代码去注释后 $\text{4KiB+}$），反正狗都不写。

T4 link $\color{#CCCCCC}(-)$

先咕咕。

总结、失误与反思

由于去年CSP-S与NOIP的T1均为贪心，导致在T1想了 $\text{2h+}$ 假贪心。
这直接导致正解没时间调，交了 $O\left(n^3\right)$ 暴力上去，$\color{#FF5500}-40$。
T2快速注意到性质从而使用好写的ST表倒很好，省得调线段树。

结论：应该在较暴力的dp行不通时在考虑贪心，上来就想贪心很可能假。