Solution P9051 | F**king Convexity

拿到这个题，哇，时限 6 秒，先二分答案肯定不劣。就算多个 log 应该也能冲过去。

二分答案，要求最大子段和

\le M

，然后设计一个 dp。由于

V

很大，我们争取让 dp 的维度都是

\mathcal{O}(n)

级别。

考虑从左往右确定

i

选择

a_i

还是

b_i

，同时为了维护最大子段和，我们应该记录最大后缀和，要求最大后缀和保持

\le M

。

那么

f_{i,j}

表示前

i

个数中选

j

个

a_i

（剩下的选

b_i

）的最大后缀和的最小值，不难写出转移：

f_{i,j} = \max(0, \min(f_{i-1,j} + b_i, f_{i-1,j-1} + a_i))

特别地，当

f_{i,j} > M

，将其赋值为

+\infty

。

注意到

f_i

具有凸性，考虑用一个堆去维护差分数组，每次会插入一个

a_i - b_i

。

需要进行的操作：

全局加 $b_i$ ；
往维护差分数组的堆中插入一个 $a_i - b_i$ ；
全局对 $0$ 取 $\max$ ；
扔掉所有 $>M$ 的 dp 值。

什么，你想让我讲讲怎么处理细节？还是自己吃一下这坨吧。

这里给一个技巧：令

x = \sum [a_i \le b_i]

，若

k \le x

，那么

k

越大，答案越小，维护的凸包就是单调递减的，不用维护后面上升的部分，大大方便了实现。

那么当

k > x

的时候，交换序列

a

和

b

并令

k' = n - k

即可。

然后讲讲输出方案，其实就是找到最后堆中较小的

k

个数值的对应位置（

a_i - b_i

对应的

i

），所以用 set<pair<ll,ll>> 维护堆，顺便记录编号。

但是有一个问题，堆中的数值会被修改，有些会被修改成

0

，而有些

0

不能计入方案，就是那些一开始

b_i < a_i

的

i

。由于之前保证了

k \le x

，把这个编号

i

标记作不能用即可，后面不会出现不够用的情况（因为选

i

只会让答案更劣）。

以下是完整的 checker 部分代码，供参考。

CPP

bool flg; // 表示一开始是否有交换 a,b
namespace Check{ 
	set<pair<ll,ll>>Q; // 记录差分数值及其对应位置
	ll ht=0, sum=0;
	vector<ll>zero_edge; // 末尾有一车 0，记录其对应位置
	vector<ll>ans; // 开头有一些因为 >mid 被删除的元素，记录其对应位置
	bool check(ll mid){
		Q.clear(), zero_edge.clear(), ans.clear();
		ht = sum = 0; // ht 是 dp 值的首项，sum 是差分数组的总和
		for(ll i=1;i<=n;i++){
			ht += b[i];
			if(a[i]-b[i] <= 0){
				Q.emplace(a[i]-b[i], i), sum+=a[i]-b[i];
			}else{
				Q.emplace(0, n+1);
			} // n+1 表示不能计入最终方案
			// erase <0
			while(ht+sum<0){
				if(!Q.size()) {
					ht = 0;
					break;
				}
				auto p = *(--Q.end()); auto [x,y] = p;

				if(ht+sum-x<=0){
					sum -= x; zero_edge.pb(y);
					Q.erase(p);
				}else{
					// make ht+sum=0
					ll fw = ht+sum;
					x -= fw, sum -= fw;
					Q.erase(p); Q.emplace(x,y);
					break;
				}
			}

			// erase >mid
			while(ht > mid){
				if(!Q.size()) return 0;
				auto p = *Q.begin(); auto [x,y] = p;

				ht += x, sum -= x, ans.pb(y);
				Q.erase(p);
			}
		}

		// output
		ll K = k;
		if(ans.size() <= K && K <= ans.size() + Q.size() + zero_edge.size()){
			for(int i=1; i<=n; i++) str[i] = 'B'-flg;
			for(auto x: ans){
				if(x != n+1){
					str[x] = 'A'+flg;
					K--;
				}
			}
			while(K && Q.size()){
				auto [x,y] = *Q.begin();
				Q.erase({x,y});
				if(y != n+1){
					str[y] = 'A'+flg;
					K--;
				}
			}
			reverse(zero_edge.begin(), zero_edge.end());
			while(K && zero_edge.size()){
				if(zero_edge.back() != n+1){
					str[zero_edge.back()] = 'A'+flg;
					K--;
				}
				zero_edge.pop_back();
			}

			return 1;
		}
		return 0;
	}
}

Solution P9051 | F**king Convexity

文章操作

相关推荐

评论

Solution P9051 | F**king Convexity