CF1809E 题解

· · 题解

0. 前言
没啥好说的。
Upd 2023.4.20 21:38 修正了线段举例的表述及 LaTeX。
Upd 2023.4.21 6:22 把题解改得正常了然后拿大号交。

1. 分析
首先不难注意到一点，两个容器的总水量不变。
这个也算是一个典型套路，记住就好。
我们假装将两个容器底部接通。
那么一次体积为 v 的挪水操作就相当于 v 次体积为 1 的挪水操作，除非某一个容器满了或空了。
我们可以认为，在数轴上 -a 和 b 分别有两个点，称为“容积上限点”。
而原点是 “分隔点”。
若干体积水可以理解为一条线段，挪水则是线段的左右滑动。但是：

考虑何种线段可以合并处理。例如，两个分别是左 0 右 5 和左 1 右 4 的线段，进行左到右的 1 的挪水后重合。因此同长度的线段可以统一考虑。
即一系列的相邻两个左端点最初差 1 的同长度的线段在数轴上进行滑动。假设左端点初始为 \{a_k\}，那么操作之后的左端点必然为 \{a_x+r,a_x+r,\dots,a_x+r,a_{x+1}+r,a_{x+2}+r,\dots,a_y+r,a_y+r,\dots,a_y+r\}，即左边一段重叠，中间两两差 1，右边一段重叠。其中 r 为挪水量的总和。

若当前状态符合这个定义，因为操作被拆分成了若干左 1 或右 1。
当左 1 时，若若干线段受 -a 限制。
则它们的左侧不可能有更多线段（否则超出 -a 限制），此时右侧的线段因为平移量只有 1 所以全部不受限。即左端进行了额外一格的吞并。
同理可以证明右 1 的 b 限制和左右的原点限制。

也就是只要算出左右的重叠长度即可。

2. AC Code 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm> 
#define int long long
#define maxn 10005
#define maxv 1005

using namespace std;

int _, n, a, b, v[maxn], ans[maxv][maxv];
void work() {
    int sum = 0;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++) cin >> v[i], sum += v[i];
    for(int w = 0; w <= a + b; w++) { //枚举线段长度
        int l = max(a - w, 0ll), r = min(a + b - w, a); //因为显然数组不能访问负的位置，所以将左右中的限制和线段都向右平移 $a$。
        int L = l, R = r;//初始状态的左端点上下界
        for(int i = 1; i <= n; i++) {
            r += v[i];
            l += v[i];
            r = min(r, R);
            l = min(l, R);
            r = max(r, L); 
            l = max(l, L);
        }
        if(l == r) {
            for(int i = L; i <= R; i++) {
                ans[a - i][i + w - a] = a - l;
            }
            continue;
        } 
        for(int i = L; i < l - sum; i++) {
            ans[a - i][i + w - a] = a - l;
        }
        for(int i = l - sum; i < r - sum; i++) {
            ans[a - i][i + w - a] = a - (i + sum);
        }
        for(int i = r - sum; i <= R; i++) {
            ans[a - i][i + w - a] = a - r;
        }
                //l-sum 和 r-sum 分别是当前合并后左端点上下界的线段在平移前的左端点值。因为这个表是要根据初始值绘制的。
    }
    for(int i = 0; i <= a; i++) {
        for(int j = 0; j <= b; j++) {
            cout << ans[i][j] << ' ';
        }cout << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    _ = 1;
    while(_--) work();
}