Codeforces Round 783 div.1 ABC (div2.CDE)

A. Make it Increasing

题意：给出一个整数序列 \(a\)，现有另一个全为0的序列 \(b\)，每次操作可以选取一个位置，使得 \(b_i\) 加上或减去 \(a_i\)，问最少多少次操作可以使得 \(b\) 序列严格递增。数据范围 \(n\le10^3\)

数据范围允许我们考虑 \(n^2\)，首先可以贪心地想到，肯定会有一个位置保持为0，那么就可以枚举这个0的位置，然后往两边贪心即可。

int n, m;
ll a[maxn], b[maxn];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    ll ans = 1e18;
    for(int i=1;i<=n;i++){
        ll sum = 0;
        b[i] = 0;
        for(int j=i-1;j>=1;j--){
            ll k = abs(b[j+1]) / a[j] + 1;
            sum += k;
            b[j] = -k * a[j];
        }

        for(int j=i+1;j<=n;j++){
            ll k = abs(b[j-1]) / a[j] + 1;
            sum += k;
            b[j] = k * a[j];
        }
        ans = min(ans, sum);
    }
    cout << ans << '\n';
}

B. Optimal Partition

题意：给出一个序列 \(a\)，可以将其分成若干个连续的子区间，每个子区间的贡献是：

• \(r−l+1\quad if s>0,\)
• \(0\quad if s=0,\)
• \(−(r−l+1)\quad if s<0.\)

求总贡献的最小值

考虑 \(dp\)，\(dp_i\) 表示前 \(i\) 个数的答案，它可以从几个方面转移过来：

• 最后一段划分的区间和为负，它不优于将所有数单独拆出来，\(dp_i=dp_{i-1}+val_i\)
• 最后一段划分的区间和为0，其实仔细想一下会发现，肯定能把它拆成两半使得它更优：
  • 区间长度为偶数，划分为等长两段，一边大于0则另一边小于0，或者都等于0，显然不会更劣
  • 区间长度为奇数，划分为左段（小一点）和右段，如果右段大于0则划分更优；如果右端小于0，则左段大于0，尝试将中间值挪到左段去，如果左段扔大于0则划分更优，否则左段小于0，则右端大于0，那么去掉中间值后，两边都大于0，显然还是更优的。
  • 所以只需考虑单个数为0的情况，同样满足 \(dp_i=dp_{i-1}+val_i\)
• 最后一段划分的区间和为正，那么 \(dp_i\) 可以从若干个前面的 \(j\) 转移过来，满足 \(val[j+1,i]\gt0\)，有 \(dp_i=dp_j+i-j\)
  • 可以通过前缀和快速计算 \(val[j+1,i]\)，我们用数据结构维护每个前缀和下的 \(dp_j-j\) 的最大值，查询比当前前缀和小的所有前缀和下的 \(dp_j-j\) 最大值即可转移
  • 前缀和范围很大，可以提前预处理然后离散化

int n, m;
int a[maxn], f[maxn], rk[maxn];
pair<ll, int> sum[maxn];

struct fwt{//FenWick Tree
    int t[maxn];
    void add(int p, int ad){ for(int i=p;i<=n+1;i+=i&-i) t[i] = max(t[i], ad);}
    int mx(int p){
        int r = -1e9;
        while(p > 0){
            r = max(r, t[p]);
            p -= p & -p;
        }
        return r;
    }
}bt;

void solve(){
    cin >> n;
    for(int i=0;i<=n+1;i++) bt.t[i] = -1e9;
    sum[0] = {0, 0};
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum[i] = {sum[i-1].first+a[i], i};
    }
    sort(sum, sum+n+1);
    int tot = 0;
    for(int i=0;i<=n;i++){
        if(i == 0 || sum[i].first != sum[i-1].first) ++tot;
        rk[sum[i].second] = tot;
    }
    bt.add(rk[0], 0);
    for(int i=1;i<=n;i++){
        f[i] = f[i-1] + (a[i] < 0 ? -1 : a[i] > 0 ? 1 : 0);
        f[i] = max(f[i], bt.mx(rk[i]-1) + i);
        bt.add(rk[i], f[i] - i);
    }
    cout << f[n] << '\n';
}

C. Half Queen Cover

题意：有一个 \(n\times n\) 的棋盘，棋子“半皇后”可以控制其同一排，同一列，同一左上-右下对角线上的所有格子，问最少多少个半皇后可以控制整个棋盘。

构造题，单纯看结论会感到莫名其妙，不知思路从哪来

提供一种思考过程：想让棋子数量少，就需要尽可能减少棋子控制范围的重复，理想情况下应该有：每行仅有一个棋子，每列仅有一个棋子，每对角线也仅有一个棋子。即除了不可避免的交叉之外不重复。

接下来考虑这种理想情况能否实现，大概会摸出这样的图：

这里一共使用了5个棋子，发现中间区域还没能填满，那么就继续扩张，假设左上放置 \(x\) 个棋子，右下放置 \(y\) 个棋子，那么中间部分能占据的完整矩形范围为 \(max(x,y)\)， 即 \(x+y+max(x,y)\ge n\)，此时为最优解。

我们当然要让 \(x,y\) 之间差不超过1...