T1
题意
给定两个长度为 \(n\) 的序列 \(a,b\)，选择一个最长的区间 \([l,r]\) 使得 \(\sum\limits_{i=l}^r a_i \ge 0\) 并且\(\sum\limits_{i=l}^r b_i \ge 0\)。
输出这个区间的长度。
思路
我们记 \(s_i = \sum\limits_{j=1}^i a_j,t_i = \sum\limits_{j=1}^i b_j\)。
题目的条件即可转换为 \(s_r - s_{l-1} \ge 0\) 并且 \(t_r - t_{l-1} \ge 0\)。
不难想到，我们可以将 \(s\) 升序排序，这样我们就只需要考虑 \(t_r - t_{l-1} \ge 0\) 这个限制，直接树状数组维护即可。
复杂度是单 \(log\) 的。
代码
click
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=5e5+10;
struct node{
int a,b,id;
}a[N];
ll ans;
int n,m,T,c[N],d[N];
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
inline void add(int x,int c){
for(;x<=N;x+=lowbit(x)) d[x]=min(c,d[x]);
}
inline int sum(int x){
int res=1e18;
for(;x;x-=lowbit(x)) res=min(d[x],res);
return res;
}
inline bool cmp(node a,node b){
return a.a==b.a?a.b<b.b:a.a<b.a;
}
signed main(){
n=read();
for(register int i=0;i<N;++i) d[i]=1e9;
for(register int i=1;i<=n;++i) a[i].a=read(),a[i].a+=a[i-1].a;
for(register int i=1;i<=n;++i) a[i].b=read(),a[i].b+=a[i-1].b;
for(register int i=1;i<=n;++i) c[i]=a[i].b,a[i].id=i;
sort(c+1,c+n+1);
sort(a+1,a+n+1,cmp);
int tot=unique(c+1,c+n+1)-c-1;
for(register int i=1;i<=n;++i) a[i].b=lower_bound(c+1,c+tot+1,a[i].b)-c;
for(register int i=1;i<=n;++i){
ans=max(ans,a[i].id-sum(a[i].b));
add(a[i].b,a[i].id);
}
cout<<ans;
return 0;
}
T2
题意
给定 \(n\) 个二元组 \((a_i,b_i)\)，你可以选出任意个并且将它们任意排列，要求 \(\forall i,a_i \leq b_j\) 其中 \(j>i\)。
问最多选出多少个。
思路
不妨先选出一些下标 \(p\)，记为 \(p_1,p_2,\dots,p_n\)，这些二元组构成的序列是合法的。
然后我们考虑怎么加入 \(p_i\) 到 \(p_{i+1}\) 之间的二元组。
假设该二元组为 \((a_q,b_q)\)。
发现一定不能插在 \(p_i\) 和 \(p_{i+1}\) 之间，但是可以插在 \(p_{i+1}\) 之后，思考一下发现这就是最优情况。
然后就可以开始 \(\text{dp}\) 了。
我们设 \(dp_{i}\) 表示取到第 \(i\) 个你所能得到的最大权值。
根据刚才的贪心方法，可以得到：
\(dp_i =\max\limits_{j <i 且 b_i \ge a_j}\{ {f_j + \sum\limits_{i < k < j 且 b_k \leq a_i} w_k}\} + w_i\)。
看起来很不可做。
但是我们发现，每个 \(\sum\) 条件中的第二个约束都是一个连续的区间，可以认为，\(\forall k\) 都只对一个连续的 \(i\) 的区间产生贡献，我们只需要在开始和结束的时候加/减去 \(k\) 的贡献即可。
使用线段树维护，时间复杂度 \(O(n\log n)\)。
代码
click
别急
T3
题意
给定 \(n\) 个点，每个点有一个权值 \(v_i\)。
你要构建一颗二叉查找树使得 \(\sum\limits_{i=1}^n d_i \times v_i\) 的值最小，其中 \(d_i\) 为第 \(i\) 个点在树中的深度。
思路
显然的，一颗子树的编号在序列中一定是一个连续的区间，然后直接区间 \(\text{dp}\)。
记 \(s_{l,r} = \sum\limits_{i=l}^r v_i\)。
写出暴力的转移式：\(f_{l,r} = \max\limits_{k=l}^r \{ f_{l,k-1} + f_{k+1,r} \} + s_{l,r}\)。
上帝告诉你这个式子符合四边形不等式的性质。
你记录 \(p_{l,r}\) 是 \(f_{l,r}\) 的最优决策点。
记 \(x = p_{l+1,r},y = p_{l,r-1}\) 。
你的枚举范围就变成了 \(\max\limits_{k=x}^{y}\)。
它的复杂度是 \(\sum\limits_{l \leq r} (p_{l,r-1} - p_{l+1,r}) = \sum\limits_{l \leq n} p_{l,n}- \sum\limits_{r \ge 1} p_{1,r} = O(n)\)。
所以总复杂度就是 \(O(n^2)\)。
代码
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=5e3+10;
ll ans;
int n,m,T,dp[N][N],p[N][N],a[N],sum[N];
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
signed main(){
n=read();
for(register int i=1;i<=n;++i) a[i]=read();
for(register int i=1;i<=n;++i) sum[i]=a[i]+sum[i-1];
for(register int i=1;i<=n;++i) dp[i][i]=a[i];
for(register int i=1;i<=n;++i) p[i][i]=i;
for(register int i=1;i<=n+1;++i) dp[i][i-1]=0;
for(register int len=2;len<=n;++len){
for(register int i=1;i+len-1<=n;++i){
int j=i+len-1;
for(register int k=p[i][j-1];k<=p[i+1][j];++k){
if(dp[i][k-1]+dp[k+1][j]<=dp[i][j]){
dp[i][j]=dp[i][k-1]+dp[k+1][j];
p[i][j]=k;
}
}
dp[i][j]+=sum[j]-sum[i-1];
}
}
cout<<dp[1][n];
return 0;
}