题解：CF1209E1 Rotate Columns (easy version)

· · 题解

糖麻了，挑战最糖解。

当 n<4 时显然可以取到最大的 n 个数。

于是下面只讨论 n=4 的情况。

显然选取的四个数除了两两分组存在于两个列里而且高度差不同这一种情况，其他都可以全部取到。

这样就可以暴力 check 是否合法。

先判断最大的四个数。
可行就做完了，不行继续看下面。

判断最大的三个数加上第五大的数。
可行就做完了，不行继续看下面。

两个都不可以，放回去构造局面，会发现应当是：

5 1 1 3
1 1 1 5
5 1 1 4
1 1 1 1

这样的东西，把 \texttt 3 和 \texttt 4 都试了。

于是取前五大去掉第三大一定是合法解。

被叉了。有可能第三大非常牛，绝对不能扔。

然后你发现此时把第五大换第六大也一定合法。

两个方案取最优即可。

做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fish{
    int x,X,Y;
};
bool cmp(fish x,fish y){
    return x.x>y.x;
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<fish>ve;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        int x;
        cin>>x;
        ve.push_back({x,i,j});
    }
    sort(ve.begin(),ve.end(),cmp);
    if(n==4){
        map<pair<int,int>,bool>mp;
        for(int i=0;i<n;i++){
            mp[{ve[i].X,ve[i].Y}]=1;
        }
        bool flc=1;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(ve[i].Y!=ve[j].Y&&(mp[{ve[i].X+1,ve[i].Y}]||mp[{ve[i].X+3,ve[i].Y}])&&mp[{ve[j].X+2,ve[j].Y}])flc=0;
        }
        int ans=0;
        if(flc)for(int i=0;i<n;i++)ans+=ve[i].x;
        else{
            ans+=ve[n].x;
            ans+=ve[0].x;
            ans+=ve[1].x;
            mp.clear();
            for(int i=0;i<=n;i++){
                if(i==n-1)continue;
                mp[{ve[i].X,ve[i].Y}]=1;
            }
            flc=1;
            for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++){
                if(i==n-1)continue;
                if(j==n-1)continue;
                if(ve[i].Y!=ve[j].Y&&(mp[{ve[i].X+1,ve[i].Y}]||mp[{ve[i].X+3,ve[i].Y}])&&mp[{ve[j].X+2,ve[j].Y}])flc=0;
            }
            if(flc)ans+=ve[n-2].x;
            else ans+=ve[n-1].x,ans=max(ans,ve[0].x+ve[1].x+ve[2].x+ve[5].x);
        }
        cout<<ans<<'\n';
    }else{
        int ans=0;
        for(int i=0;i<n;i++)ans+=ve[i].x;
        cout<<ans<<'\n';
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 人都有善意和恶意，接受这一切并加以俯瞰，然后确实守护自己重要的事物。
// 这是玛格过去的未婚夫的生存方式。

// 玛格现在也看著和他一样的事物，用同样的方式思考。
// 她追上了憧憬的背影，即使那里已经没有他的身影，还是走在相同的地方。
// 缇亚忒明白那是能让人非常满足的事情。

必须得注意的是：

5 1 5 1
1 1 5 1
5 1 1 1
1 1 1 1

除了这种。

1 5 5 1
1 1 5 1
1 1 1 1
1 5 1 1

这个也不合法，duel 的时候注意力不够没发现，哭了。

nbh 一秒给我 hack 了，狠狠被吊打。（nbh 这么强 NOIP 肯定要 400 了！！）

警钟长鸣。

一天之内两把 duel 掉了 200 rating /dk

喵喵快碎成「喵喵碎片」了，可以点个赞祝喵喵 NOIP rp++ 吗 QwQ