T1 填数游戏

10%

爆搜答案即可。

另外30%

意味着每个数都要填到格子里，那么有一个很直观的贪心想法，大的数匹配大的数，小的数匹配 小的数就可以使答案最大了。

50%

主要要意是鼓励选手思考比较简单的 做法。 可以做 的前缀 max 优化 dp 做法。可以拿到 50 分。

100%

考虑另外 30% 的贪心。但是因为有一些数可以不选的，所以可以把数分为大于 0 和小于 0 的。

首先肯定是负数和负数匹配，正数和正数匹配。然后余下的数按照大的和大的匹配，小的和小的匹配的原则匹配即可。

复杂度 ，注意开 longlong。

T2 摆渡车

权值线段树。

显然会选取 中数字最小的若干个数字，若对每个 都对 重新排序，或者使用插入排序后再统计答案，期望得分为 30 分。

但注意到第 4 第 5 个数据点 M 小于等于 100，所以我们使用插入排序时可以只维护前 100 个数字（若存在 的特殊处理）的排序后的结果就好，期望得分 50 分。

满分做法可以使用权值线段树，线段树上每个结点维护对应权值区间范围内有多少个数字以及这些数字的和是多少，查询时每次判断左子树对应区间范围内有多少数字，相加后的和是否超过限制，超过则向左递归否则向有递归。时间复杂度 ，期望得分 100 分。

T3 分糖果

做法：二分+DP+离散化+树状数组

要求最大的最小，第一时间想到二分。关键在于二分答案 后怎么判断。

当 时，显然只需要看一下是否存在某个前缀和小于等于 即可。期望得分 20 分。

当 时，我们可以使用 DP 来解决。用 表示前 个数字中，最多可以分成多少段，使得每一段的和都小于等于 。若存在 ，则 是可行解，往小的范围继续二分，否则 不合法，往大的范围继续二分。转移方程如下：

, 其中 ， 数组为数列 的前缀和数组，正确性显然。时间复杂度为 ，结合 的情况，期望得分 50 分。

我们发现上面这个 DP 很慢，而且主要是状态转移太慢了，我们来思考如何优化状态转移。当 和 固定时，符合条件的 就是那些满足 的 ，而转移时就是在这些符合条件的 里面找一个 的最大值。很容易想到使用数据结构来优化。

理论上我们可以使用权值线段树，但这里由于 的范围很大，其部分和 的范围就更大了，使用权值线段树容易超时。而且我们发现 是已知的且不变的，所以我们使用预处理离散化+树状数组会更好：先预处理出 数组，然后从大到小排序后离散化，建立树状数组记录对应前缀和大小为 时，最大的 是多少。那么接下来每次查询时就是查询树状数组中某个前缀的最大值。 时间复杂度为 。期望得分 100 分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn=2e5+5;
ll a[maxn],f[maxn];
 
int bit[maxn*2+100];
void update(int x,int d){
    for(int i=x;i>0;i-=i&-i) bit[i]=max(bit[i],d);
}
int querysuf(int x,int B){
    int ret=-1e9;
    for(int i=x;i<B;i+=i&-i) ret=max(bit[i],ret);
    return ret;
}
void remove(int x,int B){
    for(int i=x;i<B;i+=i&-i) bit[i]=-1e9;
    for(int i=x;i>0;i-=i&-i) bit[i]=-1e9;
}
 
vector<ll> disc;
int getid(ll x){return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;}
 
bool check(ll ans,int n,int k){// sum<=ans
    disc.clear();
    for(int i=1;i<=n;i++) {
        disc.push_back(a[i]);
        disc.push_back(a[i]-ans);
    }
    disc.push_back(0);
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());
 
    for(int i=1;i<=disc.size();i++) remove(i,disc.size());
    f[0]=0;
    update(getid(0),f[0]);
    for(int i=1;i<=n;i++) {
        f[i]=querysuf(getid(a[i]-ans),disc.size()+1)+1;
        update(getid(a[i]),f[i]);
        if(f[i]>=k) return true;
    }
    return false;
}
 
int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) {
            scanf("%lld",a+i);
            a[i]+=a[i-1];
        }
        ll l=-1e9*1e6,r=1e9*1e6;
        while(l+1<r){//  ans -> ( ]
            ll mid=(l+r)/2;//
            if(check(mid,n,k)) r=mid;//
            else l=mid;
        }
        printf("%lld\n",r);
    }
    return 0;
}

T4 宝石加工

首先考虑单组询问怎么做。

定义 表示已经考虑完了第一列宝石前 个，第二个宝石前 个，最大的总获利。初始 。

则转移显然，枚举直接卖第一列、第二列，或者加工即可。

直接优化较难，数据较为复杂。考虑同时处理所有询问。

注意到，如果将状态 看做点，三种转移看成边，则整个转移网形成了一个图。并且，只存在如下三种边：

每组讯问等价于从 走到 的最长路。

注意到只能向右上走，考虑分治。

设我们正在处理的矩形长 ，宽 。

取 、 中较小者，将其切半。

对于完全被左矩形（上矩形）包含的询问，递归处理。

对于完全被右矩形（下矩形）包含的询问，递归处理。

对于横跨中间的询问，注意到最长路一定在某个纵（横）坐标穿过中心（即，从 走到 ，或从 走到 ，另一方向同理）。

考虑枚举这条边，对于这条边的左（下、左下）端点，处理出其到矩形左下角区域内所有点的最长路；对于这条边的右（上、右上）端点，处理出其到矩形右上角区域内所有点的最长路。

对于所有要处理的询问，若该边在询问矩形范围内，则依据已处理的最长路算出贡献。

若某一矩形内没有询问，则返回。

由于该图为 DAG，最长路仍可用 DP 解决，所以总时间复杂度为 ，可以通过。