题解：CF2248F Matrix Elimination

AeeE5x · 2026-08-04 11:10:01 · 题解

前言

绝世好题。

赛时就差最后一步没时间了。

Solution

Part 1

注意到单点减是不优的，因此对于一个数而言，被减的同行同列的其他数的数量不会少于 1，即题目中的式子一定会趋于成立而非不成立。

而且注意到同行同列的数减的越多越优。

所以我们猜一个结论：每次操作都是对整个矩形全体减 1。

这显然是错的，所以我们尝试寻找这个结论成立的条件。

设 h_{i,j} = \sum\limits_{k=1}^{m}a_{i,k} + \sum\limits_{k=1}^{n}a_{k,j} - 3a_{i,j}。

显然，一个位置是好的，当且仅当 h_{i,j}\le 0。

对于一次操作，考虑将位置分为两种：被减的、没被减的。

• 对于没被减的数，考虑最大能对其 h_{i,j} 造成的负增量，这个显然是 \max(n-1, m-1)。
• 对于被减的数，显然应取整个矩形来减，负增量为 n+m-2\color{red}-1。这个 -1 是因为减了 (i,j) 自己。

因此，如果我们要求一直减整个矩形就能取到最优，应满足：

这个条件等价于：

反过来，就是 n=1 或 m=1。

因此，只要这个矩阵长得不是一个序列，我们一直减整个矩形就是对的。考虑每个数需要被减的次数 \max \left(0,\left\lceil \dfrac{h_{i,j}}{n+m-3} \right\rceil\right)，放到全局取第 k 小即可。

观察样例，16 组里只有两组满足 \min(n,m)\ge 2。这更加印证了我们的结论是对的。

Part 2

接下来，我们把这个问题转化到了序列上。

记 n 为序列长度，a_i 为原本矩阵中的第 i 个数，g_i=\sum\limits_{k=1}^{n}a_k-2a_i。

这个时候我们发现减整个序列不一定优，还有可能减 [1,n-1] 的前缀或 [2,n] 的后缀。

如果是对更短的区间减，则不难发现会被减整个序列偏序掉，因此不需要考虑。

• 操作 1：对整个矩形减，会对每个 g_i 带来 n-2 的负增量。
• 操作 2：对前缀 [1,n-1] 减，会对 g_{[1,n-1]} 带来 n-3 的负增量，对 g_n 带来 n-1 的负增量。
• 操作 3 是对称的。

再次假设，我们进行了操作 2 和操作 3 各至少一次，则我们对 g_1 和 g_n 的负增量为 2n-4，对 g_{[2,n-1]} 的负增量为 2n-6。

这种情况也被两次操作 1 偏序掉了，因此我们发现操作 2 和操作 3 只会出现其中一种。

我们以只出现操作 2 为例。

若我们进行了至少一次操作 2，则 g_n 在操作结束后必须要满足 g_n\le 0。否则不进行操作 2 全部进行操作 1 是更优的。

这个很好理解，因为操作 2 对其他数的负增量只有 n-3，最后如果 g_n 没有依靠 n-1 负增量冲进前 k 小，则只使用操作 1 达成这个一定是不需要更多次的。

Part 3

接下来考虑如何计算。

假设我们进行了 t 次操作 2 和 u 次操作 1，则有下式：

操作总次数记为 T：

对 t 放缩，得到 T 的三个下界：

若 k=1，则没有第一、三个限制，直接返回第二个式子的下界即可。

不难发现 g_i 越小，被减少到 0 的就越早。

因此我们将 g_{[1,n-1]} 排序，取第 k-1 小的 g_{k-1} 替换上面的 i。

Part 4

结束了吗？并没有。

上面算出来的 T 的下界一定能够取到吗？还需要验证。

根据 Part 3 的式子，得到 t 的范围：

若上述不等式有解，则当前情况的答案为 T。

Code

妈呀这个太难写了。

:::success[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

long long n,m,k;
vector<vector<long long> > a;
long long rsum[100010],csum[100010];

long long solve1(){
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) rsum[i]+=a[i][j],csum[j]+=a[i][j];

    vector<long long> vec;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        long long d=(rsum[i]+csum[j]-a[i][j]*2)-a[i][j];
        vec.push_back(max(0ll,(d+(n+m-3)-1)/(n+m-3)));
    }
    for(int i=1;i<=n;i++) rsum[i]=0;
    for(int i=1;i<=m;i++) csum[i]=0;
    sort(vec.begin(),vec.end());
    return vec[k-1];
}

long long g[100010];
long long solve2(vector<long long> b){
    long long sum=0;
    for(int i=1;i<=n;i++) sum+=b[i];
    for(int i=1;i<=n;i++) g[i]=sum-2*b[i];
    sort(g+1,g+n);

    if(k==1) return max(0ll,(g[n]+(n-1)-1)/(n-1));

    long long cnt=max({(g[k-1]+(n-2)-1)/(n-2),(g[n]+(n-1)-1)/(n-1),(g[k-1]+g[n]+(n*2-4)-1)/(n*2-4),0ll});
    if(max(g[n]-(n-2)*cnt,0ll)<=min(cnt,(n-2)*cnt-g[k-1])) return cnt;
    return infll;
}

int main(){
    cin.tie(0)->sync_with_stdio(false);

    int T;cin>>T;
    while(T--){
        cin>>n>>m>>k;
        a.resize(n+1);
        for(int i=1;i<=n;i++) a[i].resize(m+1);
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];

        if(n==1||m==1){
            if(n==1&&m==1){
                if(a[1][1]>=0) cout<<"0\n";
                else cout<<"-1\n";
            }else if((n==1&&m==2)||(n==2&&m==1)){
                if(k==1) cout<<"0\n";
                else cout<<llabs(a[min(n,1ll)][min(n,1ll)]-a[n][m])<<"\n";
            }else{
                long long ans=solve1();
                vector<long long> b(max(n,m)+1);
                for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) b[i+j-1]=a[i][j];
                n=max(n,m);

                ans=min(ans,solve2(b));
                reverse(b.begin()+1,b.end());
                ans=min(ans,solve2(b));
                cout<<ans<<"\n";
            }
        }else cout<<solve1()<<"\n";
    }

    # ifdef KarmaticEnding
    cerr<<"\n\033[1;38;2;234;200;225mUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\033[0m\n";
    # endif
    return 0;
}

:::